树type
status
date
slug
summary
tags
category
icon
password
Property
树
树是一种非线性的数据结构，是由个有限结点组成一个具有层次关系的集合。
有一个特殊的结点，称为根结点，根节点没有前驱结点。除根节点外，其余结点被分成 个互不相交的集合 其中每一个集合 又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继。因此，树是递归定义的。
相关名词解释
- 节点的度：一个节点的子树 (子节点) 个数称为该节点的度，A的度为3
- 叶节点 (终端节点)：度为0的节点称为叶节点，J、F、K、L、H、I 节点为叶节点
- 非终端节点 (分支节点)：度不为0的节点，B、C、D、E、G 节点为分支节点
- 双亲节点 (父节点)：若一个节点有子节点，则这个节点称为其子节点的父节点，A是B的父节点
- 孩子节点 (子节点)：一个节点含有的子树的根节点称为该节点的子节点，B是A的孩子节点
- 兄弟节点：具有相同父节点的节点互称为兄弟节点，B、C、D是兄弟节点
- 树的度：一棵树中，最大的节点的度称为树的度，上图树的度为3
- 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推
- 树的高度 (深度)：树中节点的最大层次，上图树的高度为4，空树的高度是0，只有根节点的树高度为1
- 堂兄弟节点：双亲在同一层的节点互为堂兄弟，F、G互为堂兄弟节点
- 节点的祖先：从根到该节点所经分支上的所有节点，A是所有节点的祖先，K的祖先是A、C、G
- 子孙：以某节点为根的子树中任一节点都称为该节点的子孙，所有节点都是A的子孙
- 森林：由棵互不相交的树的集合称为森林（并查集就是一个森林）
树的表示
树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。其中最常用的孩子兄弟表示法：
二叉树
一个二叉树是结点的一个有限结合，该集合：由一个根节点加上两棵别称为左子树和右子树的二叉树组成，或者为空。
- 二叉树不存在度大于2的结点
- 二叉树的子树有左右之分，是有序树，次序不能颠倒
对于任意的二叉树都是由以下几种情况复合而成的：
特殊的二叉树
满二叉树 Full Binary Tree：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为，且结点总数是 ，则它就是满二叉树。
满足下列性质：
一颗树深度为，最大层数为，深度与最大层数相同，
叶子节点数（最后一层）为，第层的节点数是：，总节点数是：，且总节点数一定是奇数。
完全二叉树 Complete Binary Tree：完全二叉树是效率很高的数据结构。
设二叉树的深度为，除第层外，其它各层 的结点数都达到最大个数，第层所有的结点都连续集中在最左边，这就是完全二叉树。
一个深度为的有个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，当且仅当其每一个结点都与深度为的满二叉树中编号从1 至的结点一一对应时称之为完全二叉树。注：满二叉树是一种特殊的完全二叉树。
除最后一层外都是满的，最后一层不一定满，但最后一层从左到右必须是连续的。
深度为的完全二叉树的节点个数最多为，最少为 （前层节点个数总和+1，因为第层至少有一个），所以节点个数范围是：
平衡二叉树Balanced Binary Tree：又被称为AVL树，它是一颗空树或左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。
二叉搜索树Binary Search Tree：
又称二叉查找树、二叉排序树（Binary Sort Tree）。它是一颗空树或是满足下列性质的二叉树：
- 若左子树不空，则左子树上所有节点的值均小于或等于它的根节点的值
- 若右子树不空，则右子树上所有节点的值均大于或等于它的根节点的值
- 左、右子树也分别为二叉排序树
红黑树Red Black Tree：
每个节点都带有颜色属性（颜色为红色或黑色）的自平衡二叉查找树，满足下列性质：
- 根节点是黑色，节点是红色或黑色，所有叶子节点都是黑色
- 每个红色节点必须有两个黑色的子节点(从每个叶子到根的所有路径上不能有两个连续的红色节点)
- 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点
二叉树的存储结构
顺序存储
使用数组来存储，而数组一般只适合表示满二叉树或完全二叉树，因为不是完全二叉树会有空间的浪费。在实际使用中，只有堆才会使用数组来存储。二叉树的顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。
在数组中用下标来表示树中的父子关系，满足以下关系：
链式存储
二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素间的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来记录该结点左孩子和右孩子所在的链结点的存储地址。链式结构又分为二叉链和三叉链，一般都是二叉链（红黑树等才会用到三叉链）
二叉树的遍历
欲在屏幕上形象地输出链式二叉树是一件困难的事，一般采用输出它的三个线性序列VLR、LVR和LRV的方式。所谓前序、中序和后序遍历，是相对于根结点位置而言的。例如，在中序遍历中，根结点在中间；而前序遍历是根结点在前面，后序遍历是根结点在后面，三种遍历方式一定是先左子树后右子树。
前序（PreOrder）遍历
VLR称为前序（PreOrder）遍历序列，它是按先树根，再左子树，后右子树的次序，输出二叉树的结点值
根 ➜ 左 ➜ 右
中序（InOrder）遍历
LVR称为中序（InOrder）遍历序列，它是按先左子树，再树根，后右子树的次序，输出二叉树的结点值
左 ➜ 根 ➜ 右
在二分搜索树中，中序遍历的顺序符合从小到大（或从大到小）顺序的，要输出排序好的结果使用中序
后序（PostOrder）遍历
LRV称为后序（PostOrder）遍历序列，它是按先左子树，再右子树，后树根的次序，输出二叉树的结点值
左 ➜ 右 ➜ 根
后续遍历的特点是在执行操作时，肯定已经遍历过该节点的左右子节点，适用于进行破坏性操作，比如删除所有节点，比如判断树中是否存在相同子树
BFS（广度优先搜索）和DFS（深度优先搜索）
广度优先搜索
层序遍历，横向访问。当树的高度非常高（非常瘦），使用广度优先节省空间
二叉树的层序遍历（即逐层地，从左到右访问所有节点）
二叉树的锯齿形层序遍历
给二叉树的根节点
root，返回其节点值的 锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。深度优先搜索
纵向，探底到叶子节点
当每个节点的子节点非常多（非常胖），使用深度优先遍历节省空间（访问顺序和入栈顺序相关，想当于先序遍历）
