树

简介

• 每个节点有零个或多个子节点
• 没有父节点的节点称为根节点
• 每一个非根节点有且只有一个父节点
• 除了根节点外，每个子节点可以分为多个不相交的子树；

名词

节点的度

一个节点含有的子树的个数

叶节点（或终端节点）

度为0的节点

分支节点（或非终端节点）

度不为0的节点

双亲节点（或父节点）

若一个节点含有子节点，则该节点为其子节点的父节点

孩子节点（或子节点）

兄弟节点

具有相同父节点的节点

树的度

一棵树中，最大的节点的度

节点的层次

根节点为1，以此类推

高度（树、节点）

从根（高度为1）开始向叶子节点数，即从上往下数

深度（树、节点）

从叶子节点往该j节点数，即从下往上数

堂兄弟节点

父节点在同一层的节点

节点的祖先

从根到该节点所经分支上的所有节点

子孙

以某节点为根的子树中任一节点

森林

有m（m>0）棵互不相交的树的集合

分类

无序树（自由树）

树中任意节点的子节点之间没有顺序关系

有序树

与无序树相对应

二叉树

每个节点最多含有两个子树的树，且左右子树顺序不能颠倒

完全二叉树

• 叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树；
• 对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树

满二叉树

除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树；
（如果一棵二叉树的结点要么是叶子结点，要么它有两个孩子结点，这样的树就是满二叉树。）

霍夫曼树（最优二叉树）

带权路径最短的二叉树

平衡二叉树

它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树

二叉树性质

1. 在非空二叉树中，第i层的结点总数不超过$2^{i-1}, i>=1$
2. 深度为h的二叉树节点个数最少有h个，最多$2^h-1, h>=1$
3. 对于任意一棵二叉树，如果其叶结点数为$N_0$，而度数为2的结点总数为$N_2$，则$N_0=N_2+1$；
4. 具有n个结点的完全二叉树的深度为$log_2^{n+1}$
5. 有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：
   1. 若I为结点编号则 如果$I>1$，则其父结点的编号为$I/2$;
   2. 如果$2*I<=N$，则其左儿子（即左子树的根结点）的编号为$2*I$；若$2*I>N$，则无左儿子；
   3. 如果$2*I+1<=N$，则其右儿子的结点编号为$2*I+1$；若$2*I+1>N$，则无右儿子。
6. 给定$N$个节点，能构成$h(N)$种不同的二叉树。$h(N)$为卡特兰数的第N项，则$h(n)=C(2*n,n)/(n+1)$;
7. 设有$i$个枝点，$I$为所有枝点的道路长度总和，$J$为叶的道路长度总和, 则$J=I+2i[4]$；

遍历

先序遍历

首先访问根，再先序遍历左（右）子树，最后先序遍历右（左）子树

中序遍历

首先中序遍历左（右）子树，再访问根，最后中序遍历右（左）子树

后序遍历

首先后序遍历左（右）子树，再后序遍历右（左）子树，最后访问根