树的认识

2021-06-28

树的认识

每种数据结构都有自己特定的应用场景.但是树确实也综合了一些的数据结构的优点（当然优点不足以盖过其他数据结构，比如效率一般情况下没有哈希表高）.并且也弥补了一些数据结构的缺点。而且为了模拟某些场景，我们使用树结构会更加方便。因为树结构是非线性的，可以表示一对多的关系，比如文件的目录结构

树结构的术语
1、节点的度(Degree): 节点的子树个数
2、树的度：树的所有结点中最大的度数
3、叶节点(Leaf)：度为0的节点(也称为叶子节点)
4、父节点(Parent): 有子树的节点是其子树的根节点的父节点
5、子节点(Child): 若A节点是B节点的父节点，则称B节点是A节点的子节点；子节点也称为孩子节点
6、兄弟节点(Sibling): 具有同一父节点的各节点彼此是兄弟节点
7、路径和路径长度: 从节点n1到nk的路径为一个节点序列n1, n2, … , nk, ni 是 ni+1的父节点.路径所包含边的个数为路径的长度
8、节点的层次：节点的层次(Level)：规定根节点在1层，其他任一节点的层数是其父节点的层数加1
9、树的深度(Depth): 树中所有节点中的最大层次是这个树的深度

树结构的表示方式：儿子兄弟表示法.任何一棵树都可以用二叉树模拟出来

二叉树的认识

如果树种每个节点最多只能有两个子节点，这样的树就称为”二叉树”
二叉树的重要性，不仅仅是因为简单，也因为几乎上所有的树都可以表示成二叉树的形式

二叉树的基本性质

1、每个节点的度最多为2
2、度为0的节点比度为2的节点多一个
证明：设度为0的节点个数为n0,度为1的节点个数为n1,度为2的节点个数为n2。那么总的节点个数为n0+n1+n2,而总的边数等于0*n0+1*n1+2*n2,又总边数等于总节点数-1，那么就可以得出0*n0+1*n1+2*n2=n0+n1+n2-1,可以推导出n0-1=n2

遍历

根据根节点被访问的时机，分为前序遍历(根、左子树、右子树)、中序遍历(左子树、根、右子树)、后序遍历(左子树、右子树、根)

特殊的二叉树

1、完全二叉树(complete binary tree)
2、满二叉树(full binary tree)-指所有节点的度都是0或2的二叉树(即没有度为1的节点)
3、完美二叉树(perfect binary tree)

学习二叉树的作用

1、二叉树是理解高级数据结构的基础

1、完全二叉树-堆、优先队列
2、多叉树/森林-字典树、AC自动机、并查集
3、二叉排序树(BST,Binary Search Tree)-AVL树、2-3树、红黑树、B树、B+树

2、二叉树是练习递归技巧的最佳选择

设计/理解递归程序：
(1)数学归纳法-》结构归纳法(k0正确，我们假设ki->k-+1是正确的)=>联立第一和第二步
(2)赋予递归函数一个明确的意义
(3)思考边界问题
(4)实现递归过程

3、学习二叉树后，可以使用左孩子右兄弟法来节省空间

例子：1                 1
    / | \              /
    2 3 4      =>      2
      /\                \
      5 6                3
                        / \
                        5  4
                         \
                          6

三叉树每个节点存放了3个指针域：左边6个节点->63=18个指针域=>有多少个有效指针域:5条边=>浪费了18-5=13个指针域
二叉树每个节点存放了2个指针域：62=12个指针域=>有多少个有效指针域:5条边=>浪费了12-5=7个指针域
通过以上例子可以得到n个节点的k叉树：一共右nk个指针域，有n-1条边（有效指针域），浪费了nk - n + 1 = n(k-1)+1个指针域

二叉搜索树的认识

二叉搜索时(BST,Binary Search Tree)，也称二叉排序树或二叉查找树.
二叉搜索时是一棵二叉树，可以为空;
如果不为空，满足以下性质:
(1)非空左子树的所有键值小于其根节点的键值
(2)非空右子树的所有键值大于其根节点的键值
(3)左右子树本身也都是二叉搜索树

// 下面哪些是二叉搜索树?
//     18              30              6
//    /  \             / \            / \
//    10  20          15 41          3   9
//    /\   \             /\         /\   /\
//    7 5  22           33 50      1  4  7 10
//    (不是二叉搜索树  是二叉搜索树   \  \  \  \
//    ,10的右子树                    2  5  8  11
//    的键值小于它)                   是二叉搜索树

二叉搜索树的特点：
(1)二叉搜索树的特点就是相对较小的值总是保存在左节点上，相对较大的值总是保存在右节点上
那么利用这个特点，我们可以做什么事情呢？
查找效率非常高，这也是二叉搜索树中，搜索的来源