《第5章树和二叉树--1》由会员分享，可在线阅读，更多相关《第5章树和二叉树--1（55页珍藏版）》请在金锄头文库上搜索。
1、第6章树和二叉树(1) （课后复习版） 主讲：顾为兵作者声明：课件仅限本班教学参考用，不对外发布第六章 树和二叉树目录6.1 树的定义和基本术语6.2 二叉树6.3 遍历二叉树6.4 线索二叉树6.5 树和森林6.6 哈夫曼树及其应用6.1 树的定义和基本术语6.1.1 树的定义6.1.2 树的术语树的定义和基本术语6.1.1 树的定义（P130）v树是n（n0）个结结点的有限集。在任意一棵非空树树中，有且仅仅有一个称为为根的结结点；其余 结结点分为为m（m0）个互不相交的子集，每个子集又是一棵树树，称为为根的子树树。v这这是一个递归递归 的定义义在树树的定义义中又用到了树树的概念。v递归递归
2、 是树树的固有特性。 树的定义和基本术语 树的定义AFEDCBIHGKJ8树根：A8三个互不相交的子集： B，E，F，J C D，G，H，I，K 8每个子集都是满足树的 定义的树，称为A的子树 B子树、C子树、D子树。 8树根A没有直接前驱；其余结点有且仅有一个 直接前驱有，有0个或多个直接后继。树的特征：层次性和分支性树的定义和基本术语 树的定义6.1 树的定义和基本术语6.1.1 树的定义6.1.2 树的术语 树的定义和基本术语 树的定义6.1.2 树的术语8 结点的度：结点的非空子树个数8 树的度：树中各结点度的最大值8 分支结点(非终端结点) ：度0的结点8 叶子结点(终端结点)：度=
3、0的结点8 孩子：结点子树的根称为该结点的孩子8 双亲：孩子的直接前驱结点称为该结点的双亲8 兄弟：同一个双亲的结点互称为兄弟8 子孙：以某结点为根的各个子树上的所有结点称为 该结点的子孙8 祖先：从树根到该结点所经过的所有分支结点称为 该结点的祖先AFEDCBIHGKJ8 堂兄:双亲是兄弟的所有结点互称为堂兄弟8 结点的层次：从树根开始自上而下编 号，树根的层次为1，其余结点的层次为 其双亲的层次18树的深度（高度）：结点层次的最大值8有序树和无序树：若树中所有结点的孩 子都长幼有序，位置不能互换，称为有序 树，否则称为无序树。8森林：m（m0）个树的集合AFEDCBIHGKJTree=(A
4、 ( B( E( J ),F ), C, D( G, H ( K ), I ) ) )树的定义和基本术语 树的定义树的基本运算：初始化空树InitTree( 二叉树可以有5种基本形态： 二叉树不是结点的度都不超过2的有序树。ACIBGFHED二叉树 二叉树的定义三个结点的树有两种不同的形态：三个结点的二叉树有五种不同的形态：二叉树 二叉树的定义c树型结构的共同特征：层次性、分支性c两种完全不同的树型结构：树二叉树二叉树 二叉树的定义二叉树的基本运算：初始化空二叉树InitBiTree( 若X有左孩子，则X左孩子的编号为2i； 若X有右孩子，则X右孩子的编号为2i1； 若i为奇数且i1，则X的左
5、兄弟为i1； 若i为偶数且idata);/访根preorder(bt-lchild);preorder(bt-rchild);若二叉树为空，则空操作； 否则,(1)中序遍历左子树(2)访问根；(3)中序遍历右子树中序遍历的递归定义：(2)(1)(3)二叉树 遍历二叉树void inorder(BiTree bt)if(!bt) return;inorder(bt-lchild);visit(bt-data);/访根inorder(bt-rchild);若二叉树为空，则空操作;否则,(1)后序遍历左子树(2)后序遍历右子树(3)访问根；后序遍历的递归定义：(3)(1)(2)二叉树 遍历二叉树vo
6、id postorder(BiTree bt)if(!bt) return;postorder(bt-lchild);postorder(bt-rchild);visit(bt-data);/访根ACBGEDIFH先序遍历序列：中序遍历序列：后序遍历序列： A B D G E C F H ID G B E A C H IFG D E B I H F C A二叉树的遍历二叉树 遍历二叉树void preorder(BiTree bt) if( !bt ) return;visit(bt-data); preorder(bt-lchild);preorder(bt-rchild);void ino
7、rder(BiTree bt) if( !bt ) return;inorder(bt-lchild);visit(bt-data); inorder(bt-rchild);void postorder(BiTree bt) if( !bt ) return;postorder(bt-lchild);postorder(bt-rchild); visit(bt-data); 现将三个遍历算法中的visit语句去掉，我们发现这三个算法完全一样。这说明三种遍历的路径是一样的，只是访问根的时机不同而已。二叉树 遍历二叉树扩展二叉树：将二叉树中的空指针用一个虚结点表示，这样构成的二叉树称为该二叉树的扩
8、展二叉树。扩展二叉树的虚结点不是原二叉树的一部分，称为外部结点，而原树中结点称为内部结点。ADBE内部结点外部结点二叉树 遍历二叉树ADBC围绕扩展二叉树走一圈，每个内部结点将相遇三次。若每次访问都是在：第一次相遇时进行，构成先序遍历序列ABDC第二次相遇时进行，构成中序遍历序列BDAC第三次相遇时进行，构成后序遍历序列DBCAABDCABDC DBCAvoid InOrder(BiTree bt, void(*visit)(BiTree)/中序遍历的非递归算法InitStack(S);e=BT,Travel; if(BT) Push(S,e);while(!StackEmpty(S)Pop(
9、S,e);if(e.task=Visit) visit(e.ptr);elseif(e.ptr!=NULL)p=e.ptr;e.ptr=p-rchild; e.task=Travel; Push(S,e);e.ptr=p; e.task=Visit; Push(S,e);e.ptr=p-lchild; e.task=Travel; Push(S,e);/if/while /InOrderACIBGFHED后序遍历先序遍历另一种先序遍历的非递归算法：void PreOrder(BiTree bt) if(!bt) return; InitStack(S); push(S, bt); /树根的指针
10、进栈 while(!EmptyStack(S) pop(S, p); while(p) /沿着左链一路向下visit(p-data); /访问if(p-rchild)push(S,p-rchild);/右孩 子进栈p=p-lchild; 二叉树 遍历二叉树ACIBGFHED6.3 遍历二叉树6.3.1 先序、中序和后序遍历6.3.2 算术表达式的二叉树表示6.3.3 二叉树的运算举例6.3.4 按层次遍历二叉树6.3.5 构造二叉链表二叉树 遍历二叉树6.3.2 算术表达式的二叉树表示二目算符右操作数左操作数一目算符右操作数二叉树 算术表达式的二叉树表示-a+b(c-d)-e/fcdb-a-+ef-/先序序列：-+-ab-cd/ef后序序列：a-bcd-+ef/-中序序列：-a+bc-d-e/f波兰式逆波兰式二叉树 算术表达式的二叉树表示*+aa+(b+c)*d-e/(f-g)*h*-b+cde/g-fh 波兰式：+a*-*+bcd/e-fgh逆波兰式：abc+d*efg-/-h*+a+(b+c)*d-e/(f-g)*h二叉树 算术表达式的二叉树表示
