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!nn";
}
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";
}
}
}

在这个文件中有些东西搞砸了，我不知道。我只想打印元素，并不总是文本消息"调用打印功能！"，我想将它们打印到输出控制台。图形输出可以在以后完成，现在我只想让它运行。

#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!nn";
if (pInternalRep == NULL) return;
//CSearchTreeBin::Print(); // this won't work that easily
//pInternalRep->CSearchTreeBin::Print();
}

不知何故，我/我们必须找到一种方法来打印包含元素，如果它们已经在树内，否则我必须找到树保持为空的错误。

如上所述，我刚刚开始在C++开发。是的，有一些BFS的示例算法或相关的东西，但它们都没有像我这样复杂。

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

可能会有问题，因为我(简单地(将所有内容都放在公共范围内。

你需要实现函数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();
}
}

这类似于 Java 中的数据结构和算法，Robert Lafore 第 2 版第 381-382 页。如果你想在C++年继续在计算机科学的这一部分编程，我的建议是学习一些通用C++和C++的数据结构和算法(我听说罗伯特·塞奇威克写了一本书(。

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

你在代码注释中提出了更多的问题，你的代码有一些粗糙的C++部分(0和NULL之间的不一致，有时使用std::，有时写using namespace...... 这个网页可能会帮助你学习英语或德语的C++元素。另外，欢迎来到C++编程。

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