【图论】树
Audrey_Hall · · 算法·理论
树
树是一种数据结构，也是一种特殊的图，它是由
之所以把它叫做“树”，是因为它看起来像一棵倒挂着的树，也就是说它是根朝上，叶朝下的。
相关概念
-
树中的每个元素称为节点（node），一棵树中至少有
1 个节点，即根节点； -
每个节点有零个或多个子节点；
-
没有父节点的节点称为根节点，每一个非根节点有且只有一个父节点；
-
除了根节点外，每个子节点可以分为多个不相交的子树；
-
一个节点的子树的个数，称为这个节点的度,度为
0 的节点称为叶节点（leaf）； -
树中各节点的度的最大值称为这棵树的度；
-
树的直径指一棵树中相距最远的两个点之间的距离。
性质
-
树中所有节点均连通；
-
树中不存在环；
-
任意两节点之间只存在一条路径；
-
若树中存在多条直径，则所有直径之间均有公共点；
Proof：假设树中存在两条没有公共点的直径，则我们一定可以用这两条直径的四个端点中的某两个构造出一条更长的直径。
-
树的直径的两个端点一定是叶节点；
Proof：假设存在一个端点不是叶节点，则我们一定可以取那个端点的子节点，代替那个端点做直径的端点，于是就构造出来一条更长的直径。
-
树中距离某一直径端点最远的点，至少有一个是该直径的另一个端点；
Proof：假设不是，则我们一定可以用与之距离最远的点更新直径。
-
对于树中任意一个节点，和与之距离最远的一个点，至少有一个是直径的端点。
二叉树
二叉树是一种特殊的树型结构，它是度数为
每个节点的两个子结点分别称为左儿子和右儿子。
完全二叉树
满二叉树
五种基本形态
性质
-
一棵二叉树的第
i 层最多有2^{i-1} 个节点(i\ge 1) 。 -
一棵深度为
k 的二叉树最多有2^{k-1} 个节点(k\ge 1) 。 -
任意一棵二叉树，如果其叶结点数为
x ，度为2 的结点数为y ，则一定满足：x-y=1 。 -
一棵含有
n 个结点的完全二叉树的深度为\left\lfloor\log_2 n\right\rfloor+1 。 -
一棵含有
n 个结点的完全二叉树，对于任意一个编号为i 的节点，存在一下编号方式：如果
i=1 ，则此结点为根；如果
i>1 ，则其父结点的编号为\left\lfloor\dfrac i2\right\rfloor ，其左孩子的编号为2i ，其右孩子的编号为2i+1 。
树的遍历
用树结构解决问题时，按一定的规律和次序访问树中的各个节点，获得树中全部节点的信息，这种操作叫作树的遍历。
（以下均以二叉树为例）
先序遍历（先根遍历）
先访问根结点，再从左到右按照先序思想遍历各棵子树。
若二叉树为空，则空操作，否则，
访问根结点、先序遍历左子树、先序遍历右子树。
void preorder(tree bt){
//先序遍历递归算法
if(bt){
cout<<bt->data;
preorder(bt->lchild);
preorder(bt->rchild);
}
}中序遍历
若二叉树为空，则空操作，否则，
中序遍历左子树、访问根结点、中序遍历右子树。
void inorder(tree bt){
//中序遍历递归算法
if(bt){
inorder(bt->lchild);
cout<<bt->data;
inorder(bt->rchild);
}
}后序遍历(后根遍历)
先从左到右按照后序思想遍历各棵子树，再访问根结点。
若二叉树为空，则空操作，否则，
后序遍历左子树、后序遍历右子树、访问根结点。
void postorder(tree bt){
//后序递归算法
if(bt){
postorder(bt->lchild);
postorder(bt->rchild);
cout<<bt->data;
}
}层次遍历
按照层次从小到大逐层访问，同一层次按照从左到右的次序访问。
叶结点遍历
即从左到右遍历所有叶节点。
性质
已知先序序列和中序序列可唯一确定一棵二叉树；
已知中序序列和后序序列可唯一确定一棵二叉树；
已知先序序列和后序序列不能唯一确定一棵二叉树。
二叉树操作
普通树转二叉树
由于二叉树是有序的，而且操作和应用更广泛，所以在实际使用时，我们经常把普通树转成二叉树进行操作。
通用法则：“左孩子，右兄弟”
建树
删除一棵二叉树
插入一个结点到排序二叉树中
在排序二叉树中查找一个数
表达式树
关于表达式树，我们可以用先序、中序、后序遍历得到完全不同的遍历结果，如，对于下图的遍历结果如下，它们对应着表达式的3种表示方法。