| 树结构是一种非常重要的非线性结构，该结构中一个数据元素可以有两个或两个以上的直接后继元素，可以用来描述客观世界中广泛存在的层次关系。
|
|
|
|
|
| 树是n（n≥0）个结点的有限集合。当n=0时称为空树。在任一非空树（n>0）中，有且仅有一个称为根的结点；其余结点可分为m（m≥0）个互不相交的有限集T1，T2，…，Tm，其中每个集合又都是一棵树，并且称为根结点的子树。
|
|
|
| 树的定义是递归的，它表明了树本身的固有特性，也就是一棵树由若干棵子树构成，而子树又由更小的子树构成。该定义只给出了树的组成特点，若从数据结构的逻辑关系角度来看，树中元素之间有明显的层次关系。对树中的某个结点，它最多只和上一层的一个结点（即其双亲结点）有直接关系，而与其下一层的多个结点（即其子树结点）有直接关系，如下图所示。通常，凡是分等级的分类方案都可以用具有严格层次关系的树结构来描述。
|
|
|
|
|
|
|
| .双亲、孩子和兄弟：结点的子树的根称为该结点的孩子，相应地，该结点称为其子结点的双亲。具有相同双亲的结点互为兄弟。例如，上图中，结点A是树根，B、C、D是A的孩子结点，B、C、D互为兄弟；B是E、F的双亲，E、F互为兄弟。
|
|
|
| .结点的度：一个结点的子树的个数记为该结点的度。例如，上图中，A的度为3，B的度为2，C的度为0，D的度为1。
|
|
|
| .叶子结点：也称为终端结点，指度为零的结点。例如，上图中，E、F、C、G都是叶子结点。
|
|
|
| .内部结点：度不为零的结点称为分支结点或非终端结点。除根结点之外，分支结点也称为内部结点。例如，上图中，B、D都是内部结点。
|
|
|
| .结点的层次：根为第一层，根的孩子为第二层。以此类推，若某结点在第i层，则其孩子结点就在第i+1层。例如，上图中，A在第1层，B、C、D在第2层，E、F和G在第3层。
|
|
|
| .树的高度：一棵树的最大层次数记为树的高度（或深度）。例如，上图所示树的高度为3。
|
|
|
| .有序（无序）树：若将树中结点的各子树看成是从左到右具有次序的，即不能交换，则称该树为有序树，否则称为无序树。
|
|
|
|
|
|
|
| 二叉树是n（n≥0）个结点的有限集合，它或者是空树（n=0），或者是由一个根结点及两棵不相交的、分别称为左子树和右子树的二叉树所组成。
|
|
|
| 尽管树和二叉树的概念之间有许多联系，但它们有区别。树和二叉树之间最主要的区别是：二叉树中结点的子树要区分左子树和右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树，树中则不区分，如下图所示。另外，二叉树中结点的最大度为2，而树中不限制结点的度数。
|
|
|
|
|
|
|
|
|
| 性质1：二叉树第i层（i≥1）上至多有2i-1个结点。
|
|
|
|
|
| 性质2：深度为k的二叉树至多有2k-1个结点（k≥1）。
|
|
|
由性质1，每一层的结点数都取最大值即得 ，因此性质2得证。
|
|
|
| 性质3：对任何一棵二叉树，若其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。
|
|
|
| 对二叉树中结点的度求总和也就是分支的数目，而二叉树中结点总数恰好比分支数目多1，因此性质3得证。
|
|
|
性质4：具有n个结点的完全二叉树的深度为 。
|
|
|
| 若深度为k的二叉树有2k-1个结点，则称其为满二叉树。可以对满二叉树中的结点进行连续编号，约定编号从根结点起，自上而下、自左至右依次进行。即根结点的编号为1，其左孩子结点编号为2，右孩子结点编号为3，以此类推，编号为i的结点的左孩子编号为2i、右孩子编号为2i+1。
|
|
|
| 当深度为k、有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应时，称之为完全二叉树。高度为3的满二叉树和完全二叉树如下图（a）~（d）所示，显然，满二叉树也是完全二叉树。
|
|
|
|
|
|
|
| 在一个高度为h的完全二叉树中，除了第h层（即最后一层），其余各层都是满的。在第h层上的结点必须从左到右依次放置，不能留空。下图所示的高度为3的二叉树都不是完全二叉树，其中，（a）中4号结点、（b）中5号结点、（c）中6号结点的左边有空结点。
|
|
|
|
|
|
|
显然，具有n个结点的完全二叉树的高度为 。
|
|
|
|
|
|
|
| 用一组地址连续的存储单元存储二叉树中的结点，必须把结点排成一个适当的线性序列，并且结点在这个序列中的相互位置能反映出结点之间的逻辑关系。对于深度为k的完全二叉树，除第k层外，其余各层中含有最大的结点数，即每一层的结点数恰为其上一层结点数的两倍，由此从一个结点的编号可推知其双亲、左孩子和右孩子的编号。
|
|
|
|
|
.若i=1，则该结点为根结点，无双亲；若i>1，则该结点的双亲结点为 。
|
|
|
| .若2i≤n，则该结点的左孩子编号为2i，否则无左孩子。
|
|
|
| .若2i+1≤n，则该结点的右孩子编号为2i+1，否则无右孩子。
|
|
|
|
|
|
|
|
|
| 显然，顺序存储结构对完全二叉树而言既简单又节省空间，而对于一般二叉树则不适用。因为在顺序存储结构中，以结点在存储单元中的位置来表示结点之间的关系，那么对于一般的二叉树来说，也必须按照完全二叉树的形式存储，也就是要添上一些实际并不存在的“虚结点”，这将造成空间的浪费，如上图（b）所示。
|
|
|
| 在最坏的情况下，一个深度为h且只有h个结点的二叉树（单枝树）却需要2h-1个存储单元。
|
|
|
|
|
| 由于二叉树中结点包含有数据元素、左子树根、右子树根及双亲等信息，因此可以用三叉链表或二叉链表（即一个结点含有三个指针或两个指针）来存储二叉树，链表的头指针指向二叉树的根结点，如下图所示。
|
|
|
|
|
|
|
| 设结点中的数据元素为整型，则二叉链表的结点类型定义如下：
|
|
|
|
|
|
|
| 遍历是按某种策略访问树中的每个结点，且仅访问一次。
|
|
|
| 由于二叉树所具有的递归性质，一棵非空的二叉树可以看作是由根结点、左子树和右子树三部分构成，因此若能依次遍历这三个部分的信息，也就遍历了整棵二叉树。按照遍历左子树要在遍历右子树之前进行的约定，依据访问根结点位置的不同，可得到二叉树的前序、中序和后序三种遍历方法。
|
|
|
| 中序遍历二叉树的操作定义如下。若二叉树为空，则进行空操作。否则：
|
|
|
|
|
|
|
|
|
|
|
|
|
| 实际上，将中序遍历算法中对根结点的访问操作放在左子树的遍历之前或右子树的遍历之后，就分别得到先序遍历和后序遍历算法。遍历二叉树的过程实质上是按一定规则，将树中的结点排成一个线性序列的过程。
|
|
|
| 遍历二叉树的基本操作就是访问结点，不论按照哪种次序遍历，对含有n个结点的二叉树，遍历算法的时间复杂度都为O（n）。因为在遍历的过程中，每进行一次递归调用，都是将函数的“活动记录”压入栈中，因此，栈的容量恰为树的高度。在最坏情况下，二叉树是有n个结点且深度为n的单枝树，遍历算法的空间复杂度也为O（n）。
|
|
|
| 设二叉树的根结点所在层数为1，二叉树的层序遍历就是从树的根结点出发，首先访问第1层的树根结点，然后从左到右依次访问第二层上的结点，其次是第三层上的结点，以此类推，自上而下、自左至右逐层访问树中各层结点的过程就是层序遍历。
|
|
|
|
|
| 最优二叉树又称为哈夫曼树，是一类带权路径长度最短的树。
|
|
|
| 从树中一个结点到另一个结点之间的通路称为结点间的路径，该通路上分支数目称为路径长度。树的路径长度是从树根到每一个叶子之间的路径长度之和。结点的带权路径长度为从该结点到树根之间的路径长度与该结点权的乘积。
|
|
|
| 树的带权路径长度为树中所有叶子结点的带权路径长度之和，记为：
|
|
|
|
|
| 其中，n为带权叶子结点数目，wk为叶子结点的权值，lk为叶子结点到根结点的路径长度。
|
|
|
| 最优二叉树是指权值为w1，w2，…，wn的n个叶子结点的二叉树中带权路径长度最小的二叉树。例如，在下图中所示的具有4个叶子结点的二叉树中，以下图（b）所示二叉树的带权路径长度最小。
|
|
|
|
|
|
|
|
|
| （1）根据给定的n个权值｛w1，w2，…，wn｝构成n棵二叉树的集合F=｛T1，T2，…，Tn｝，其中每棵树Ti中只有一个带权为wi的根结点，其左右子树均空。
|
|
|
| （2）在F中选取两棵根结点的权值最小的树作为左右子树，构造一棵新的二叉树，置新构造二叉树的根结点的权值为其左、右子树根结点的权值之和。
|
|
|
| （3）从F中删除这两棵树，同时将新得到的二叉树加入到F中。
|
|
|
| 重复（2）、（3）步，直到F中只含一棵树时为止，这棵树便是最优二叉树（哈夫曼树）。
|
|
|
| 最优二叉树的一个应用是对字符集中的字符进行编码和译码。
|
|
|
| 对给定的字符集D=｛d1，d2，…，dn｝及权值集合W=｛w1，w2，…，wn｝，构造其哈夫曼编码的方法为：以d1，d2，…，dn作为叶子结点，w1，w2，…，wn作为对应叶子结点的权值，构造出一棵最优二叉树，然后将树中每个结点的左分支标上0，右分支标上1，则每个叶子结点代表的字符的编码就是从根到叶子的路径上的0、1字符组成的串。
|
|
|
| 例如，设有字符集｛a，b，c，d，e｝及对应的权值集合｛0.30，0.25，0.15，0.22，0.08｝，按照构造最优二叉树的哈夫曼方法：先取字符c和e所对应的结点构造一棵二叉树（根结点的权值为c和e的权值之和），然后与d对应的结点分别作为左、右子树构造二叉树，之后选a和b所对应的结点作为左、右子树构造二叉树，最后得到的最优二叉树（哈夫曼树）如下图所示。其中，字符a的编码为00，字符b、c、d、e的编码分别为01、100、11、101。译码时就从树根开始，若编码序列中当前编码为0，则进入当前结点的左子树，为1则进入右子树，到达叶子时一个字符就翻译出来了，然后再从树根开始重复上述过程，直到编码序列结束。例如，若编码序列101110000100对应的字符编码采用下图所示的树进行构造，则可翻译出字符序列"edaac"。
|
|
|
|
|
|
|
|
|
| 二叉查找树又称为二叉排序树，它或者是一棵空树，或者是具有如下性质的二叉树。
|
|
|
| （1）若它的左子树非空，则左子树上所有结点的关键码值均小于根结点的关键码值；
|
|
|
| （2）若它的右子树非空，则右子树上所有结点的关键码值均大于根结点的关键码值；
|
|
|
|
|
| 一棵二叉查找树如下图（a）所示。下图（b）所示的二叉树不是二叉查找树，因为46比54小，它应该在根结点54的左子树上。
|
|
|
|
|
|
|
| 从二叉查找树的定义可知，对二叉查找树进行中序遍历，可得到一个关键码递增有序的结点序列。
|
|
|
