如何从预订单遍历中列出二进制搜索树中每个节点的子节点

Question

给定一个作为int向量的预序遍历(例如{7,4,3,6,5,8,10}(，我如何列出迭代每个节点的子节点？

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

我生成了一个树，然后递归地列出每个子项，但我只需要使用给定的向量。知道吗？

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

Answer 1

经过几次尝试，我成功了。对于每个iteation，你必须找到更多和更少的元素，打印它们，并将它们设置为常用元素，以避免打印其他分支的值。

#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