采用二叉树链表作为存储结构,设计一棵二叉树,输入完全二叉树的先序序列,用#代表虚结点(空指针),如ABD###CE##F##,建立二叉树。先序、中序和后序遍历的递归操作和中序的非递归操作,求出先序、中序和后序遍历序列,求树的高度,叶子结点个数及结点总数。
时间: 2023-07-21 15:11:07 浏览: 129
二叉树_17281183_刘梦婷_splitns2_扩展先序序列_二叉树_
好的,我明白了。这是一道关于二叉树的综合题目,我会尽力回答你的问题。
首先,根据输入的完全二叉树的先序序列,我们可以通过递归的方式建立这棵树。具体来说,我们可以按照先序序列的顺序逐个读取结点,如果读到的是一个实结点,则创建一个新结点并将其赋值为当前读取的结点;如果读到的是一个虚结点,则直接返回 NULL。在创建完当前结点后,我们可以递归地创建其左子树和右子树,最终返回当前结点。
代码如下:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def build_tree(preorder):
n = len(preorder)
if n == 0:
return None
root = TreeNode(val=preorder[0])
if n == 1:
return root
left_preorder = []
right_preorder = []
i = 1
while i < n:
if i % 2 == 1:
left_preorder.append(preorder[i])
else:
right_preorder.append(preorder[i])
i += 1
root.left = build_tree(left_preorder)
root.right = build_tree(right_preorder)
return root
```
接下来,我们可以实现先序、中序和后序遍历的递归操作。其中,先序遍历的操作很简单,只需要按照“根左右”的顺序遍历整棵树即可;中序遍历和后序遍历的操作可以根据递归的顺序进行调整。
代码如下:
```python
def preorder_traversal(root):
if root is None:
return []
res = [root.val]
res += preorder_traversal(root.left)
res += preorder_traversal(root.right)
return res
def inorder_traversal(root):
if root is None:
return []
res = inorder_traversal(root.left)
res += [root.val]
res += inorder_traversal(root.right)
return res
def postorder_traversal(root):
if root is None:
return []
res = postorder_traversal(root.left)
res += postorder_traversal(root.right)
res += [root.val]
return res
```
此外,我们还可以实现中序遍历的非递归操作。具体来说,我们可以使用一个栈来模拟递归的过程。对于当前结点,如果其左子树非空,则将其入栈,并继续遍历左子树;否则,输出当前结点的值,并遍历其右子树。当栈为空时,遍历结束。
代码如下:
```python
def inorder_traversal_iter(root):
res = []
stack = []
while root is not None or len(stack) > 0:
while root is not None:
stack.append(root)
root = root.left
if len(stack) > 0:
node = stack.pop()
res.append(node.val)
root = node.right
return res
```
最后,我们可以求出树的高度、叶子结点个数和结点总数。其中,树的高度可以通过递归地计算左子树和右子树的高度,然后取其较大值并加一得到;叶子结点个数可以通过递归地计算左子树和右子树的叶子结点个数,然后相加得到;结点总数可以通过递归地计算左子树和右子树的结点总数,然后加一得到。
代码如下:
```python
def tree_height(root):
if root is None:
return 0
left_height = tree_height(root.left)
right_height = tree_height(root.right)
return max(left_height, right_height) + 1
def leaf_node_count(root):
if root is None:
return 0
if root.left is None and root.right is None:
return 1
return leaf_node_count(root.left) + leaf_node_count(root.right)
def node_count(root):
if root is None:
return 0
return node_count(root.left) + node_count(root.right) + 1
```
综上所述,我们可以通过以上代码实现对二叉树的各种操作。
阅读全文