05树
05树
1. 二叉树
1.1 性质
证明
已知叶子结点数为，度为 2 的结点数为，设度为 1 的结点数为，显然注意到除了根结点以外，其他结点都有一个分支进入，这些分支是由度为 1 或 2 的结点引出，因此联合即有
由题意，因此，由于是完全二叉树，，因此最多
考虑，由递推有解为若记次序，则为。
1.2 存储结构
顺序存储
tree = [None] * (1 << h - 1)
root = 1
def left_child(i):
return 2 * i + 1
def right_child(i):
return 2 * i + 2
def parent(i):
return (i - 1) // 2
链式存储
@dataclass
class Node:
val: Any
left: "Node" = None
right: "Node" = None
或者使用字典
tree = {}
tree[node] = [left, right]
1.3 二叉树遍历
先序遍历
递归实现：
def preorder(node):
if not node:
return
print(node.val)
preorder(node.left)
preorder(node.right)
栈实现：
def preorder(root):
if not root:
return
stack = [root]
while stack:
node = stack.pop()
print(stack.pop())
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
中序遍历
递归实现：
def inorder(node):
if not node:
return
inorder(node.left)
print(node.val)
inorder(node.right)
栈实现：
def go_left(curr, stack):
while curr:
stack.append(curr)
curr = curr.left
def inorder(root):
if not root:
return
curr = root
while curr or stack:
go_left(curr, stack)
node = stack.pop()
print(node.val)
curr = node.right
后序遍历
递归实现：
def postorder(node):
if not node:
return
postorder(node.left)
postorder(node.right)
print(node.val)
- 中序=后序无右孩
- 前序=中序无左孩
- 前序=后序只有根结点或没有
栈实现：
模拟前序遍历，左右根->根右左
def postorder(root):
stack = [root]
result = []
while stack:
node = stack.pop()
result.append(node)
if l := node.left:
stack.append(l)
if r := node.right:
stack.append(r)
return result[::-1]
- 前序遍历：从根开始，先记录当前结点，然后向左走直到尽头，回退时访问右子树。
- 中序遍历：从左子树走到底，回退时访问结点，再走右子树。
- 后序遍历：从左子树走到底，回退时访问右子树，最后访问根结点。
2. 线索二叉树
利用空链域记录前驱和后继：
@dataclass
class Node:
val: Any
left: "Node" = None
right: "Node" = None
left_thread: bool
right_thread: bool
在遍历过程中记录线索：
pre = None
def set_thread(node):
global pre
if node.left is None:
node.left_thread = True
node.left = pre
if pre is not None and pre.right is None:
pre.right_thread = True
pre.right = node
pre = node
2.1 中序遍历
def inorder(node):
if node is None:
return
if not node.left_thread:
inorder(node.left)
set_thread(node)
if not node.right_thread:
inorder(node.right)
- 前驱结点：
- 如果结点的 左子树 不为空，则前驱结点是 左子树中最右的结点（即左子树的最大值）。
- 如果结点的 左子树 为空，则前驱结点是 通过线索指针获取的，即 左孩。
- 后继结点：
- 如果结点的 右子树 不为空，则后继结点是 右子树中最左的结点（即右子树的最小值）。
- 如果结点的 右子树 为空，则后继结点是 通过线索指针获取的，即 右孩。
2.2 前序遍历
def preorder(node):
if node is None:
return
set_thread(node)
if not node.left_thread:
inorder(node.left)
if not node.right_thread:
inorder(node.right)
- 前驱结点：
- 前序遍历难以找到前驱
- 后继结点：
- 如果结点的 左子树 不为空，则后继结点是 左孩。
- 如果结点的 左子树 为空，则后继结点是 通过线索指针获取的 或者 只有右孩，因此都是右孩。
@property
def succ(self):
if not self.left_thread:
return self.left
return self.right
2.3 后序遍历
def postorder(node):
if node is None:
return
if not node.left_thread:
inorder(node.left)
if not node.right_thread:
inorder(node.right)
set_thread(node)
- 前驱结点：
- 如果结点的 右子树 不为空，则前驱结点是 右孩。
- 如果结点的 右子树 为空，则前驱结点是 通过线索指针获取的 或者 只有左孩，因此都是左孩。
- 后继结点：
- 后序遍历难以找到后继。
@property
def pred(self):
if not self.right_thread:
return self.right
return self.left
3. 树
3.1 树的存储结构
- 双亲表示法：以一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲结点在表中的位置。
- 孩子链表表示法：以单链表将所有的双亲相同的孩子结点链接在一起，并将该链表的头指针和双亲构成树中的一个结点。
- 孩子兄弟表示法：以二叉链表作树的存储结构，表中结点的两个链域分别指向该结点的“最左“孩子结点和下一个兄弟结点。
3.2 遍历
- 先根遍历：若树不空，则先访问根结点，然后依次先根遍历各棵子树。
- 后根遍历：若树不空，则先依次后根遍历各棵子树，然后访问根结点。
- 层次遍历：若树不空，则自上而下自左至右访问树中每个结点。
4. 森林
4.1 森林与二叉树的转换
- 增加一个根结点,作为原森林中各树根结点的父结点
- 将新树转换成二叉树
- 删除二叉树的根结点
4.2 遍历
- 先序遍历：依次从左至右对森林中的每一棵树进行先根遍历。
- 中序遍历：依次从左至右对森林中的每一棵树进行后根遍历。
5. 赫夫曼树
- 根据给定的个权值构成棵二叉树的集合，其中每棵二叉树中只有一个权值为的根结点。
- 在 中选取两棵根结点权值最小的树作为左、右子树构造一棵新的二叉树，且置新二叉树的根结点的权值为其左、右子树根结点的权值之和。
- 在 中删除这两棵树，同时将新得到的二叉树加入集合 中。
- 重复 (2) 和 (3) ，直到 中只含一棵树为止。
def build_huffman_tree(weights):
heap = [Node(weight) for weight in weights]
heapq.heapify(heap)
while len(heap) > 1:
left = heapq.heappop(heap)
right = heapq.heappop(heap)
merged_node = Node(left.weight + right.weight)
merged_node.left = left
merged_node.right = right
heapq.heappush(heap, merged_node)
return heap[0]
时间复杂度为 ，空间复杂度为 。
证明
设叶子结点为，非叶子结点为，总边数为，显然有由于赫夫曼树是满叉树，因此此时联立有即故证毕。