第七章树和二叉树举例7.1.2基本术语：（1）结点：包含一个数据元素及若干指向其子树的分支（2）结点的度：结点拥有子树数目称为结点的度。如图7-1-1的（b）中，A的度为3；C的度为1；M的度为0。（3）叶子（或终端）结点：度为零的结点。（4）分支结点（或非终端结点）：除根结点外度不为零的结点，也称为内部结点。（5）树的度：树内各结点的度的最大值。（6）孩子：结点的子树的根称为该结点的孩子。如图7-1-1的（b）中，D为A的子树T3的根，则D是A的孩子。（7）双亲：和孩子定义相应地该结点称为孩子的双亲。如图7-1-1的（b）中，A为D的双亲。（8）兄弟：同一个双亲的孩子之间互称兄弟。如图7-1-1的（b）中的H，I，J。（9）祖先：从根到该结点所经过分支上的所有结点。如：M的祖先为A，D，H（10）子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。如图7-1-1的（b）中B的子孙为E，F，K，L（11）层次：从根开始定义为第一层，根的孩子为第二层，依次例推。（12）深度（或高度）：树中结点的最大层次。（13）有序树：将树中结点的各子树看成从左到右是有序的。有序树中最左边的子树的根称第一个孩子，最右边的称为最后一个孩子。（14）无序树：树中结点的各子树没有次序的。（15）森林：是m(m≥0)棵互不相交的树的集合，对树中每个结点而言，其子树的集合即为森林。该树的根结点为：a，分支结点为：b、c、e；叶子结点为d、f、g、h、i、j；该树的度为3，高度为4；第一层有结点：a，第二层有结点：b、c；第三层有结点d、e、f、g、h，第四层有结点：i、j。7.2二叉树7.2.2二叉树的性质(1)性质1：在二叉树的第i层上至多有2i-1个结点（i≥1）。(2)性质2：深度为k的二叉树的最大结点数为2k-1(k≥1)。(3)性质3：对任何一棵二叉树T，如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1（4）一棵深度为k且有2k-1个结点的二叉树称满二叉树。特点：每层上的结点数都为最大结点数，除终端结点外，每个结点都有两棵子树。（5）完全二叉树：如深度为k，有N个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1到N的结点一一对时，称之为完全二叉树。特点：深度为k的完全二叉树，其前k-1层是一棵满二叉树，最后第k层结点都尽量排在靠左的位置上。显然一棵满二叉树一定是完全二叉树，但一棵完全二叉树不一定是满二叉树。（6）完全二叉树的两个特性：性质4：具有n个结点的完全二叉树的深度为└Log2n┘+1。性质5：如果对一棵有n个结点的完全二叉树（其深度为└Log2n┘+1）的结点按顺序编号，则任一结点i(1≤i≤n)有：①若i=1,则结点i是二叉树的根结点，若i>1，则i的双亲结点为结点┗i/2┛;②若2i≤n，则i的左孩子是结点2i，否则无左孩子；③若2i+1≤n，则i的右孩子是结点2i+1,否则无右孩子。7.2.3二叉树的存储结构1.顺序存储结构用一组连续的存储单元存储二叉树的数据元素，按满二叉树的结点顺序编号依次存放二叉树中数据元素。012345T(6)图7-3完全二叉树2.链式存储结构链表的结点至少包含：数据域和左右指针域的链有时还需增一指向双亲的指针域，有两个指针域的链表称为二叉链表，有三个指针域的链表称为三叉链表，如图5-5所示：例7-3分别画出二叉树链式存储结构7.3遍历二叉树2.中序遍历：按中序遍历根结点的左子树；访问根结点；按中序遍历根结点的右子树；3.后序遍历：按后序遍历根结点的左子树；按后序遍历根结点的右子树；访问根结点；4.层次遍历：按照自上而下（从根结点开始），从左到右（同一层）的顺序逐层访问二叉树上的所有结点，这样的遍历方法称为层次遍历。例7．4用三种不同方法遍历图5-9所示的二叉树得：前序遍历结果为：124753689中序遍历结果为：742513869后序遍历结果为：745289631层次遍历结果为：123456789前序遍历的序列为：abdgcefh中序遍历的序列为：dgbaechf后序遍历的序列为：gdbehfca层次遍历的序列为：abcdefgh举例：如图的一棵二叉树：1、写出先序遍历、中序遍历和后序遍历的结果；2、写出结点c的双亲结点、其左右孩子。先序遍历序列：eadcbjfghi中序遍历序列：abcdjefhgi后序遍历序列：bcjdahigfec的双亲结点是e，左孩子为b，没有右孩子。7.3.2恢复二叉树7.4二叉树的转换7.4.2森林转换成二叉树7.4.3二叉树转换成森林7.5二叉树的应用7.6哈夫曼树及其应用例：有三棵二叉树都有