《数据结构第五章幻灯片.ppt》由会员分享，可在线阅读，更多相关《数据结构第五章幻灯片.ppt（67页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构第五章第1页，共67页，编辑于2022年，星期六1.树的基本概念树的基本概念2.二叉树二叉树3.遍历二叉树遍历二叉树4.线索二叉树线索二叉树5.树的应用树的应用特点：非线性结构，一个直接前驱，但可能有多个直特点：非线性结构，一个直接前驱，但可能有多个直接后继。接后继。（一对多或（一对多或1:n1:n）二叉树的定义、性质和存储结构二叉树的运算第2页，共67页，编辑于2022年，星期六l树适于反应层次关系的数据对象的研究。层次树适于反应层次关系的数据对象的研究。层次化的数据之间可能有化的数据之间可能有:祖先祖先后代、上级后代、上级下级、下级、整体整体部分部分等其它类似的关系。等其它类似的关
2、系。学院学院法法学学院院工工商商学学院院信信息息学学院院金金融融学学院院人人文文学学院院会会计计学学院院财财税税学学院院计计算算机机系系信信息息系系统统计计系系图图5.1.1 5.1.1 一棵学院信息的树一棵学院信息的树第3页，共67页，编辑于2022年，星期六5.1.1 5.1.1 树的定义树的定义 由一个或多个由一个或多个(n0)(n0)结点组成的有限集结点组成的有限集合合T T，有且仅有一个结点称为根（有且仅有一个结点称为根（rootroot）当当n1n1时，其余的结点分为时，其余的结点分为m(m0)m(m0)个互个互不相交的有限集合不相交的有限集合T1,T2T1,T2，TmTm。每个集
3、合本身又是棵树，被称作这个根每个集合本身又是棵树，被称作这个根的子树的子树 。树的定义具有递归性，即树的定义具有递归性，即“树中还有树树中还有树”。第4页，共67页，编辑于2022年，星期六一棵树至少包含一个树结点，不存在不一棵树至少包含一个树结点，不存在不含树结点的树；含树结点的树；树中结点存在着层次关系，但同一层上树中结点存在着层次关系，但同一层上的树结点之间是无序的。的树结点之间是无序的。一棵树的每个结点都是某个子树的根。一棵树的每个结点都是某个子树的根。第5页，共67页，编辑于2022年，星期六若干术语若干术语（也称父亲）（也称父亲）即上层的那个结点即上层的那个结点(直接前驱直接前驱)
4、即下层结点的子树的根即下层结点的子树的根(直接后继直接后继)同一双亲下的同层结点（孩子之间互称兄弟）同一双亲下的同层结点（孩子之间互称兄弟）即双亲位于同一层的结点（但并非同一双亲）即双亲位于同一层的结点（但并非同一双亲）即从根到该结点所经分支的所有结点即从根到该结点所经分支的所有结点即该结点下层子树中的任一结点即该结点下层子树中的任一结点ABCGEIDHFJFLK 根根 叶子叶子 森林森林有序树有序树无序树无序树即根结点即根结点(没有前驱没有前驱)即终端结点即终端结点(没有后继没有后继)指指m棵不相交的树的集合棵不相交的树的集合(例例如删除如删除A后的子树个数后的子树个数)双亲双亲孩子孩子兄弟
5、兄弟堂兄弟堂兄弟祖先祖先子孙子孙结点各子树从左至右有序，不能互换（左为第一）结点各子树从左至右有序，不能互换（左为第一）结点各子树可互换位置。结点各子树可互换位置。第6页，共67页，编辑于2022年，星期六即树的数据元素即树的数据元素结点挂接的子树数结点挂接的子树数结点结点结点的度结点的度结点的层次结点的层次终端结点终端结点分支结点分支结点树的度树的度树的深度树的深度(或高度或高度)ABCGEIDHFJFLK从根到该结点的层数（根结点算第一层）从根到该结点的层数（根结点算第一层）即度为即度为0的结点，即叶子的结点，即叶子即度不为即度不为0的结点（也称为内部结点）的结点（也称为内部结点）所有结点
6、度中的最大值（所有结点度中的最大值（Max各结点的度各结点的度）指所有结点中最大的层数（指所有结点中最大的层数（Max各结点的层次各结点的层次）问：右上图中的结点数问：右上图中的结点数 ；树的度；树的度 ；树的深度；树的深度13133 34 4（有几个直接后继就是几度，亦称（有几个直接后继就是几度，亦称“次数次数”）第7页，共67页，编辑于2022年，星期六A AB BC CD DE EF FG GH HI IJ JK KL LM M结点结点A A的度：的度：?结点结点B B的度：的度：?结点结点M M的度：的度：?叶子：叶子：?结点结点A A的孩子：的孩子：?结点结点B B的孩子：的孩子：?
7、结点结点I I的双亲：的双亲：?结点结点L L的双亲：的双亲：?结点结点B B，C C，D D为为?结点结点K K，L L为为?树的度：树的度：?结点结点A A的层次：的层次：?结点结点M M的层次：的层次：?树的深度：树的深度：?结点结点F F，G G为为?结点结点A A是结点是结点F F，G G的的?320B，C，DE，F3 31 14 4K K，L L，F F，G G，M M，I I，J JD DE E兄弟兄弟兄弟兄弟4 4堂兄弟堂兄弟祖先祖先第8页，共67页，编辑于2022年，星期六5.2.1 5.2.1 二叉树的定义二叉树的定义l定义：二叉树是定义：二叉树是n(nn(n 0)0)个结
8、点的有限集，它或为空树个结点的有限集，它或为空树(n=0)(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成二叉树构成l特点特点每个结点至多有二棵子树每个结点至多有二棵子树(即不存在度大于即不存在度大于2 2的结点的结点)二叉树的子树有左、右之分，且其次序不能任意颠倒二叉树的子树有左、右之分，且其次序不能任意颠倒l基本形态基本形态A只有根结点的二叉树 空二叉树AB右子树为空AB左子树为空ABC左、右子树均非空第9页，共67页，编辑于2022年，星期六2.2.二叉树的定义与树的定义的区别二叉树的定义与树的定义的区别1
9、.1.二叉树存在着空树；但树不能为空。二叉树存在着空树；但树不能为空。2.2.二叉树中的每一个结点只可能有二叉树中的每一个结点只可能有0 0个，个，1 1个或个或2 2个孩子，个孩子，也就是说，二叉树不存在度大于也就是说，二叉树不存在度大于2 2的结点；而树中的的结点；而树中的每个结点可以有多个子树。每个结点可以有多个子树。3.3.二叉树的子树有左右之分，两者不能颠倒；但树的二叉树的子树有左右之分，两者不能颠倒；但树的子树一般是无序的。子树一般是无序的。l除以上区别外，上一节引入树的有关术语对于二叉除以上区别外，上一节引入树的有关术语对于二叉树也适用。树也适用。第10页，共67页，编辑于202
10、2年，星期六3.3.满二叉树的定义满二叉树的定义 若若二二叉叉树树中中所所有有分分枝枝结结点点的的度度数数都都为为2 2，且且叶叶子子结结点点都都在在同同一层上，则称这类二叉树为满二叉树。一层上，则称这类二叉树为满二叉树。5.5.完全二叉树的定义完全二叉树的定义 若二叉树中所有分枝结点的度数要就为若二叉树中所有分枝结点的度数要就为2 2，要就为，要就为0 0，称这，称这类二叉树为完全二叉树。类二叉树为完全二叉树。4.4.顺序二叉树的定义顺序二叉树的定义:对对满满二二叉叉树树从从上上至至下下，从从左左至至右右地地从从1 1开开始始编编号号，结结果果是是每个结点都可以与满二叉树中编号为每个结点都可
11、以与满二叉树中编号为1 1至至n n的结点一一对应的结点一一对应6.6.退化二叉树的定义退化二叉树的定义:如果一棵非空的二叉树只有一个叶子，且其余结点均只有一如果一棵非空的二叉树只有一个叶子，且其余结点均只有一个孩子个孩子 第11页，共67页，编辑于2022年，星期六ABCDEFG图图5.2.2 一棵满二叉树一棵满二叉树1 12 23 34 45 56 67 78 89 9101011111212图图5.2.4 一棵顺序二叉树一棵顺序二叉树图图5.2.5 一棵非顺序二叉树一棵非顺序二叉树1 12 23 34 45 56 67 78 89 91212图图5.2.8 退化的二叉树退化的二叉树AID
12、B1212474728285252(a)(b)第12页，共67页，编辑于2022年，星期六5.2.2 5.2.2 二叉二叉树树的性的性质质 性质性质1:1:在二叉树的第在二叉树的第 i i 层上最多有层上最多有2 2i-1i-1个结点（个结点（i1i1）。）。用归纳法证明它。用归纳法证明它。当当i=1i=1时，时，2 21-11-1=1=1，这时只有一个根结点，显然结论是正确的。，这时只有一个根结点，显然结论是正确的。假假设设，对对于于所所有有的的j j（1ji1j0n0）个元素的二叉树的边数为）个元素的二叉树的边数为n-1n-1。l证明：二叉树中每个元素（除根结点外）有且仅有一个双证明：二叉
13、树中每个元素（除根结点外）有且仅有一个双亲结点。而孩子结点与双亲结点之间有且仅有一条边，因亲结点。而孩子结点与双亲结点之间有且仅有一条边，因此包含此包含n n个元素的二叉树的边数是个元素的二叉树的边数是n-1n-1。第15页，共67页，编辑于2022年，星期六5.2.2 5.2.2 二叉二叉树树的性的性质质 1.1.性质性质1:1:在二叉树的第在二叉树的第 i i 层上最多有层上最多有2 2i-1i-1个结点（个结点（i1i1）。）。l性质性质2:2:深度为深度为h h的二叉树至多有的二叉树至多有2 2h h-1-1个结点。个结点。l性质性质3:3:包括包括n n（n0n0）个元素的二叉树的边
14、数为）个元素的二叉树的边数为n-1n-1。l性质性质4:4:对于任何一棵二叉树，若其终端结点数为对于任何一棵二叉树，若其终端结点数为n n0 0，其度为其度为2 2的结点数为的结点数为n n2 2，则有：，则有：n n0 0=n=n2 2+1+1。5.5.性质性质5:5:若一棵满二叉树有若一棵满二叉树有n n个结点个结点,则深度则深度h h第16页，共67页，编辑于2022年，星期六性质性质6 6一一棵棵有有n n个个结结点点的的顺顺序序二二叉叉树树，如如从从左左至至右右、从从上上至至下下的的，对对每每个个结结点点从从1 1开开始始编编号号，对对于于其其中中任意编号为任意编号为i i的结点（的
15、结点（1in1in）有：）有：(1)(1)若若i i 1,1,则则i i的的父父亲亲是是 i/2i/2；若若i=1i=1，则则i i是是根根结结点点，无父亲。无父亲。(2)(2)若若2in2in，则则i i的的左左孩孩子子是是2i2i；若若2in2in，则则i i无无左左孩孩子。子。(3)(3)若若2i+1n2i+1n，则则i i的的右右孩孩子子是是2i+12i+1；若若2i+1n2i+1n，则则i i无右孩子。无右孩子。第17页，共67页，编辑于2022年，星期六123114589126710图图5.2.9 顺序二叉树父子关系顺序二叉树父子关系152178525777ii+12i2i+12i
16、+2 i/2 第18页，共67页，编辑于2022年，星期六3.3.深度为深度为9 9的二叉树中至少有的二叉树中至少有 个结点。个结点。)9 9 )8 8 )9 91 12.2.深度为的二叉树的结点总数，最多为深度为的二叉树的结点总数，最多为 个。个。)k-1k-1 )log)log2 2k k )k k )k k1.1.树中各结点的度的最大值称为树的树中各结点的度的最大值称为树的 。)高度高度 )层次层次 )深度深度 )度度DCC课堂练习：课堂练习：第19页，共67页，编辑于2022年，星期六 4 4：具有：具有3 3个结点的二叉树可能有几种不个结点的二叉树可能有几种不同形态？同形态？第20页
17、，共67页，编辑于2022年，星期六二叉二叉树树的抽象数据的抽象数据类类型型 Dset：有限元素集合。有限元素集合。Rset：如果不空，被分为根结点、左子树和如果不空，被分为根结点、左子树和右子树；每个子树仍然是一个二叉树。右子树；每个子树仍然是一个二叉树。OPSet：PreOrder(*BT)二叉树的前序遍历递归算法二叉树的前序遍历递归算法PreOrderN(*BT)二叉树的前序遍历非递归算法二叉树的前序遍历非递归算法InOrder(*BT)二叉树的中序遍历递归算法二叉树的中序遍历递归算法InOrderN(*BT)二叉树的中序遍历非递归算二叉树的中序遍历非递归算法法第21页，共67页，编辑于
18、2022年，星期六二叉二叉树树的抽象数据的抽象数据类类型型 PostOrder(*BT)二叉树的后序遍历递归算法二叉树的后序遍历递归算法PostOrderN(*BT)二叉树的后序遍历非递归算法二叉树的后序遍历非递归算法LevelOrderTL(*BT)左至右，上至下层次遍历左至右，上至下层次遍历LevelOrderTR(*BT)右至左，上至下层次遍历右至左，上至下层次遍历MakeNode(&x)构造结点构造结点MakeBinaryTree(*root,*left,*right)联接三个结点为二联接三个结点为二叉树叉树BinaryHeight(*BT)求二叉树的高度求二叉树的高度BinaryDe
19、lete(*BT)二叉树的删除算法二叉树的删除算法第22页，共67页，编辑于2022年，星期六5.3.1 5.3.1 二叉树的存储结构二叉树的存储结构一、顺序存储结构一、顺序存储结构按按二二叉叉树树的的结结点点“自自上上而而下下、从从左左至至右右”编编号号，用用一一组组连连续续的的存存储储单单元元存存储。储。A AB BC CD DE EF FG GH HI I012345678问：顺序存储后能否复原成唯一对应的二叉树形状？问：顺序存储后能否复原成唯一对应的二叉树形状？答：若是完全答：若是完全/满二叉树则可以做到唯一复原。满二叉树则可以做到唯一复原。而且有规律：下标值为而且有规律：下标值为i
20、i的双亲，其左孩子的下标值的双亲，其左孩子的下标值必为必为2(i+1)-12(i+1)-1，其右孩子的下标值必为，其右孩子的下标值必为2(i2(i1)1)例如，对应例如，对应2C2C的两个孩子必为的两个孩子必为55和和6,6,即即B B的左孩的左孩子必是子必是F,F,右孩子必为右孩子必为G G。A AB BC CGGE EI ID DHHF F0 01 12 2第23页，共67页，编辑于2022年，星期六讨论：讨论：不是完全二叉树怎么办？不是完全二叉树怎么办？答：答：一律转为完全二叉树！一律转为完全二叉树！方法很简单，将各层空缺处统统补上方法很简单，将各层空缺处统统补上“虚结点虚结点”，其内容
21、为空。，其内容为空。A AB B C C D D E E012345678.15ABECD缺点：缺点：浪费空间；浪费空间；插入、删除不便插入、删除不便 第24页，共67页，编辑于2022年，星期六二、链式存储结构二、链式存储结构二、链式存储结构二、链式存储结构用二叉链表即可方便表用二叉链表即可方便表用二叉链表即可方便表用二叉链表即可方便表示。示。示。示。datadataleft_childright_childdataleft_childright_childtypedef struct BinaryTreeNodeBinaryTreeNodeEType data;BinaryTreeNode
22、*LChild;BinaryTreeNode*RChild;BinaryTreeNode；一般从根结点开始存储。一般从根结点开始存储。（相应地，访问树中结点时也（相应地，访问树中结点时也只能从根开始）只能从根开始）注：如果需要倒查某结点的双亲，注：如果需要倒查某结点的双亲，可以再增加一个双亲域（直接前趋）可以再增加一个双亲域（直接前趋）指针，将二叉链表变成三叉链表。指针，将二叉链表变成三叉链表。第25页，共67页，编辑于2022年，星期六优点：优点：不浪费空间；不浪费空间；插入、删除方便插入、删除方便 ABCDEFG AB C D E F G第26页，共67页，编辑于2022年，星期六问问：含
23、含有有n n个个结结点点的的二二叉叉树树中中，共共有有链链接接域域有有2n2n个个，空空闲闲的（不用的）链接域有的（不用的）链接域有n+1n+1个（为什么？）个（为什么？）证明：根据性质证明：根据性质4 4：n n0 0=n=n2 2+1,+1,有叶子结点空闲的链接域为有叶子结点空闲的链接域为2n2n2 2+2+2度为度为1 1的结点空闲的链接域为的结点空闲的链接域为n-nn-n0 0-n-n2 2=n-2n=n-2n2 2-1,-1,则总的空闲链接域为则总的空闲链接域为2n2n0 0+n+n1 1=n+1=n+1第27页，共67页，编辑于2022年，星期六5.4.4 5.4.4 二叉树的其它
24、操作二叉树的其它操作 l构造一棵二叉树构造一棵二叉树 的结点的结点 BinaryTreeNode *MakeNode(EType&x)/构造结点构造结点BinaryTreeNode*ptr;Ptr=new BinaryTreeNode;if (ptr)return NULL;ptr-data=x;ptr-LChild=NULL;ptr-RChild=NULL;return ptr;x=A;BinaryTreeNode*Aptr=MakeNode(&x);第28页，共67页，编辑于2022年，星期六2)2)构造一棵二叉子构造一棵二叉子树树（或二叉（或二叉树树）void MakeBinaryTre
25、e(BinaryTreeNode*root,BinaryTreeNode*left,BinaryTreeNode*right)/联接联接root，left,right所指的结点指针为二叉树所指的结点指针为二叉树root-LChild=left;root-RChild=right;第29页，共67页，编辑于2022年，星期六ABCDEFG图图5.4.4 一棵二叉树一棵二叉树MakeBinaryTree(E,G,NULL);MakeBinaryTree(B,D,E);MakeBinaryTree(C,NULL,F);MakeBinaryTree(A,B,C);用用MakeBinaryTree构造下
26、图给出的树。构造下图给出的树。第30页，共67页，编辑于2022年，星期六5.4 5.4 二叉树链式存储结构下的操作二叉树链式存储结构下的操作5.4.1 5.4.1 遍历二叉树遍历二叉树遍历定义遍历定义遍历用途遍历用途遍历方法遍历方法指按某条搜索路线遍访每个结点且不重复指按某条搜索路线遍访每个结点且不重复（又称周游）。（又称周游）。它是树结构插入、删除、修改、查找和排它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础序运算的前提，是二叉树一切运算的基础和核心。和核心。对每个结点的查看通常都是对每个结点的查看通常都是“先左后右先左后右”。Traversing Binary
27、Tree第31页，共67页，编辑于2022年，星期六遍历规则遍历规则l二叉树由根、左子树、右子树构成，定义为二叉树由根、左子树、右子树构成，定义为D、L、R以根结点为参照系注：注：“前、中、后前、中、后”的意思是指访问的结点的意思是指访问的结点D D是先于子树出现还是是先于子树出现还是后于子树出现。后于子树出现。v D、L、R的组合定义了六种可能的遍历方案：的组合定义了六种可能的遍历方案：LDR,LRD,DLR,DRL,RDL,RLDv 若限定若限定先左后右先左后右，则有三种实现方案：，则有三种实现方案：DLR LDR LRD前前序遍历序遍历 中中序遍历序遍历 后后序遍历序遍历 第32页，共6
28、7页，编辑于2022年，星期六ADBCD L RAD L RD L RBDCD L R前序遍历序列：前序遍历序列：A B D C前序遍历:第33页，共67页，编辑于2022年，星期六ADBCL D RBL D RL D RADCL D R中序遍历序列：中序遍历序列：B D A C中序遍历:第34页，共67页，编辑于2022年，星期六ADBC L R DL R DL R DADCL R D后序遍历序列：后序遍历序列：D B C A后序遍历:B第35页，共67页，编辑于2022年，星期六+*A*/EDCB先序遍历结果先序遍历结果+*/A B C D E前缀表示法前缀表示法中序遍历结果中序遍历结果A
29、/B*C*D+E中缀表示法中缀表示法后序遍历结果后序遍历结果A B/C*D*E+后缀表示法后缀表示法例例1：用二叉树表示算术表达式：用二叉树表示算术表达式：用二叉树表示算术表达式：用二叉树表示算术表达式先序遍历结果先序遍历结果中序遍历结果中序遍历结果后序遍历结果后序遍历结果层次遍历结果层次遍历结果第36页，共67页，编辑于2022年，星期六ABCDEFGA AB BC CGGE EI ID DHHF F例例1 1先序遍历结果先序遍历结果A B D H I E C F G中序遍历结果中序遍历结果H D I B E A F C G后序遍历结果后序遍历结果H I D E B F G C A例例1 1
30、例例2 2例例2 2先序先序遍历遍历结果结果A B C D E G F中序遍历结果中序遍历结果C B E G D F A后序遍历结果后序遍历结果C G E F D B A第37页，共67页，编辑于2022年，星期六1.1.构构造造二二叉叉树树：一一步步是是先先构构造造结结点点，第第二二步步是是将将产生的结点联接在一起。产生的结点联接在一起。2.2.计计算算二二叉叉树树的的深深度度：比比较较左左子子树树和和右右子子树树的的高高度度，取其最大值取其最大值 3.3.删删除除二二叉叉树树 ：从从叶叶子子开开始始，先先删删除除左左子子树树，再再删删除右子树，最后删除根结点。除右子树，最后删除根结点。4.
31、4.统统计计二二叉叉树树结结点点数数 ：在在遍遍历历时时，每每次次访访问问一一个个结结点时，就在统计个数的计数器中加一。点时，就在统计个数的计数器中加一。5.5.插入结点或删除结点插入结点或删除结点 ：二叉二叉树树的操作的操作第38页，共67页，编辑于2022年，星期六5.4.2 5.4.2 二叉二叉树树的前序、中序、后序遍的前序、中序、后序遍历历操操作作 对对于于二二叉叉树树的的遍遍历历，将将用用递递归归算算法法和和非非递递归算法给予讨论。归算法给予讨论。l递递归归算算法法简简单单明明晰晰，但但由由于于递递归归本本身身的的嵌嵌套套执执行行过程，会影响到算法执行的效率；过程，会影响到算法执行的
32、效率；l非非递递归归算算法法相相对对较较复复杂杂，实实现现中中运运用用栈栈结结构构类类型型，算法的效率相对效高，算法的效率相对效高，第39页，共67页，编辑于2022年，星期六1 1）前序遍前序遍历历的的递归递归算法算法void PreOrder(BinaryTreeNode*BT)/二叉树的前序遍历递归算法二叉树的前序遍历递归算法if(BT)cout data LChild);PreOrder(BT-RChild);第40页，共67页，编辑于2022年，星期六主程序主程序Pre(T)返回返回pre(T R);返回返回pre(T R);ACBDTBprintf(B);pre(T L);BTAp
33、rintf(A);pre(T L);ATDprintf(D);pre(T L);DTCprintf(C);pre(T L);C返回T左是空返回pre(T R);T左是空返回T右是空返回T左是空返回T右是空返回pre(T R);先序序列：A B D C第41页，共67页，编辑于2022年，星期六前序遍历的非递归算法前序遍历的非递归算法DLR#define MaxStackSize 100typedef structBinaryTreeNode*element;inttop;intMaxSize;Stack；Stack S;第42页，共67页，编辑于2022年，星期六非递归前序算法遍历思想：非递归
34、前序算法遍历思想：lA A。结点指针非空时或堆栈非空时。结点指针非空时或堆栈非空时:如果结点指针非空时，首先访问如果结点指针非空时，首先访问“根根”结点；结点；结点指针为空时，转结点指针为空时，转C C步骤；步骤；lB B。然然后后将将访访问问过过的的结结点点指指针针（一一个个“根根”的的指指针针）进进栈栈，再再将将指指针针指指向向访访问问过过的的结结点点的的左左子子树树的的根根，转转A A步骤；步骤；lC C。堆堆栈栈非非空空时时，退退栈栈，指指针针指指向向退退栈栈结结点点的的右右子子树树结点，转结点，转A A。第43页，共67页，编辑于2022年，星期六 ABCDE图图5.4.3 二叉树二
35、叉树表表5.4.1 5.4.1 二叉树前序遍历非递归过程二叉树前序遍历非递归过程步步 骤骤访问结点访问结点栈栈S S内容内容P P的指向的指向初初 态态A A1 1A AA AB B2 2B BABABC C3 3C C ABCABC空空(C(C的左孩子的左孩子)4 4ABAB空空(C(C的右孩子的右孩子)5 5 A AD D6 6D D ADAD空空(D(D的左孩子的左孩子)7 7 A AE E8 8E E AEAE空空(E(E的左孩子的左孩子)9 9 A A空空(E(E的右孩子的右孩子)1010 空空空空(A(A的右孩子的右孩子)P P第44页，共67页，编辑于2022年，星期六二叉树的前
36、序遍历非递归算法二叉树的前序遍历非递归算法while (p|!IsEmpty(&S)if(p)cout data LChild;/指针指向访问过的指针指向访问过的“根根”结结点左子树点左子树.else/左子树为空时，利用堆栈回朔左子树为空时，利用堆栈回朔第45页，共67页，编辑于2022年，星期六二叉树的前序遍历非递归算法二叉树的前序遍历非递归算法if(!IsEmpty(&S)Pop(&S,p);/从堆栈中弹出回朔结点指针（该结从堆栈中弹出回朔结点指针（该结点已访问过）点已访问过）p=p-RChild;/指针指向回朔结点的右子树指针指向回朔结点的右子树 第46页，共67页，编辑于2022年，星
37、期六2.2.中序遍历的递归算法中序遍历的递归算法 LDR void InOrder(BinaryTreeNode*BT)/二叉树的中序遍历递归算法二叉树的中序遍历递归算法if(BT)InOrder(BT-LChild);cout data RChild);第47页，共67页，编辑于2022年，星期六中序遍历的非递归算法中序遍历的非递归算法 1.1.首先结点指针（一个首先结点指针（一个“根根”的指针）进栈，的指针）进栈，然后将结点指针指向进栈结点的左子树的根，然后将结点指针指向进栈结点的左子树的根，重复重复A A步，直到指针指向空。（最后一个进栈的步，直到指针指向空。（最后一个进栈的是最左子树）
38、；是最左子树）；2.2.堆栈非空时，从堆栈中退出一个指向子树的堆栈非空时，从堆栈中退出一个指向子树的“根根”的指针，访问该指针所指结点，转到的指针，访问该指针所指结点，转到C C步骤。堆步骤。堆栈为空时，结束算法；栈为空时，结束算法；3.3.然后将指针指向访问过结点的右子树的根，重新然后将指针指向访问过结点的右子树的根，重新从从A A步骤做起。步骤做起。第48页，共67页，编辑于2022年，星期六表表5.4.2 5.4.2 二叉树中序遍历非递归过程二叉树中序遍历非递归过程步步 骤骤访问结点访问结点栈栈S S内容内容P P的指向的指向初初 态态A A1 1A AB B2 2ABABC C3 3A
39、BCABC空空(C(C的左孩子的左孩子)4 4C CABAB空空(C(C的右孩子的右孩子)5 5B BA AD D6 6ADAD空空(D(D的左孩子的左孩子)7 7D DA AE E8 8AEAE空空(E(E的左孩子的左孩子)9 9E EA A空空(E(E的右孩子的右孩子)1010A A空空空空(A(A的右孩子的右孩子)ABCDE图图5.4.3 二叉树二叉树第49页，共67页，编辑于2022年，星期六dowhile(p)/找最左子树找最左子树Push(S,p);/“根根”结点（未访问）指针进栈，以后回结点（未访问）指针进栈，以后回朔时再退栈朔时再退栈p=p-LChild;/指针指向该指针指向该
40、“根根”结点左子树结点左子树if(!IsEmpty(S)/左子树为空时，利用堆栈回左子树为空时，利用堆栈回朔朔Pop(S,p);/从堆栈中弹出回朔结点指针（该结点从堆栈中弹出回朔结点指针（该结点未访问过）未访问过）cout data RChild;/指针指向回朔结点的右子树指针指向回朔结点的右子树 while（p）|!IsEmpty(S)）;第50页，共67页，编辑于2022年，星期六3.3.二叉二叉树树的后序遍的后序遍历历 LRDvoid PostOrder(BinaryTreeNode*BT)/二叉树的中序遍历递归算法二叉树的中序遍历递归算法if(BT)PostOrder(BT-LChil
41、d);PostOrder(BT-RChild);Cout data LChild;/指针指向该指针指向该“根根”结点左子树结点左子树else第56页，共67页，编辑于2022年，星期六if(!IsEmpty(S)/左子树为空时，利用堆栈回朔左子树为空时，利用堆栈回朔Pop(S,temp);/从堆栈中弹出回朔结点指针及标志（该从堆栈中弹出回朔结点指针及标志（该结点未访问过）结点未访问过）p=temp.prt;/p指向退栈结点指向退栈结点if(temp.B)cout data RChild;/指针指向指针指向“根根”的右子树的右子树 第57页，共67页，编辑于2022年，星期六对遍历的分析：对遍历
42、的分析：1.从前面的三种遍历算法可以知道：从前面的三种遍历算法可以知道：从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的的访问路径是相同的，只是访问结点的时机不同。访问路径是相同的，只是访问结点的时机不同。从虚线的出发点到终点的路径从虚线的出发点到终点的路径上，每个结点经过上，每个结点经过3次次。AFEDCBG第第1次次经过时访问，是经过时访问，是先序先序遍历遍历第第2次次经过时访问，是经过时访问，是中序中序遍历遍历第第3次次经过时访问，是经过时访问，是后序后序遍历遍历2.2.二叉树遍历的时间效率和空间效率二叉树遍历的时
43、间效率和空间效率时间效率时间效率:O(n)O(n)O(n)O(n)/每个结点只访问一次每个结点只访问一次空间效率空间效率:O(n)O(n)O(n)O(n)/栈占用的最大辅助空间栈占用的最大辅助空间精确值：树深为k的递归遍历需要k+1个辅助单元第58页，共67页，编辑于2022年，星期六5.4.3 5.4.3 二叉树的层次遍历操作二叉树的层次遍历操作 l介绍从上至下的两种遍历过程介绍从上至下的两种遍历过程 l层次遍历时，将使用一个队列作为辅助，来完成遍历过程层次遍历时，将使用一个队列作为辅助，来完成遍历过程typedef structBinaryTreeNode*element;intfront
44、;intrear;intMaxSize;Queue；l如如果果一一个个结结点点被被访访问问后后，则则其其先先准准备备访访问问的的孩孩子子就就应应该该先进队，后访问的孩子后进队。先进队，后访问的孩子后进队。第59页，共67页，编辑于2022年，星期六1.1.从上至下，从上至下，从左至右（从左至右（Top_LeftTop_Left）ABCDEFG图图5.4.4 一棵二叉树一棵二叉树第60页，共67页，编辑于2022年，星期六while(p)cout data LChild)Enqueue(&Q,p-LChild);/左子树进队左子树进队if(p-RChild)Enqueue(&Q,p-RChild
45、);/右子树进队右子树进队if(!DeQueue(&Q,p)return;/出出队队返返回回状状码码ERROR时时结结束束（队队空）空）第61页，共67页，编辑于2022年，星期六2.2.从上至下，从右至左（从上至下，从右至左（Top_RightTop_Right）while(p)cout data RChild)Enqueue(&Q,p-RChild);/右子树进队右子树进队if(p-LChild)Enqueue(&Q,p-LChild);/左子树进队左子树进队if(!DeQueue(&Q,p)return;/出队返回状码出队返回状码ERROR时结束（队空）时结束（队空）第62页，共67页，
46、编辑于2022年，星期六程序设计程序设计l1.1.二叉树前序非递归遍历二叉树前序非递归遍历;l2.中序非递归遍历中序非递归遍历;l3.后序非递归遍历后序非递归遍历;l4.4.层层次遍次遍历历l要求：要求：建立如建立如图图的二叉的二叉树树,结结点点为为student,student,定义如下定义如下,给出给出遍遍历历结果。结果。typedef structintnum;/学号学号 char name10;/姓名姓名 student；typedef student EType;1654327第63页，共67页，编辑于2022年，星期六3.3.关于从下至上算法讨论关于从下至上算法讨论 l静态队列中，
47、出队时不存在释放空间问题静态队列中，出队时不存在释放空间问题?l队列中除原来的队头和队尾指针外，还要增加一个总是指队列中除原来的队头和队尾指针外，还要增加一个总是指在第一个进队结点在第一个进队结点 l最后进队的结点指针作为栈顶最后进队的结点指针作为栈顶.图图5.4.5 5.4.5 队列状态队列状态1 1B B2 2C C3 3D D4 4E E5 5F F6 6G G0 0A Afrontfrontrearrear第64页，共67页，编辑于2022年，星期六2 2。求二叉树的高度。求二叉树的高度 int BinaryHeight(BinaryTreeNode *BT)/返回二叉树的高度返回二叉
48、树的高度 if(!BT)return 0;int HighL=BinaryHeight(BT-LChild);int HighR=BinaryHeight(BT-RChild);if(HighL HighR)return+HighL;else return+HighR;第65页，共67页，编辑于2022年，星期六HL=0HR=0返回1HL=1HL=0HR=0返回1HL=1HR=0返回0返回2HR=2HL=0HR=0返回1HL=0HR=1HR=2HL=3返回3返回2返回返回4第66页，共67页，编辑于2022年，星期六3 3。删除二叉树。删除二叉树 void BinaryDelete(BinaryTreeNode*BT)/二叉树的删除算法二叉树的删除算法if(BT)BinaryDelete(BT-LChild);BinaryDelete(BT-RChild);delete BT;/这里的这里的delete是系统过程是系统过程4。统计二叉树中结点的个数统计二叉树中结点的个数 第67页，共67页，编辑于2022年，星期六