时间戳

首页 > 解决方案 > 打印的二叉树问题。用户输入不打印任何内容

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

问题描述

我正在尝试通过用户输入创建和打印二叉树，但它不起作用。我提供输入 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;
}

标签： c++

解决方案

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

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

在这里，每个标记为waiting...is 的节点都对应于对 的调用createTree，它总是会通过cin>>d;语句询问用户输入。要完成这棵树，您实际上需要输入8 3 10 1 -1 -1 -1 -1 -1, 来结束每个等待节点。另外，请注意这棵树是非常线性的，因为您要插入元素depth-first。您可以像 一样构建输入8 3 -1 -1 10 -1 -1，这将创建以下树：

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

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

推荐阅读