C++二叉树打印函数实现

Question

我必须用 C++ 实现二叉树，问题是我刚开始用 C++ 编写代码。所以我对这个话题真的很陌生，在我用 C 或 Python 编码之前，而不是在 C++ 中编码。

我已经创建并初始化了一个二叉树，覆盖了一些叶子，一个树根元素，现在我想看看我所做的是否正确，因此它有效或者完全是胡说八道。

查看我的代码，我使用Visual Studio 2017 Enterprise:

"bintree.cpp"
#include "cseatreebin.h"
#include <iostream>
using namespace std;

void main() 
{
CSearchTreeBin MyTree;
std::cout << "#######################################################\n"
             "##################Binary Tree C++######################\n";

MyTree.Insert(5);
MyTree.Insert(15);
MyTree.Insert(7);
MyTree.Insert(-5);
MyTree.Insert(6);
MyTree.Insert(3);
MyTree.Insert(650);
MyTree.Insert(20);
MyTree.Insert(-20);
MyTree.Insert(510);
MyTree.Print();
MyTree.Print(); cout << endl;
//cout << "Amount of Treenodes: " << MyTree.GetNrOfNodes() << endl;
// Amount/Number should be calculated again if allready called once
//cout << "Amount of Treenodes: " << MyTree.GetNrOfNodes() << endl;
// ... only if the tree has changed... 
//MyTree.Insert(99);
//cout << "Number of treenodes: " << MyTree.GetNrOfNodes() << endl;
}

自定义头文件：

"cseatreebin.h"
#ifndef SEARCHTREEBIN_H
#define SEARCHTREEBIN_H

class CSearchTreeBinInt;

class CSearchTreeBin 
{
public:
CSearchTreeBin(void);

void Insert(int);

void Print();

private:
CSearchTreeBinInt *pInternalRep;
};

#endif  // SEARCHTREEBIN_H

我的二叉树初始化文件：

#include "cseatreebinint.h"
#include <stdlib.h>
#include <iostream>

using namespace std;
CSearchTreeBinInt::CSearchTreeBinInt()
{
pRoot   = 0; //init and create treeroot
};

void CSearchTreeBinInt::Insert(int dat)  
{
Insert(pRoot, dat); //insert the root to the tree
}

void CSearchTreeBinInt::Insert(Node*& rpNode, int dat) 
{
if (rpNode == NULL) //check if there are nodes in the tree
{
rpNode        = new Node; //create new nodes if there are none
rpNode->dat   = dat; 
rpNode->pLeft = rpNode->pRight = NULL;
std::cout << "Binary Tree  has been initalized correctly-> inserting new Elements!\n\n";
 }
else
 {
   if (dat < rpNode->dat) {            // inserted data is less then existing?
       Insert(rpNode->pLeft, dat);    // put it on the left
       std::cout << "A Node has been inserted on the left!\n";
   }
   else {                              // if it's bigger then already existing nodes
       Insert(rpNode->pRight, dat);   // put it on the right side of the tree
       std::cout << "A Node has been inserted on the right side!\n";
   }
  }
  }

我不知道这个文件中有什么地方乱七八糟的。我只想打印元素，而不是总是打印文本消息 "Call Printfunction!"，我想将它们打印到输出控制台。图形输出可以稍后完成，现在我只想制作它运行。

#include "cseatreebin.h"
#include "cseatreebinint.h"
#include <stdlib.h>
#include <iostream>

using namespace std;



CSearchTreeBin::CSearchTreeBin()
{
pInternalRep=new CSearchTreeBinInt; //init. and creation of Binarytree
};
void CSearchTreeBin::Insert(int dat)  //dat = is this the node which will   be inserted?
{
pInternalRep->Insert(dat);
}

void CSearchTreeBin::Print() {
int a;
std::cout << "Printfunction has been called!\n\n";
if (pInternalRep == NULL) return;

//CSearchTreeBin::Print(); // this won't work that easily
//pInternalRep->CSearchTreeBin::Print();
}

不知何故 I/we 必须找到一种方法来打印包含的元素，如果它们已经在树中，否则我必须找到为什么树仍然为空的错误。

如上所述，我刚开始使用C++进行开发。是的，有一些 BFS 或相关算法的示例算法，但其中 none 和我的一样复杂。

Answer 1

根据您的代码，我可以生成缺少的头文件。但我的某些声明可能与您的不同。 node 和 CSearchTreeBinInt 的头文件看起来像这样，也许：

/* "cseatreebinint.h"
 *
 */
#ifndef SEARCHTREEBININT_H
#define SEARCHTREEBININT_H

class Node
    {
public:
    Node *pLeft, *pRight;
    int dat;
    void Print(); //maybe this needs to be added
    };

class CSearchTreeBinInt
    {
public:
    Node* pRoot;
    CSearchTreeBinInt(void);
    void Insert(int);
    void Insert(Node*& , int );
    };

#endif  // SEARCHTREEBININT_H

可能会有问题，因为我（简单地）将所有内容都放在 public 范围内。

你需要实现函数Node::Print，因为我添加了这个函数。例如。简单，用于打印树的递归函数如下所示：

void Node::Print()
    {
    std::cout << "This node contains the value " << dat << std::endl;
    if (pLeft != NULL)
        {
        pLeft->Print();
        }
    if (pRight != NULL)
        {
        pRight->Print();
        }
    }

这类似于 Data Structures & Algorithms in Java, 2nd ed. by Robert Lafore 第 381-382 页中的内容。如果您想继续使用 C++ 进行计算机科学这一部分的编程，我建议您学习一些通用的 C++ 以及 C++ 中的数据结构和算法（我听说 Robert Sedgewick 写了一本书）。

最后一点：在您的函数 CSearchTreeBin::Print 中，您需要添加一个 else-case 并检查有效的根节点。如果根节点有效，则调用根节点的递归 Print 并观察魔术的发生。

您在代码注释中提出了更多问题并且您的代码有一些粗略的 C++ 部分（0 和 NULL 之间的不一致，有时使用 std:: 有时写 using namespace...)。此网页可能会帮助您学习 English or maybe German 中的 C++ 元素。另外，欢迎来到 C++-Programming。

编辑： 你不会像我那样命名函数 Node::Print，但我会这样命名。

C++二叉树打印函数实现

C++ Binary Tree Print Function Implementation

c++

binary-tree

binary-search-tree

computer-science

breadth-first-search