建立二叉树的二叉链表,实现二叉树的如下操作:1. 建立二叉链表;2. 先序遍历算法;3. 中序序遍历算法;4. 后序遍历算法;5. 求二叉树深度;6. 求二叉树叶子节点数,代码。
时间: 2024-10-27 13:05:52 浏览: 29
erchashubianli.rar_用二叉链表 进行 二叉树 遍历
建立二叉链表通常涉及到创建节点,并将它们连接起来形成树形结构。每个节点包含两个指针,一个指向左子节点,另一个指向右子节点。以下是基本步骤:
1. **建立二叉链表**:
- 创建`Node`类,包含整数值`val`、指向左右子节点的指针`left`和`right`。
- 创建`BinaryTree`类,初始化根节点为空。
```python
class Node:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class BinaryTree:
def __init__(self):
self.root = None
```
2. **先序遍历**:
- 定义递归函数`preorder_traversal(node)`,首先访问当前节点,然后递归左子树和右子树。
```python
def preorder_traversal(root):
if root is not None:
print(root.val) # 访问当前节点
preorder_traversal(root.left)
preorder_traversal(root.right)
```
3. **中序遍历**:
- 也是递归,但是顺序不同:先左子树,再当前节点,最后右子树。
```python
def inorder_traversal(root):
if root is not None:
inorder_traversal(root.left)
print(root.val) # 访问当前节点
inorder_traversal(root.right)
```
4. **后序遍历**:
- 左右子树后,访问当前节点。
```python
def postorder_traversal(root):
if root is not None:
postorder_traversal(root.left)
postorder_traversal(root.right)
print(root.val) # 访问当前节点
```
5. **求二叉树深度**:
- 可以使用递归或者迭代的方法(广度优先搜索)。这里展示递归版本。
```python
def max_depth(root):
if root is None:
return 0
else:
left_height = max_depth(root.left)
right_height = max_depth(root.right)
return max(left_height, right_height) + 1
```
6. **求二叉树叶子节点数**:
- 叶子节点是没有子节点的节点。
```python
def count_leaves(root):
if root is None:
return 0
elif root.left is None and root.right is None: # 判断是否为叶子节点
return 1
else:
return count_leaves(root.left) + count_leaves(root.right)
```
阅读全文