二叉树的建立和遍历代码以及注释
时间: 2023-11-05 13:26:15 浏览: 93
当然,我可以为你提供二叉树的建立和遍历代码以及注释。以下是示例代码:
```python
# 定义二叉树节点类
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 二叉树建立
def buildTree(preorder, inorder):
# 利用前序遍历和中序遍历序列构造二叉树
if not preorder or not inorder:
return None
root = TreeNode(preorder[0])
idx = inorder.index(preorder[0])
root.left = buildTree(preorder[1:idx+1], inorder[:idx])
root.right = buildTree(preorder[idx+1:], inorder[idx+1:])
return root
# 二叉树前序遍历
def preorderTraversal(root):
res = []
if root:
res.append(root.val)
res += preorderTraversal(root.left)
res += preorderTraversal(root.right)
return res
# 二叉树中序遍历
def inorderTraversal(root):
res = []
if root:
res += inorderTraversal(root.left)
res.append(root.val)
res += inorderTraversal(root.right)
return res
# 二叉树后序遍历
def postorderTraversal(root):
res = []
if root:
res += postorderTraversal(root.left)
res += postorderTraversal(root.right)
res.append(root.val)
return res
```
注释说明:
1. `TreeNode` 类表示二叉树的节点,包括节点值 `val`,左子树 `left` 和右子树 `right`。
2. `buildTree` 函数利用前序遍历序列和中序遍历序列构造二叉树,返回根节点。
3. `preorderTraversal` 函数实现二叉树的前序遍历,返回遍历结果。
4. `inorderTraversal` 函数实现二叉树的中序遍历,返回遍历结果。
5. `postorderTraversal` 函数实现二叉树的后序遍历,返回遍历结果。
以上代码适用于 Python 语言,其他语言的实现方式类似。希望能够对你有所帮助!
阅读全文