c ++ проблема рекурсивной печати двоичного дерева

Question

Я практиковал некоторые старые проблемы C ++, чтобы подготовиться к нескольким собеседованиям, и в настоящее время я пытаюсь рекурсивно построить двоичное дерево из массива, а затем рекурсивно распечатать его в порядке следования.Тем не менее, я получил некоторые странные значения при попытке вывести результат.

Проблема: создать двоичное дерево из массива [4,2,5,1,3], а затем создать функцию, которая печатает
ихinorder рекурсивно.

Ответ: Я могу напечатать результат, однако мое решение содержит некоторые неожиданные нули, которые также выводятся в результате.Я понятия не имею, как эти 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 ++ и рекурсией ... Надеюсь, вы, ребята, сможете мне помочь.

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 следующим образом: - <br> node *tmp = null;<br> if(num < SIZE)<br> {<br> tmp= new node();<br> ......<br> }<br> return tmp;

Answer 3

У вас есть другая проблема.Ваш алгоритм упорядочения дерева сильно зависит от порядка, в котором вы посещаете данные.Попробуйте ваше решение на

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