c++递归打印二叉树的问题

Question

我一直在练习一些旧的 C++ 问题，为一些工作面试做准备，目前我正在尝试从数组递归构造二叉树，然后也递归地按顺序打印它。然而，当我尝试输出结果时，我得到了一些奇怪的值。

问题：从数组 [4,2,5,1,3] 构造二叉树，然后创建一个打印
的函数 它们递归地按顺序排列。

答案：我能够打印结果，但是我的解决方案包含一些意外的 0，这些 0 也会在结果中打印。我不知道这些 0 如何最终出现在打印结果中。

这是我当前的打印结果（注意值之间不需要的 0）：
0 1 0 2 0 3 0 4 0 5 0

这是我编写的 C++ 解决方案。 （只需复制并粘贴并在编译器上运行它）：

#include <iostream>

using namespace std;

const int SIZE = 5;

struct node{
    node *leftBranch;
    node *rightBranch;
    int val;
};

int data[SIZE] = {4,2,5,1,3};
node* construct_tree(int);
void print_tree(node*);

node * construct_tree(int num){
    node *tmp = new node();
    if(num < SIZE){
        tmp->leftBranch = construct_tree(2*num + 1);
        tmp->val = data[num];
        tmp->rightBranch = construct_tree(2*num + 2);
    }
    return tmp;
}

int main(){
    node *tree = construct_tree(0);
    print_tree(tree);
    return 0;
}

void print_tree(node* tree){
    if(tree == NULL)
        return;
    print_tree(tree->leftBranch);
    cout<<tree->val<<" ";
    print_tree(tree->rightBranch);
}

我想我对 C++ 和递归有点生疏了..我希望你们能帮助我。thx

Answer 1

问题出在construct_tree上。对它的调用是：

construct_tree(0) -- from main()
    construct_tree(1)
        construct_tree(3)
            construct_tree(7)
            construct_tree(8)
        construct_tree(4)
            construct_tree(9)
            construct_tree(10)
    construct_tree(2)
        construct_tree(5)
        construct_tree(6)

问题是，对construct_tree的每次调用都会创建一个添加到树中的新节点，即使num超出范围也是如此。

Answer 2

特德是对的。尝试按如下方式更改construct_tree：-
<代码>
节点 *tmp = null;
if(num < 大小)
{
tmp=新节点();
……
}
返回tmp；

Answer 3

你还有另一个问题。对树进行排序的算法高度依赖于您访问数据的顺序。尝试您的解决方案

int data[SIZE] = {5, 4, 3, 2, 1};