数据结构
第五章 树与二叉树
author:slightwjq
2021年8月12日
树的基本概念
度大于零的节点称为分支节点（非终端节点），反之称为叶子结点，每个节点的分支数称为节点的度。
深度是从根开始自顶向下逐层累加的，高度是从叶子节点开始自底向上逐层累加的。
有序树：各子树顺序不能互换。
二叉树的概念
二叉树是每个节点最多有两棵子树的有序树。
特殊的二叉树
满二叉树：每个节点度数均为2且叶子节点都在最下层。
完全二叉树：
特点：叶子结点只在最下面两层出现
若存在度为1的节点，最多只有一个
若节点数n为奇数，则最大的分支节点n/2只有左孩子。
二叉排序树：左子树关键字<根<右子树关键字
平衡二叉树：左右子树深度差小于等于1
二叉树的性质
叶子节点数等于度为2的节点数加一n(0) = n(2) + 1
第k层至多2^(k-1)个节点
高度为h的二叉树至多2^h - 1个节点
具有n个节点的二叉树高为 log2(n) + 1 向下取整
二叉树的遍历和线索二叉树
先序遍历：根左右
中序遍历：左根右
后序遍历：左右根
每个节点仅访问一次，但会经过两次。
中序与前序（后序，层序）都可以唯一的确定一棵二叉树。
只知道前序和后序不能。
线索二叉树
n个节点的二叉树有n+1个空指针，用空指针存储前驱或后继。
没有左子树，则左指针指向前驱。没有右子树则右指针指向后继。
并增加标识域tag，若tag=0则指向的是孩子，否则指向的是线索。
二叉树是逻辑结构，但线索二叉树是加上线索后的链表结构，所以是物理结构。
中序二叉树
中序二叉树隐含了前驱后继信息，若右标记为0，即有右子树，则右子树中第一个访问的节点即为后继，即右子树最左下的节点。
树、森林
储存结构
双亲表示法：
2*n数组表示 ：data域和parent域
可以很快找到双亲，但求孩子需要完全遍历。
孩子兄弟表示法：
又称二叉树表示法，左子树指向孩子，右子树指向兄弟。
树、森林与二叉树的转换
基于孩子兄弟表示法，森林就是多棵树的根节点互为兄弟。
树的二叉树根节点至多有一个孩子，因为根节点没有兄弟。而森林不同。
二叉树转换为树或森林是唯一的。
树和森林的遍历
树：
先根遍历：对应二叉树的先序序列
后根遍历：对应二叉树的中序遍历
森林：
先序遍历森林：等同依次先根遍历
中序遍历森林：等同依次后序遍历
即森林的先序和中序对应二叉树的先序和中序
树与二叉树的应用
二叉排序树BST
左子树<根<右子树
中序遍历得到递增序列
平衡二叉树AVL
左右子树高度差不超过1，即平衡因子为-1/0/1。
插入
先找到插入路径上离插入节点最近的平衡因子绝对值大于一的节点，再以A为根的子树，在保持特性的额前提下，调整各节点的位置关系，使之重新达到平衡。
四种旋转需要熟练掌握。
平衡二叉树的平均查找长度为log2(n)。
哈夫曼树
WPL带权路径长度最小的为哈夫曼树
哈夫曼树不唯一，其中不存在度为1的节点。
- 本文作者： 魏静崎
- 本文链接： https://slightwjq.github.io/2023/10/17/数据结构-第五章/
- 版权声明： 该文章来源及最终解释权归作者所有