树和二叉树2(二叉树基本应用).ppt

《树和二叉树2(二叉树基本应用).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、6.3遍历二叉树遍历二叉树遍历的非递归算法遍历二叉树的应用顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。一、问题的提出“访问”的含义可以很广，如：输出结点的信息等。6.3.1遍历二叉树“遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构，每个结点有两个后继，则存在如何遍历即按什么样的搜索路径进行遍历的问题。对“二叉树”而言，可以有三条搜索路径：1．先上后下的按层次遍历；2．先左（子树

2、）后右（子树）的遍历；3．先右（子树）后左（子树）的遍历。根结点(D)非空二叉树左子树(L)右子树(R)二、先左后右的遍历算法先（根）序的遍历算法中（根）序的遍历算法后（根）序的遍历算法根左子树右子树根根根根根若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。先（根）序的遍历算法：若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。中（根）序的遍历算法：若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）

3、后序遍历右子树；（3）访问根结点。后（根）序的遍历算法：先序遍历：DLR中序遍历：LDR后序遍历：LRDADBCT1T2T3DLRADLRDLR>B>>D>>CDLR以先序遍历DLR为例演示遍历过程ABDCBDACDBCAABCDEFGHK先序序列：中序序列：后序序列：ABCDEFGHKBDCAEHGKFDCBHKGFEA递归算法的描述先序遍历二叉树的递归算法：voidPreorder(BiTreeT){if(T){printf(T->data);//访问结点Preorder(T->lchild)

4、;//遍历左子树Preorder(T->rchild);//遍历右子树}}VoidPreOder(BiTreeT){if(T){printf(T->data);PreOrder(T->lchild);PreOrder(T->rchild);}}/*先序遍历*/主程序Pre(T)返回返回pre(TR);返回返回pre(TR);ACBDTBprintf(B);pre(TL);BTAprintf(A);pre(TL);ATDprintf(D);pre(TL);DTCprintf(C);pre(TL);C

5、返回T>左是空返回pre(TR);T>左是空返回T>右是空返回T>左是空返回T>右是空返回pre(TR);中序遍历二叉树的递归算法：voidinOrder(BiTreeT){if(T!=NULL){inOrder(T->lchild);printf(T->data);inOrder(T->rchild);}}后序遍历二叉树的递归算法：voidPostOrder(BiTreeT){if(T!=NULL){PostOrder(T->lchild);PostOrder(T->rchild);printf

6、(T->data);}}层次遍历：Ａ　Ｂ　Ｃ　Ｄ　Ｅ　Ｆ三、层次遍历ADCBFEABCDEFG遍历序列：AABCBDCEFGDEFG用队列存放结点地址算法描述队列Q初始化；2.如果二叉树非空，将根指针入队；3.循环直到队列Q为空3.1q=队列Q的队头元素出队；3.2访问结点q的数据域；3.3若结点q存在左孩子，则将左孩子指针入队；3.4若结点q存在右孩子，则将右孩子指针入队；算法：用到队列voidlayer(BiTreeT){InitQueue(Q);if(T)EnQueue(Q,T);while

7、(!QueueEmpty(Q)){DeQueue(Q,p);printf(p);if(p->lchild)EnQueue(Q,p->lchild);if(p->rchild)EnQueue(Q,p->rchild);}}AGBCDFE遍历算法的执行轨迹第1次到达第2次到达第3次到达每个结点都有3次到达的机会-+/A*EFB-CDP=NULL先序遍历非递归算法有三件事要顺序完成：①访问根结点X；②遍历XL；③遍历XR其中①②连接没问题，但②和③的连接有问题。为了将来遍历XR，必须将X→rchild的

8、值存起来；用指针栈来存储。ABDCEppppp&A&Cp=NULLp=NULL&D栈SXXRXLvoidpreorder(BiTreebt){//顺序栈s用于存放指针InitStack(s)；push(s，bt)；while(!StackEmpty(s)){p=pop(s)；while(p){printf(p→data)；if(p→rchild)push(s，p→rchild)；p=p→lchild；}}}//preorder四、遍历的非递归算法——路径分析法中序遍历的非递归pP=