数据结构[第6章].ppt

第六章 二叉树⒈教学内容;⒊教学重点： ⑴ 二叉树的定义;6.1 定义与性质6.1.1;1．二叉树的定义 二叉树（;因此二叉树具有五种基本形态，如;2．二叉树的相关概念 (;(5) 路径、路径长度。如果一;(10) 满二叉树。 在;(11) 完全二叉树。 ;6.1.2 二叉树的主要性质;性质3 对于一棵非空的二叉树;性质4 具有n个结点的完全二;性质5 对于具有n个;此外，若对二叉树的根结点从0开;6.2 基本操作与存储实现6;6.2.1 二叉树的存储1．;下面给出一棵完全二叉树的顺序存;对于非完全二叉树： 若仍;对于一般的二叉树，如果仍按从上;如图给出了一棵一般二叉树改造后;最坏的情况是右单支树，一棵深度;2．链式存储结构（1）二叉链表;下图(a)给出一棵二叉树的二叉;data、lchild以及rc;下图给出一棵二叉树的三叉链表示;尽管在二叉链表中无法由结点直接;6.2.2 二叉树的基本操作及;(4) InsertR（bt，;2、 算法的实现 ;(1) Initiate（bt;【算法6-1*】建立二叉树算法;(2) Create（x，lb;(3) InsertL（bt，;(4) DeleteL（bt，;6.3 二叉树的遍历 二叉树;6.3.1 二叉树的遍历方法;由二叉树的定义可知，一棵由根结;1．先序遍历（DLR） 先序遍;小插曲：Rev( ){ cha;对于上图所示的二叉树，按先序遍;2．中序遍历（LDR）中序遍历;对于上图所示的二叉树，按中序遍;【算法6-6】二叉树中序遍历算;3．后序遍历（LRD）后序遍历;对于上图所示的二叉树，按后序遍;4.层次遍历 所谓二叉树;由层次遍历的定义可以推知，在进;因此，在进行层次遍历时，可设置;【算法6-8】二叉树层次遍历算;6.3.2 二叉树遍历的非递;如前图所示的二叉树，对其进行先;分析：包络线正是从根结点开始沿;分析：在这一过程中，返回结点的;(1)先序遍历的非递归实现 ;对于下图所示的二叉树，用该算法;（2）中序遍历的非递归实现 ;（3）后序遍历的非递归实现 ;这样当结点指针进、出栈时，其标;【算法6-10】后序遍历的非递;也可以：while(p!=NU;6.3.3 由遍历序列恢复二;先序序列中，第一个结点一定是二;同时，左子树和右子树的根结点又;下面通过一个例子，来给出由二叉;上述过程是一个递归过程，其递归;【算法6-11】由先序和中序序;【算法6-11-2】由后序和中;void ReBiTree(c;6.3.4 不用栈的二叉树遍;还有一类二叉树的遍历算法，就是;构建一棵二叉树的二叉链表。前序;【算法6-22】建立二叉树的二;void InOrderOut;6.4 线索二叉树6.4.1;6.4.1 线索二叉树的定义;设想： 能否把结点;2．线索二叉树的结构 由;那么，下面的问题是在存储中，如;⑵ 不改变结点结构，仅在作为线;6.4.2 线索二叉树的基本;1．建立一棵中序线索二叉树 ;下面是建立中序线索二叉树的递归;【算法6-12】建立中序线索二;void InTreading;2．在中序线索二叉树上查找任意;【算法6-13】中序线索二叉树;3．在中序线索二叉树上查找任意;【算法6-14】在中序线索二叉;在先序线索二叉树上查找任意结点;4．在中序线索二叉树上查找任意;当p-ltag=1时，p-;不是最后一个结点时(如G、E);BiThrTree IpreP;5．在中序线索二叉树上查找任意;⑴若待确定后序前驱的结点为分支;若p-lchild不是头结点;【算法6-16】在中序线索二叉;6．在中序线索二叉树上查找值为;【算法6-17】在中序线索二叉;7．在中序线索二叉树上的更新 ;下面分两种情况来分析： ;⑵若*s的右子树非空，如图 (;【算法6-18】在中序线索二叉;6.5 二叉树应用举例6.5;6.5.2．统计出给定二叉树中;（2）二叉链表存储结构的实现【;利用遍历算法：int num=;6.5.3．创建二叉树二叉链表;【算法6-22】建立二叉树的二;void InOrderOut;6.5.4．表达式运算 ;6.6 最优二叉树――哈夫曼;设有10000个数据需要处理，;则：(c)要比较：22000;其中Wk为第k个叶结点的权值，;无标题;最优二叉树，也称哈夫曼（Haf;同一组具有确定权值的叶结点，可;其带权路径长度分别为： ;如何找到带权路径长度最小的二叉;哈夫曼树构造方法是： （;例：5个叶结点权值集合为W＝{;6.6.3 哈夫曼树的构造;parent域的作用：（1）双;无标题;【算法6-23】哈夫曼树的构造;for (i=0;in;