我有一个用预序遍历表示的二叉树,它看起来像这样:{1 4 6 10 0 0 0 7 0 8 0 0 2 5 0 0 3 9 0 0 0 }
,其中0表示没有元素的子元素。
如何从这些数据构造原始的二叉树?我试图用递归来解决问题,但是我还没有意识到如何处理节点的正确子节点,因为我无法计算它们在数组中的位置,除非它们有一个叶子作为父节点(叶子后面有两个零,这表示它没有子节点)。
我觉得解决办法应该很简单,但还是看不出来。
最佳答案
像这样简单的事情可能对你有用。您只需要在输入序列的预排序解释中重新构建树。以下代码不会验证输入序列以检查其是否是有效的树表示形式。
struct BTNode {
int data;
BTNode* left;
BTNode* right;
}
BTNode* BuildTree(int* sequence, int& pos) {
int value = sequence[pos++];
if (value == 0)
return nullptr;
BTNode* node = new BTNode;
node->data = value;
node->left = BuildTree(sequence, pos);
node->right = BuildTree(sequence, pos);
return node;
}
关于algorithm - 来自指定遍历的二叉树,其中指定了缺席的子级,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/35093006/