第6章树主要内容6.1树的定义和基本术语6.2树的链式存储结构6.3树的顺序存储结构6.4K叉树6.5树知识点总结6.1.1树和森林6.1.2森林与二叉树的等价转换6.1.3树的抽象数据类型6.1.4树的周游6.1树的定义和基本术语6.1.1树和森林树(tree)是包括n个结点的有限集合T（n≥1），使得：有且仅有一个特定的称为根(root)的结点。除根以外的其它结点被分成m个(m≥0)不相交的有限集合T1，T2，…，Tm，而每一个集合又都是树。其中树T1，T2，…，Tm称作这个根的子树(subtree)。6.1.1树和森林图6.1树形表示法ABCDEFGHIJKL6.1.1树和森林树的逻辑结构可以这样描述：树是包含n个结点的有穷集合K(n>0)，且在K上定义了一个满足以下条件的二元关系R={r}：有且仅有一个结点k0K∈，它对于关系r来说没有前驱。结点k0称作树的根。除结点k0外，K中的每个结点对于关系r来说都有且仅有一个前驱。除结点k0外的任何结点kK∈，都存在一个结点序列k0，k1，…，ks，使得k0就是树根，且ks=k，其中有序对
R∈（1≤i≤s）。这样的结点序列称为从根k0到结点k的一条路径。树形结构的各种表示法树的逻辑结构是：结点集合K={A，B，C，D，E，F，G，H，I，J}K上的关系N={，，，，，，，，}树结构中的概念在一棵树中，若存在结点k指向结点k’的连线，则称k是k’的父结点，而k’则是k的子结点，有向连线称作边。同一个父结点的子结点之间互称兄弟。树中没有父结点的结点称为根。没有子结点的结点称为树叶。结点的子树数目称为结点的度，树的度是树中各结点度的最大值，二叉树的度是2。树结构中的概念若树中存在结点序列k0，k1，…，ks，使得，，…，都是树中的边，则称从结点k0到结点ks存在一条路径。若有一条由k到达ks的路径，则称k是ks的祖先，ks是k的子孙。结点的层数同样由树根开始定义的，根结点为第0层，非根结点的层数是其父结点的层数加1。树结构中的概念有序树：计算机的存储是有序的，为方便计算机处理，往往把子结点按从左到右的次序顺序编号，即把树作为有序树(orderedtree)看待。度为2的有序树并不是二叉树，因为在第一子结点被删除后，第二子结点自然顶替成为第一子结点。因此，度为2并且严格区分左右两个子结点的有序树才是二叉树。森林与树森林(forest)是零棵或多棵不相交的树的集合（通常是有序集合）。对于树中的每个结点，其子树组成的集合就是森林；而加入一个结点作为根，森林就可以转化成一棵树了。树形结构的各种表示法树形结构在客观世界中是大量存在的，有多种逻辑表示方法,如1)树形表示法2)凹入表示法3)文氏图表示法4)嵌套括号表示法。(1)树型表示法。这是树的最基本的表示,使用一棵倒置的树表示树结构,非常直观和形象。ACGJBEDFIHMKL树形表示法树的逻辑表示法(2)文氏图表示法。使用集合以及集合的包含关系描述树结构。HLDKIMCGJEBF文氏图表示法A树的逻辑表示法(3)凹入表示法。使用线段的伸缩描述树结构。FCABDEGJHIKLM凹入表示法树的逻辑表示法(4)括号表示法(广义表表示法)。将树的根结点写在括号的左边,除根结点之外的其余结点写在括号中并用逗号间隔来描述树结构。括号表示法A(B(E,F),C(G(J)),D(H,I(K,L,M)))树的逻辑表示法6.1.2森林与二叉树的等价转换树与二叉树、森林与二叉树之间可以相互转化，而且这种转换是一一对应的。树和森林转化成二叉树后，那么森林或树的相关操作都可以转换成对二叉树的操作。树、森林到二叉树的转换树和森林到二叉树的转换过程可用连线、切线、旋转“三步曲”来说明：连线：将兄弟结点用线连接起来。切线：保留父结点与其第一个子结点的连线，将父结点到其它子结点的连线切掉。旋转：以根为轴，平面向下顺时针方向旋转45度。旋转只是为了调整画面，使得转化后的二叉树看起来比较规整。加边删边调整树转换为二叉树将树转换为二叉树的形式表示。令结点的两个链域分别指向该结点的第一个儿子和右边的兄弟。RBACDEFHGK∧∧∧RADBE∧C∧F∧G∧∧H∧K∧∧森林转换为二叉树的方法如下：（1）将...
