算法:输入字符序列,建立二叉树;按先序、中序、后序遍历二叉树(三种递归算法和中序遍历的非递归算法); 选作内容: 求二叉树的高度和结点的个数。
时间: 2024-05-14 15:16:06 浏览: 26
以下是 Python 代码实现:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def build_tree(preorder, inorder):
if not inorder:
return None
root_val = preorder.pop(0)
root = TreeNode(root_val)
inorder_index = inorder.index(root_val)
root.left = build_tree(preorder, inorder[:inorder_index])
root.right = build_tree(preorder, inorder[inorder_index+1:])
return root
def preorder_traversal(root):
if not root:
return []
return [root.val] + preorder_traversal(root.left) + preorder_traversal(root.right)
def inorder_traversal(root):
if not root:
return []
return inorder_traversal(root.left) + [root.val] + inorder_traversal(root.right)
def postorder_traversal(root):
if not root:
return []
return postorder_traversal(root.left) + postorder_traversal(root.right) + [root.val]
def iterative_inorder_traversal(root):
stack = []
result = []
while root or stack:
while root:
stack.append(root)
root = root.left
root = stack.pop()
result.append(root.val)
root = root.right
return result
def get_height(root):
if not root:
return 0
return max(get_height(root.left), get_height(root.right)) + 1
def get_node_count(root):
if not root:
return 0
return 1 + get_node_count(root.left) + get_node_count(root.right)
```
其中,`build_tree` 函数接受先序遍历序列和中序遍历序列,返回创建的二叉树的根节点。`preorder_traversal`、`inorder_traversal` 和 `postorder_traversal` 分别实现了先序、中序和后序遍历的递归算法。`iterative_inorder_traversal` 实现了中序遍历的非递归算法,使用栈来模拟递归过程。`get_height` 和 `get_node_count` 分别返回二叉树的高度和节点个数。
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)