数据结构第7章3课件

上节回顾

7.3二叉树的设计和实现

7.3.1二叉树的存储结构

7.3.2二叉链存储结构的二叉树操作实现

17.4二叉树遍历7.4.1二叉树遍历1、遍历定义——2、遍历用途——3、遍历方法——指按照某种顺序访问二叉树中的每个结点，使每个结点被访问一次且仅被访问一次。（或指按某条搜索路线遍访每个结点且不重复）。它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。对每个结点的查看通常都是“先左后右”。24、遍历规则———二叉树由根、左子树、右子树构成，定义为D、

L、R以根结点为参照系注：“先、中、后”的意思是指访问的结点D是先于子树出现还是后于子树出现。

D、L、R的组合定义了六种可能的遍历方案：LDR,LRD,DLR,DRL,RDL,RLD

若限定先左后右，则有三种实现方案：DLRLDRLRD先序遍历中序遍历后序遍历

3（3）中序遍历根结点的右子树。（三）后序遍历二叉树的递归算法为：若二叉树为空，则算法结束；否则：（1）后序遍历根结点的左子树；（2）后序遍历根结点的右子树；（3）访问根结点。（四）二叉树的层序遍历算法：(1)初始化设置一个队列；(2)把根结点指针入队列；(3)当队列非空时，循环执行步骤(3.a)到步骤(3.c):5

(3.a)出队列取得一个结点指针，访问该结点；

(3.b)若该结点的左子树非空，则将该结点的左子树指针入队列；

(3.c)若该结点的右子树非空，则将该结点的右子树指针入队列；

（4）结束。

注意：一个二叉树的遍历序列不能决定一棵二叉树，但先序（或后序）和中序遍历序列的组合可以惟一确定一棵二叉树。而先序和后序遍历则不能。6例1：先序遍历的结果是：中序遍历的结果是：后序遍历的结果是：ABCDEDBEACDEBCA口诀：DLR—先序遍历，即先根再左再右LDR—中序遍历，即先左再根再右LRD—后序遍历，即先左再右再根ABDEC7+*A*/EDCB先序遍历结果+**/ABCDE—前缀表示法中序遍历结果A/B*C*D+E—中缀表示法后序遍历结果AB/C*D*E+—后缀表示法层次遍历结果+*E*D/CAB例2：用二叉树表示算术表达式8已知中序遍历：BDCEAFHG已知后序遍历：DECBHGFA（BDCE）（FHG）（DCE）BFGHCDEA10例4：编写递归算法，打印二叉树中所有叶子结点的值。

思路：若左右指针均空，必为叶子。可选用任何一种遍历算法查找叶子，将其统计并打印出来。voidDLR(BiTreeNode*root,voidvisit(DataTypeitem))

//采用先序遍历的递归算法{if(root!=NULL)//非空二叉树条件，等效于if(root){if(!root->leftChild&&!root->rightChild)//是叶子结点则统计并打印{visit(root->data);}

DLR(root->leftChild,visit);//递归遍历左子树，直到叶子处；

DLR(root->rigthChild,visit);//递归遍历右子树，直到叶子处；}}12思考：二叉链表空间效率这么低，能否利用这些空闲区存放有用的信息或线索？——我们可以用它来存放当前结点的直接前驱和后继等线索，以加快查找速度。结论：用二叉链表法存储包含n个结点的二叉树，结点的指针区域中会有n+1个空指针。这就是线索二叉树（ThreadedBinaryTree）14二叉树中容易找到结点的左右孩子信息，但该结点的直接前驱和直接后继只能在某种遍历过程中动态获得。先依遍历规则把每个结点对应的前驱和后继线索预存起来，这叫做“线索化”。意义：从任一结点出发都能快速找到其前驱和后继，且不必借助堆栈。对二叉树进行某种遍历之后，将得到一个线性有序的序列。例如对某二叉树的中序遍历结果是BDCEAFHG，意味着已将该树转为线性排列，显然其中结点具有唯一前驱和唯一后继。在此前提下，那n+1个空链域才能装入（也装得下）“线索”。讨论2.如何获得这种“直接前驱”或“直接后继”？有何意义？讨论1：二叉树是1:2的非线性结构，如何定义其直接后继？15①每个结点增加两个域：fwd和bwd；存放前驱指针存放后继指针如何预存这类信息？有两种解决方法：②与原有的左右孩子指针域“复用”，充分利用那n+1个空链域。规定：1）若结点有左子树，则lchild指向其左孩子；否则，lchild指向其直接前驱(即线索)；2）若结点有右子树，则rchild指向其右孩子；否则，rchild指向其直接后继(即线索)。datalchildrchildfwdbwddatalchildrchild缺点：空间效率太低！问题：计算机如何判断是孩子指针还是线索指针？如何区别？16lchildLTagdataRTagrchild约定:当Tag域为0时,表示正常情况;当Tag域为1时,表示线索情况.前驱(后继)左(右)孩子为区别两种不同情况，特增加两个标志域：问：增加了前驱和后继等线索有什么好处？——能方便找出当前结点的前驱和后继，不用堆栈（递归）也能遍历整个树。各1bit171.有关线索二叉树的几个术语线索链表：线索：线索二叉树：线索化：用含Tag的结点样式所构成的二叉链表。指向结点前驱和后继的指针。在二叉树的结点上加上线索的二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程。线索化过程就是在遍历过程中修改空指针的过程：将空的lchild改为结点的直接前驱；将空的rchild改为结点的直接后继。非空指针呢？仍然指向孩子结点（称为“正常情况”）18ABCGEIDHFroot悬空？NIL悬空？NIL解：对该二叉树中序遍历的结果为:

H,D,I,B,E,A,F,C,G所以添加线索应当按如下路径进行：为避免悬空态，应增设一个头结点例6：画出以下二叉树对应的中序线索二叉树。2.线索二叉树的生成——线索化线索化过程就是在遍历过程中修改空指针的过程2000A00C00B11E11F11G00D11I11H注：此图中序遍历结果为:

H,D,I,B,E,A,F,C,

G