扩展二叉树的先序遍历序列构建二叉树c++
时间: 2023-10-06 08:08:51 浏览: 108
扩展二叉树的先序遍历序列可以表示为一个字符串,我们可以按照以下步骤构建二叉树c:
1. 将字符串的第一个字符作为根节点的值创建一个根节点。
2. 如果字符串的下一个字符是字符‘#’,则将当前节点的左子节点设置为NULL,并将字符串中的第一个字符和第二个字符删除;否则,将字符串的下一个字符作为当前节点的左子节点的值创建一个左子节点,然后递归调用步骤2,直到左子树构建完成。
3. 如果字符串的下一个字符是字符‘#’,则将当前节点的右子节点设置为NULL,并将字符串中的第一个字符和第二个字符删除;否则,将字符串的下一个字符作为当前节点的右子节点的值创建一个右子节点,然后递归调用步骤2,直到右子树构建完成。
4. 返回根节点。
示例:
假设扩展二叉树的先序遍历序列为“AB##C##”,则根据上述步骤,我们可以构建二叉树c:
1. 创建根节点A。
2. 将下一个字符B作为A的左子节点的值创建一个左子节点B,然后递归调用步骤2。
3. 将下一个字符#作为B的左子节点,将下一个字符#作为B的右子节点,因此B的左右子树都为空,返回B到A的左子节点。
4. 将下一个字符C作为A的右子节点的值创建一个右子节点C,然后递归调用步骤2。
5. 将下一个字符#作为C的左子节点,将下一个字符#作为C的右子节点,因此C的左右子树都为空,返回C到A的右子节点。
6. 根据上述构建过程,我们得到了如下的二叉树:
A
/ \
B C
/ \
NULL NULL
注意:扩展二叉树本身已经包含了NULL节点,因此在构建二叉树时,如果遇到字符‘#’,则直接将子节点设置为NULL即可。