-2

我必须在 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();
}

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

如上所述，我刚刚开始使用 C++ 进行开发。是的，有一些 BFS 的示例算法或相关的东西，但没有一个像我的那样复杂。

4

1 回答 1

0

从您的代码中，我可以生成缺少的头文件。但我的一些声明可能与你的不同。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 中的 Data Structures & Algorithms, 2nd ed 中所写的内容。罗伯特·拉福尔第 381-382页。如果您想继续使用 C++ 进行计算机科学的这一部分编程，我建议您学习一些通用的 C++ 和 C++ 中的数据结构和算法（我听说 Robert Sedgewick 写了一本书）。

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

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

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

于 2018-05-12T11:15:02.100 回答