树 一

树 一

文章目录

• • • 1.查找
    • • 二分查找判定树
    • 2. 树(Tree)
    • • 2.1 树的术语
      • 2.2树的表示：儿子兄弟表示法
    • 3. 二叉树（Binary Tree）
    • • 3.1 特殊结构二叉树
      • 3.2 二叉树的性质
      • 3.3 二叉树的存储
      • 3.4二叉树的遍历

分层次组织管理上更有效地操作。

1.查找

• 静态查找：集合中记录固定，只有查找，没有插入和删除
• 动态查找：集合中记录动态变化，除了查找，还可能发生插入和删除

二分查找判定树

如果把二分查找的顺序构造成二分查找判定树。

• 根结点是第一次比较的值，根结点的子节点分别是大于/小于时第二个进行比较的值。
• 判定树上每个节点需要查找的次数是该节点所在的层数
• 查找成功时，查找次数不会超过判定树的深度
• n个节点的判定树深度为 log ⁡ 2 n + 1 \log_2 n + 1 log2​n+1
• ASL(平均查找次数) = ∑ 层数 ∗ 该深度层的结点数 / 总结点数 \sum\text{层数}*\text{该深度层的结点数} / \text{总结点数} ∑层数∗该深度层的结点数/总结点数
• 以树的形式存储数据，方便查找
  • 在树中插入或删除节点时方便，解决动态查找的问题

2. 树(Tree)

• n个节点构成的有限集合,n=0时是空树
• 有一个根结点
• 其余节点分为m个不相交的集合，每个集合又是一棵树，称为原来的“子树”
• 除根结点，每个结点只有一个父节点
• 一颗N个节点的树，有N-1条边

2.1 树的术语

• 节点的度(degree):结点的子树个数
• 树的度：树中所有节点中最大的度数
• 叶节点(leaf)：度为0的节点
• 父节点(parent)：有子树的节点是其子树的根结点的父节点
• 子节点(child)
• 兄弟节点(sibling)
• 路径和路径的长度：路径包含边的个数是路径的长度
• 祖先节点：沿树根到某一节点路径上的所有节点都是这个节点的祖先节点
• 子孙节点：某节点的子树中全部节点
• 节点的层次：根结点层数为1，其它层的层数是父节点层数+1
• 树的深度：树中最大层次

2.2树的表示：儿子兄弟表示法

class Node:def __init__(self,data):self.data = dataself.firstchild = Noneself.nextSibling = None

如下图所示，每个节点由数值、第一个子节点、第一个兄弟节点构成。

3. 二叉树（Binary Tree）

• 度为2的树（子节点最多有两个）
• 由根结点、左子树、右子树构成
• 二叉树的子树有左右顺序之分
• 节点存储的值未必有顺序之分

3.1 特殊结构二叉树

• 斜二叉树(skewed Binary Tree)：只有左子节点或只有右子节点

• 完美二叉树(Perfect Binary Tree)/满二叉树(Full Binary Tree)：除叶节点的所有的节点都有左子节点、右子节点；叶节点都在同一层

• 完全二叉树(complete Binary Tree)：除叶节点的所有的节点都有左子节点、右子节点；要求与完美二叉树从左到右从上到下对节点编号时，同编号的位置一致。允许最下层右边的叶节点有缺失。

3.2 二叉树的性质

• 第i层最大节点数 2 i − 1 2^{i-1} 2i−1
• 深度为h的二叉树，节点数最多有 2 h − 1 2^h-1 2h−1
• 对任何非空二叉树
  • n 0 n_0 n0​表示叶节点的个数
  • n 1 n_1 n1​是度为1（只有一个儿子）的非叶节点个数
  • n 2 n_2 n2​是度为2（有两个儿子）的非叶节点个数
  • 满足关系 n 0 = n 2 + 1 n_0 = n_2 + 1 n0​=n2​+1(由于整颗树的边满足 n 0 + n 1 + n 2 − 1 = n 1 + n 2 ∗ 2 n_0 + n_1 + n_2 -1 = n_1 + n_2*2 n0​+n1​+n2​−1=n1​+n2​∗2)

3.3 二叉树的存储

1. 列表表示
   将树对应为完全二叉树（用None填充空值），按照从上至下、从左到右顺序存储。

• 非根节点的父节点序号是 i / / 2 i//2 i//2
• 节点的左儿子是 2 i 2i 2i,右儿子是 2 i + 1 2i+1 2i+1

2. 链表存储，表示为

class Node:def __init__(self,data):self.data = dataself.left = Noneself.right = None

3.4二叉树的遍历

1. 深度优先

• 先序遍历（中左右）
  访问根结点 -> 先序遍历左子树 -> 先序遍历右子树
  按先序遍历访问上面二叉树的顺序为[1,2,4,5,3,6,7]

def preOrder(root):if root is not None://中print(root.data)//左preOder(root.left)//右preOder(root.right)

用非递归的方式实现

def InOrderStep(root):#空栈stack = list()current = rootdone = Falsewhile !done:if current != None:stack.append(current)current = current.leftelse:if len(stack)> 0:current = stack.pop()print(current.data)current = current.rightelse:done = True

• 中序遍历
  中序遍历左子树 -> 访问根结点 -> 中序遍历右子树
  按中序遍历访问上面二叉树的顺序为[4,2,5,1,6,3,7]

def inOrder(root):if root is not None://左inOrder(root.left)//中print(root.data)//右inOrder(root.right)

• 后序遍历
  后序遍历左子树 ->后序遍历右子树 -> 根结点
  按后序遍历访问上面二叉树的顺序为[4,5,2,6,7,3,1]

def postOrder(root):if root is not None://左postOrder(root.left)//右postOrder(root.right)//中print(root.data)

3. 层次遍历（宽度优先）

from collections import deque
def levelOrder(root):queue = deque()queue.append(root)while len(queue) != 0:temp_node = queue.popleft()print(temp_node.data)if temp_node.left is not None:queue.append(temp_node.left)if temp_node.right is not None:queue.append(temp_node.right)