c++ - 如何从顺序遍历中列出二叉搜索树中每个节点的子节点？

Question

给定一个遍历遍历作为int vector (例如{7,4,3,6,5,8,10})，我怎么能列出
迭代地每个节点的子节点？

Example output
7 - 4 8
4 - 3 6
6 - 5
8 - 10

我让它生成一棵树，然后递归列出每个 child ，但是我只需要使用给定的 vector 就可以了。任何的想法？

我不是在要求代码，只是一些很酷的想法

Answer 1

经过几次尝试，我做到了。对于每个迭代，您都必须找到更多和更少的元素，进行打印，然后将它们设置为用于避免从其他分支打印值的元素。

#include<stdio.h>
#include<iostream>

using namespace std;

int main(){
    int preOrder[] = {7,4,3,6,5,8,10};
    int size = sizeof(preOrder)/sizeof(int);
    bool used[size] = {false};
    for(int i = 0; i < size; ++i){
        bool lesserFound = false;
        bool greaterFound = false;
        for(int j = i+1; j < size; ++j){
            if(used[j]==true)
                lesserFound=greaterFound=true;

            if(preOrder[j]<preOrder[i] && lesserFound==false){
                cout << preOrder[i] << " - LeftChild: " << preOrder[j] << endl;
                lesserFound=true;
                used[j]=true;
            }else if(preOrder[j]>preOrder[i] && greaterFound==false){
                cout << preOrder[i] << " - RightChild: " << preOrder[j] << endl;
                greaterFound=true;
                used[j]=true;
            }
        }
    }
}

输出:

7 - LeftChild: 4
7 - RightChild: 8
4 - LeftChild: 3
4 - RightChild: 6
6 - LeftChild: 5
8 - RightChild: 10