根据给定的二叉树,先人工对其进行先序遍历,根据先序遍历的结果编写程序创建该二叉树;然后用非递归中序遍历算法,输出中序遍历的结果。
时间: 2023-07-22 12:02:59 浏览: 81
二叉树的几种操作,包括递归先序建立二叉树、先序遍历、中序遍历、后序遍历、非递归的各种遍历
在这里,假设二叉树的每个节点都包含三个属性:val(节点值)、left(左子节点)、right(右子节点)。
首先,给定二叉树的先序遍历结果为:[1, 2, 4, None, None, 5, None, None, 3, 6, None, None, 7, None, None],其中 None 表示该节点为叶子节点。
根据先序遍历的结果创建二叉树的步骤如下:
1. 定义一个栈和一个指针 index,初始值为 0。
2. 将根节点创建出来并入栈。
3. 循环执行以下操作,直到栈为空:
1. 取出栈顶节点,以及其在先序遍历结果中对应的值。
2. 如果值为 None,说明该节点为叶子节点,直接跳过。
3. 否则,根据该值创建左子节点和右子节点,并入栈。注意入栈时要先入右子节点再入左子节点,因为先序遍历是先遍历左子树再遍历右子树。
4. 将指针 index 加一,指向下一个节点的值。
下面是具体的 Python 代码实现:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
preorder = [1, 2, 4, None, None, 5, None, None, 3, 6, None, None, 7, None, None]
stack = []
root = TreeNode(preorder[0])
stack.append(root)
index = 1
while stack:
node = stack.pop()
if preorder[index] is not None:
node.left = TreeNode(preorder[index])
stack.append(node.left)
index += 1
if preorder[index] is not None:
node.right = TreeNode(preorder[index])
stack.append(node.right)
index += 1
```
接下来,我们使用非递归中序遍历算法输出中序遍历的结果。具体思路如下:
1. 定义一个栈和一个指针 node,初始值为根节点。
2. 循环执行以下操作,直到栈为空且当前节点为 None 时结束:
1. 将当前节点及其左子节点依次入栈,直到当前节点为 None。
2. 取出栈顶节点,输出该节点的值,并将指针 node 指向该节点的右子节点。
下面是具体的 Python 代码实现:
```python
stack = []
node = root
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack.pop()
print(node.val)
node = node.right
```
因此,该二叉树的中序遍历结果为:4 2 5 1 6 3 7。
阅读全文