二叉树的建立与遍历
时间: 2023-08-05 22:12:06 浏览: 45
二叉树是一种常见的树形数据结构,它由节点和指向它的左右子树构成。二叉树的每个节点最多有两个子节点,分别称为左子节点和右子节点。
二叉树的建立可以通过递归或非递归方式实现。递归建立二叉树需要考虑终止条件,即当当前节点为空时返回空指针。非递归建立二叉树可以通过栈来实现,将节点入栈并按照先右后左的顺序访问,直到栈为空。
二叉树的遍历包括前序遍历、中序遍历和后序遍历,它们的区别在于节点的访问顺序不同。前序遍历先访问根节点,然后递归访问左子树和右子树;中序遍历先访问左子树,然后访问根节点,最后访问右子树;后序遍历先访问左子树,然后访问右子树,最后访问根节点。
以下是二叉树的建立和遍历的示例代码:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def build_tree(nums):
if not nums:
return None
root = TreeNode(nums[0])
stack = [root]
index = 1
while stack:
node = stack.pop()
if index < len(nums) and nums[index] is not None:
node.left = TreeNode(nums[index])
stack.append(node.left)
index += 1
if index < len(nums) and nums[index] is not None:
node.right = TreeNode(nums[index])
stack.append(node.right)
index += 1
return root
def preorder_traversal(root):
if not root:
return []
res = []
stack = [root]
while stack:
node = stack.pop()
res.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return res
def inorder_traversal(root):
if not root:
return []
res = []
stack = []
node = root
while node or stack:
while node:
stack.append(node)
node = node.left
node = stack.pop()
res.append(node.val)
node = node.right
return res
def postorder_traversal(root):
if not root:
return []
res = []
stack = [root]
while stack:
node = stack.pop()
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
res.append(node.val)
return res[::-1]
```
其中,build_tree函数用于建立二叉树,nums为节点的列表,None表示空节点;preorder_traversal、inorder_traversal和postorder_traversal函数分别实现前序遍历、中序遍历和后序遍历。