c++ - 打印的二叉树问题。用户输入不打印任何内容

Question

我正在尝试通过用户输入创建和打印二叉树，但它不起作用。我正在提供输入 8 3 10 1 6 14 4 7 13 -1 但没有打印任何内容。我做错了什么？

#include<iostream>
#include<queue>
using namespace std;
class node
{public:
    int data; //data for node
    node* left;//pointer for left subtree
    node* right;//pointer for right subtree
    node(int d):data(d),left(NULL),right(NULL) //constructor
    {

    }
};

node* createTree() //creating tree
{
    int d;
    cin>>d;
    if(d==-1)
    {
        return NULL; //when user inputs -1 return NULL
    }

    node* root=new node(d);
    root->left=createTree();
    root->right=createTree();
    return root;
}

void printTree(node* root)
{
    if(root==NULL)
    {
        return; //when null is encountered return
    }

    cout<<root->data<<" ";
    printTree(root->left); //printing recursively left subtree
    printTree(root->right);//printing recursively right subtree
}

int main()
{
   node* root=createTree(); 
   printTree(root);
   return 0;
}

Answer 1

您的程序仍在等待输入。我将尝试用调用图来解释原因。假设您使用输入 8 3 10 1 运行程序.这将创建一个函数调用树，如下所示:

                                                     (next input)
                                                    /
                                        (4, input=1)
                                       /            \
                          (3, input=10)              (waiting...)
                         /             \
             (2, input=3)               (waiting...)
START:      /            \
(1, input=8)              (waiting...)
            \
             (waiting...)

在这里，每个标记为 waiting... 的节点对应于对 createTree 的调用，总是会通过 cin>>d; 询问用户输入陈述。要完成这棵树，您实际上需要输入 8 3 10 1 -1 -1 -1 -1 -1 , 结束每个等待节点。另外，请注意这棵树是非常线性的，因为您插入的元素深度优先。您可以将输入结构化为 8 3 -1 -1 10 -1 -1 ，这将创建以下树:

         null
        /
     (3)
    /   \
   /     null
(8)
   \      null
    \    /
     (10)
         \
          null

所以你不致力于线性树。如果你想创建一个平衡树，你可以做的一件事是首先将所有输入读入 std::vector<int>直到第一个-1被读取，然后使用该 vector 以广度优先 顺序插入元素。或者，您可以使用二叉搜索树技术逐个插入元素。