第六章-树和二叉树(2).ppt

1湖南理工学院信息与通信工程学院湖南理工学院信息与通信工程学院 数据结构数据结构第六章 树和二叉树 树的定义与基本操作 二叉树 树和森林 哈夫曼树与哈夫曼编码12湖南理工学院信息与通信工程学院湖南理工学院信息与通信工程学院 数据结构数据结构二叉树的遍历二叉树的遍历：按一定规律对二叉树中的每个结点进行访问且仅访问一次。从二叉树的定义知，一棵二叉树由三部分组成：根结点、左子树和右子树。若规定D,L,R分别代表“访问根结点”、“遍历左子树”和“遍历右子树”，则其遍历二叉树的方案有6种。若限定先左后右，则只有前3种情况，分别称为：前序遍历（DLR）中序遍历（LDR）后序遍历（LRD）DLRDLR、LDR、LRDRDL、RLD、DRL23湖南理工学院信息与通信工程学院湖南理工学院信息与通信工程学院 数据结构数据结构1.前序遍历(DLR)若二叉树为空，则结束返回。否则：(1)访问根结点；(2)前序遍历左子树；(3)前序遍历右子树。ADBCD L RAD L RD L RBDCD L R先序遍历序列：A B D C34湖南理工学院信息与通信工程学院湖南理工学院信息与通信工程学院 数据结构数据结构前序遍历(DLR)练习 A,B,D,E,G,C,F A A F F G G E E D D C C B BF,C,A,D,B,E,G,H,P45湖南理工学院信息与通信工程学院湖南理工学院信息与通信工程学院 数据结构数据结构void PreOrderTraverse(BiTree BT)/*前序遍历二叉树,BT为指向二叉树(或某一子树)根结点的指针*/if(BT!=NULL)Visit(root-data);/*访问根结点*/PreOrderTraverse(BT-LChild);/*前序遍历左子树*/PreOrderTraverse(BT-RChild);/*前序遍历右子树*/前序遍历(DLR)递归算法5void preorderTraverse(BiTree*bt)if(bt!=NULL)printf(%dt,bt-data);preorderTraverse(bt-lchild);preorderTraverse(bt-rchild);主程序主程序Pre(T)返回返回pre(T R);返回返回pre(T R);ACBDTBprintf(B);pre(T L);BTAprintf(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 C67湖南理工学院信息与通信工程学院湖南理工学院信息与通信工程学院 数据结构数据结构2.中序遍历(LDR)若二叉树为空，则结束返回。否则：(1)中序遍历左子树；(2)访问根结点；(3)中序遍历右子树。ADBCL D RBL D RL D RADCL D R中序遍历序列：B D A C78湖南理工学院信息与通信工程学院湖南理工学院信息与通信工程学院 数据结构数据结构中序遍历(LDR)练习 A A F F G G E E D D C C B BD,B,G,E,A,C,FA,C,B,D,F,E,H,G,P89湖南理工学院信息与通信工程学院湖南理工学院信息与通信工程学院 数据结构数据结构中序遍历(LDR)非递归算法 二叉树的中序遍历的非递归算法，需要用到一个栈S。其算法的执行步骤如下:(1)当树非空时，将指针p指向根结点，p为当前结点指针。(2)将p压入栈S中，并令p指向其左孩子。(3)重复执行步骤(2)，直到p为空。(4)从栈S中弹出栈顶元素，将p指向此元素。(5)访问当前结点p，并将p指向其右孩子。(6)重复执行步骤(2)-(5)，直到p为空并且栈S也为空。(7)遍历结束。9ABCDEFGpiP-A(1)ABCDEFGpiP-AP-B(2)ABCDEFGpiP-AP-BP-C(3)p=NULLABCDEFGiP-AP-B访问：C(4)10pABCDEFGiP-A访问：C B(5)ABCDEFGiP-AP-D访问：C Bp(6)ABCDEFGiP-AP-DP-E访问：C Bp(7)ABCDEFGiP-AP-D访问：C B Ep(8)11ABCDEFGiP-AP-DP-G访问：C B EP=NULL(9)ABCDEFGiP-A访问：C B E G Dp(11)ABCDEFGiP-AP-F访问：C B E G Dp(12)ABCDEFGiP-AP-D访问：C B E Gp(10)12ABCDEFGiP-A访问：C B E G D Fp=NULL(13)ABCDEFGi访问：C B E G D F Ap(14)ABCDEFGi访问：C B E G D F Ap=NULL(15)1314湖南理工学院信息与通信工程学院湖南理工学院信息与通信工程学院 数据结构数据结构Void InOrderNoRec(BiTree BT)stack S;BiTree p=BT-root;while(NULL!=P)|!StackEmpty(S)if(NULL!=P)StackPush(S,P);p=p-lchild;elsep=Top(S);StackPop(S);printf(“%d”,p-data);p=p-rchild;1415湖南理工学院信息与通信工程学院湖南理工学院信息与通信工程学院 数据结构数据结构3.后序遍历(LRD)若二叉树为空，则结束返回。否则：(1)后序遍历左子树；(2)后序遍历右子树；(3)访问根结点。ADBC L R DL R DL R DADCL R D后序遍历序列：D B C AB1516湖南理工学院信息与通信工程学院湖南理工学院信息与通信工程学院 数据结构数据结构后序遍历(LRD)练习 A A F F G G E E D D C C B B D,G,E,B,F,C,AA,B,D,C,H,P,G,E,F1617湖南理工学院信息与通信工程学院湖南理工学院信息与通信工程学院 数据结构数据结构 假设一棵二叉树的后序遍历序列为D G J H E B I F C A，中序遍历序列为D B G E H J A C I F，则其前序遍历序列为 。A）A B C D E F G H I J B）A B D E G H J C F I C）A B D E G H J F I C D）A B D E G J H C F IABDEGHJCFI1718湖南理工学院信息与通信工程学院湖南理工学院信息与通信工程学院 数据结构数据结构二叉树遍历的应用在计算机中可以用树结构来表示算术表达式 (1)表达式中的每一个运算符在树中对应一个结点，称为运算符结点。(2)运算符的每一个运算对象在树中为该运算符结点的子树（在树中的顺序为从左到右）。(3)运算对象中的单变量均为叶子结点。1819湖南理工学院信息与通信工程学院湖南理工学院信息与通信工程学院 数据结构数据结构a*(bc/d)e*hg*f(s，t，xy)1920湖南理工学院信息与通信工程学院湖南理工学院信息与通信工程学院 数据结构数据结构a*(bc/d)e*hg*f(s，t，xy)2021湖南理工学院信息与通信工程学院湖南理工学院信息与通信工程学院 数据结构数据结构-+/a*b-efcd先序遍历：中序遍历：后序遍历：层次遍历：-+a*b-c d/e f-+a*b-cd/ef-+a*b-cd/e f-+a*b-c d/e f2122湖南理工学院信息与通信工程学院湖南理工学院信息与通信工程学院 数据结构数据结构 1.基本概念 二叉树的遍历运算是将二叉树中结点按一定规律线性化的过程。当以二叉链表作为存储结构时，只能找到结点的左、右孩子信息，而不能直接得到结点在遍历序列中的前驱和后继信息。要得到这些信息，第一种方法是将二叉树遍历一遍，在遍历过程中便可得到结点的前驱和后继，但这种动态访问浪费时间；第二种方法是充分利用二叉链表中的空链域，将遍历过程中结点的前驱、后继信息保存下来。线索二叉树2223湖南理工学院信息与通信工程学院湖南理工学院信息与通信工程学院 数据结构数据结构 在有n个结点的二叉链表中共有2n个链域，但n+1个链域是空的。我们可以利用n+1个空链域来存放遍历过程中结点的前驱和后继信息。现作如下规定：若结点有左子树，则其LChild域指向其左孩子，否则LChild域指向其前驱结点；若结点有右子树，则其RChild域指向其右孩子，否则RChild域指向其后继结点。2324湖南理工学院信息与通信工程学院湖南理工学院信息与通信工程学院 数据结构数据结构LChildLtagDataRtagRChild 为了区分孩子结点和前驱、后继结点，为结点结构增设两个标志域，如下图所示：Ltag=0 LChild域指示结点的左孩子域指示结点的左孩子1 LChild域指示结点的遍历前驱域指示结点的遍历前驱Rtag=0 RChild域指示结点的右孩子域指示结点的右孩子1 RChild域指示结点的遍历后继域指示结点的遍历后继2425湖南理工学院信息与通信工程学院湖南理工学院信息与通信工程学院 数据结构数据结构typedef struct node char data;struct node*lchild,*rchild;int ltag，rtag;thbitree;ltag data rtaglchildrchild2526湖南理工学院信息与通信工程学院湖南理工学院信息与通信工程学院 数据结构数据结构先序线索二叉树 A A F F E E D D C C B B0A00B10C11D01E11F1先序遍历序列：ABDFCENull2627湖南理工学院信息与通信工程学院湖南理工学院信息与通信工程学院 数据结构数据结构0A00B10C11D01E11F1中序线索二叉树 A A F F E E D D C C B B中序遍历序列：DFBAECNullNull2728湖南理工学院信息与通信工程学院湖南理工学院信息与通信工程学院 数据结构数据结构0A00B10C11D01E11F1后序线索二叉树 A A F F E E D D C C B B后序遍历序列：FDBECANull28