《二叉树后序遍历.docx》由会员分享，可在线阅读，更多相关《二叉树后序遍历.docx（32页珍藏版）》请在三一办公上搜索。
1、二叉树后序遍历的非递归算法作者：charming 2007-12-09 13:05:13思路如下：先找到最左边的叶子并把路上遇到的节点依次压栈，然后取栈顶的元素(该元素为最左边的叶子)，并判 断(1)它有没有右节点；(2)右节点是否被访问过。如果(1)为有右节点同时(2)为没有访问过，则压入它的右子树。 否则，就访问该节点，并设置pre为改节点，并且出栈。void s_postorder_2(NODE *t)NODE *stack100;NODE *pre=NULL;int top=0;while(top!=0 | | t!=NULL) /栈不空，或者，t 不空。while(t!=NULL)先
2、找到最左边的叶子并把路上遇到的节点依次压栈stacktop+=t;t=t-lchild;/t=NULLif(top!=0)/如果栈不空t=stacktop-1; /取栈顶元素if (t-rchild=NULL | | t-rchild=pre) /无右孩子或者右孩子已经访问过printf (-%c,t-data); /访问 ttop-; /出栈pre=t;t=NULL; /防止t再次入栈else /有右孩子且右孩子未访问过t=t-rchild;/end while这段程序类似上个程序，只是结构上略有变化。void s_postorder_1(NODE *t)NODE *pre=NULL;NOD
3、E *stack100;int top=0;while (t!=NULL | top!=0)if(t!=NULL)stacktop+=t;t=t-lchild;else /t=NULLt=stacktop-1; /取栈顶元素if (t-rchild=NULL | | t-rchild=pre) /无右孩子或者右孩子已经访问过printf (-%c,t-data); /访问 ttop-; /出栈pre=t;t=NULL;elset=t-rchild;/end while二叉树后序遍历的非递归算法Re:二叉树后序遍历的非递归算法-中、前序遍历#include stdlib.h”字串7#define
4、 MAXNODE 20#define ISIZE 8#define NSIZE0 7#define NSIZE1 8#define NSIZE2 15/SHOWCHAR = 1（显示字符）SHOWCHAR = 0（显示数字）#define SHOWCHAR 1/二叉树结构体struct BTNodeint data;BTNode *rchild;BTNode *lchild;；/非递归二叉树遍堆栈struct ABTStackBTNode *ptree;ABTStack *link;char TreeNodeSNSIZE0 = A,B,C,D,E,F,G;char PreNodeNSIZE0
5、= A,B,D,E,C,F,G;char MidNodeNSIZE0 = D,B,E,A,C,G,F;int TreeNodeN0NSIZE12 = 0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7;int TreeNodeN1NSIZE12 = 0,0,4,1,2,2,6,3,1,4,3,5,5,6,7,7;int TreeNode0NSIZE12 = 0,0,D,1,B,2,F,3,A,4,C,5,E,6,G,7;int TreeNode1NSIZE12 = 0,0,A,1,B,2,C,3,D,4,E,5,F,6,G,7;int TreeNode2NSIZE22 = 0,0,
6、A,1,B,2,C,3,D,4,E,5,F,6,G,7,H,8,T,9,J,10,K,11,L,12,M,13,N,14;字串 8int InsertNodeISIZE = -10,-8,-5,-1,0,12,14,16;/char *prestr = ABDECFG”;/char *midstr = DBEACGF”;/*二叉树创建函数dCreateBranchTree1（）递归算法参数描述：int array:二叉树节点数据域数组int i:当前节点的序号int n:二叉树节点个数返回值：dCreateBranchTreel =新建二叉树的根节点指针备注：根节点 =array(i+j)/2
7、;左子节点 =arrayi,array(i+j)2-1右子节点 =array(i+j)/2+1,arrayj*/BTNode *dCreateBranchTree1(char array,int i,int n)BTNode *p; /* 二叉树节点 */if(i=n)return(NULL);p = (BTNode *)malloc(sizeof(BTNode);p-data = arrayi;p-lchild = dCreateBranchTree1(array,2*i+1,n);p-rchild = dCreateBranchTree1(array,2*i+2,n);字串2return(
8、p);/*二叉树创建函数dCreateBranchTree2()递归算法参数描述：int array:二叉树节点数据域数组int i:当前节点的序号int n:二叉树节点个数返回值：dCreateBranchTree2 =新建二叉树的根节点指针备注：根节点 =array(i+j)/2;左子节点 =arrayi,array(i+j)2-1右子节点 =array(i+j)/2+1,arrayj*/BTNode *dCreateBranchTree2(char array,int i,int j)BTNode *p; /* 二叉树节点 */if(ij)return(NULL);p = (BTNode
9、 *)malloc(sizeof(BTNode);p-data = array(i+j)/2;p-lchild = dCreateBranchTree2(array,i,(i+j)/2-1);p-rchild = dCreateBranchTree2(array,(i+j)/2+1,j);return(p);/*二叉树创建函数dCreateBranchTree3()QE递归算法 字串7已知二叉树的前，中序遍历序列串，构造对应的二叉树编程思想:首先，在前序遍历序列中的首元素是二叉树的根节点，接着,在中序遍历序列中找到此节点，那么在此节点以前的节点必为 其左孩子节点，以后的必为其右孩子节点；然后，
10、在中序遍历序列中，根节点的左子树和右子树再分别对应子树前序遍历序列的首字符确定子树的根节点，再由中序 遍历序列中根节点的位置分别确定构成它们的左子树和右子树 的节点；依次类推，确定二叉树的全部节点，构造出二叉树.参数描述：char *pre: 前序遍历序列char *mid:中序遍历序列int n: 遍历序列中节点个数返回值：dCreateBranchTree3 =新建二叉树的根节点指针*/BTNode *dCreateBranchTree3(char *pre,char *mid,int n)BTNode *p;char *t;int left;if(ndata = *pre;for(t=m
11、id;tlchild = dCreateBranchTree3(pre+1,t,left);p-rchild = dCreateBranchTree3(pre+1+left,t+1,n-1-left); return(p);AD/*二叉树创建函数CreateBranchTree()参数描述：int array:二叉树节点数据域数组int n:二叉树节点个数返回值：CreateBranchTree =新建二叉树的根节点指针*/BTNode *CreateBranchTree(int array2,int n)BTNode *head,*p;BTNode *NodeAddrMAXNODE; /节点
12、地址临时缓冲区 int i,norder,rorder;head = NULL;printf(二叉树原始数据新建顺序：t)；for(i=1;idata = arrayi0;p-lchild = p-rchild = NULL;norder = arrayi1;字串9NodeAddrnorder = p;if(norder1)rorder = norder / 2; /*非根节点:挂接在自己的父节点上*/ if(norder % 2 = 0)NodeAddrrorder-lchild = p;elseNodeAddrrorder-rchild = p;elsehead = p; /* 根节点 *
13、/if(SHOWCHAR)printf(%c,p-data);elseprintf(%d,p-data);return(head)/非递归部分/*二叉树前序遍历函数pre_Order_Access()非递归算法参数描述：BTNode *head:二叉树的根节点指针字串2*/void pre_Order_Access(BTNode *head)BTNode *pt;ABTStack *ps,*top;pt = head;top = NULL;printf(n二叉树的前序遍历结果：t”);while(pt!=NULL |top!=NULL) /*二叉树未遍历完，或堆栈非空*/while(pt!=N
14、ULL)if(SHOWCHAR)printf(%c,pt-data); /* 访问根节点 */elseprintf(%d,pt-data); /* 访问根节点 */ps = (ABTStack *)malloc(sizeof(ABTStack); /*根节点进栈 */ ps-ptree = pt;ps-link = top;top = ps;pt = pt-lchild; /*遍历节点右子树,经过的节点依次进栈*/if(top!=NULL)pt = top-ptree; /*栈顶节点出栈*/ps = top;top = top-link;free(ps); /*释放栈顶节点空间*/pt = p
15、t-rchild; /*遍历节点右子树*/*二叉树中序遍历函数mid_Order_Access()非递归算法参数描述：BTNode *head:二叉树的根节点指针*/void mid_Order_Access(BTNode *head)BTNode *pt;ABTStack *ps,*top;int counter =1;pt = head;top = NULL;printf(n二叉树的中序遍历结果：t”);while(pt!=NULL |top!=NULL) /*二叉树未遍历完，或堆栈非空*/while(pt!=NULL)ps = (ABTStack *)malloc(sizeof(ABTS
16、tack); /*根节点进栈 */字串8ps-ptree = pt;ps-link = top;top = ps;pt = pt-lchild; /*遍历节点右子树,经过的节点依次进栈*/if(top!=NULL)pt = top-ptree; /*栈顶节点出栈*/ps = top;top = top-link;free(ps); /*释放栈顶节点空间*/if(SHOWCHAR)printf(%c,pt-data); /* 访问根节点 */elseprintf(%d,pt-data); /* 访问根节点 */pt = pt-rchild; /*遍历节点右子树*/*二叉树后序遍历函数last_O
17、rder_Access()非递归算法参数描述：BTNode *head:二叉树的根节点指针 */void last_Order_Access(BTNode *head)字串 1BTNode *pt;ABTStack *ps,*top;int counter =1;pt = head;top = NULL;printf(n二叉树的后序遍历结果：t”);while(pt!=NULL |top!=NULL) /*二叉树未遍历完，或堆栈非空*/while(pt!=NULL)ps = (ABTStack *)malloc(sizeof(ABTStack); /*根节点进栈 */ ps-ptree = p
18、t;ps-link = top;top = ps;pt = pt-lchild; /*遍历节点右子树,经过的节点依次进栈*/if(top!=NULL)pt = top-ptree; /*栈顶节点出栈*/ps = top;top = top-link;free(ps); /*释放栈顶节点空间*/printf(%c,pt-data); /* 访问根节点 */pt = pt-rchild; /*遍历节点右子树*/字串9/*二叉查找树静态查找函数static_Search_STree()WE递归算法参数描述：BTNode *head:二叉查找树的根节点指针int key:查找关键码返回值：static
19、_Search_STree =键值为key的节点指针(找到)static_Search_STree = NULL(没 有找到)*/BTNode *static_Search_STree(BTNode *head,int key)while(head!=NULL)if(head-data = key)printf(n 数据域=%dt 地址=%dtn”,head-data,head);return(head); /* 找到 */if(head-data key)head = head-lchild; /*继续沿左子树搜索*/elsehead = head-rchild; /*继续沿右子树搜索*/r
20、eturn(NULL); /* 没有查找*/*二叉查找树动态查找函数dynamic_Search_STree()非递归算法字串8参数描述：BTNode *head:二叉查找树的根节点指针BTNode *parent:键值为key的节点的父节点指针的指针BTNode *head:键值为key的节点指针的指针(找到)或NULL(没有找到)int key:查找关键码注意：*parent = NULL且*p = NULL没有找到(二叉树为空)*parent = NULL且*p != NULL找到(找到根节点)*parent != NULL且*p = NULL没有找到(叶节点)data = key)re
21、turn; /* 找到 */*parent = *p; /*以当前节点为父，继续查找*/if(*p)-data key)*p = (*p)-lchild; /*继续沿左子树搜索*/else*p = (*p)-rchild; /*继续沿右子树搜索*/*二叉查找树插入节点函数Insert_Node_STree()data = key;nnode-lchild = nnode-rchild = NULL;字串4if(p=NULL)head = p; /*原树为空，新建节点为查找树*/elseif(p-data key)p-lchild = nnode; /*作为左孩子节点*/elsep-rchild
22、 = nnode; /*作为右孩子节点*/return(1); /*插入成功 */*二叉查找树插入一批节点函数Insert_Batch_Node_STree()mE递归算法 参数描述：BTNode *head:二叉查找树的根节点指针int array:被插入的数据域数组intn:被插入的节点数目*/void Insert_Batch_Node_STree(BTNode *head,int array,int n)int i;for(i=0;in;i+)if(!Insert_Node_STree(head,arrayi)printf(n插入失败lchild；/ 将p移到其左孩子结点x / p=S
23、TACKltop)； flag=STACK2top-； if(flag=0) STACKl+top=p；/，当前p所指结点的地址进栈。/STACK2toP=1；/标志 1 进栈/p=p-rchild；/ x将p移到其右孩子结点o / else VISIT(p)；/ x访问当前p所指的结点x /p=NULL； while(p!=NULLtttop!=-1)；不难分析，上述算法的时间复杂度同样为O(n)7. 6. 3二叉树的线索化算法对-X树的线索化，就是把二叉树的二叉链表存储结构中结点的所有空指针域改造成指向某结点在某种遍历 序列中的直接前驱或直接后继的过程，因此，二叉树的线索化过程只能在对二叉
24、树的遍历过程中进行。-下面给出二叉树的中序线索化的递归算法。算法中设有指针pre，用来指向中序遍历过程中当前访问的结点 的直接前驱结点，pre的初值为头结点的指针；T初始时指向头结点，但在算法执行过程中，T总是指向当前访 问的结点。voldINTHREAD(TBTREET) (TBTREE pre；if(T!=Null)(INTHREAD(Tlchild)；if(Trchild=NULL)Trbit=0；if(Tlchild=NUll)；Tlchild=pre；Tlbit=0；if(prerbitc=0)prerchild=T ；pre=T ；inthread(T-rchild)； 平均查找长
25、度(AverageSearchLength)：确定一个元素在树中的位置所需要进行的比较次数的期望值。二叉树的内路径长度(InternalPathLength)：从二叉树根结点到某结点所经过的分支数目定义为该结点的路径 长度。二叉树中所有结点的路径长度之和定义为该二叉树的内路径长度IPL。图7。25(h)给出的二叉排序树的内路 径长度为IPL： 1X2+2X2+3X1+4X2=17二叉树的外路径长度(ExternalPathLength)：为了分析查找失败时的查找长度，在二叉树中出现空子树时，增 加新的空叶结点来代表这些空子树，从而得到一棵扩充后的二叉树。为了与扩充前的二叉树相区别，这些新增添
26、的空的叶结点用小方块代表，称之为外部结点，树中原有的结点为内部结点。图7. 27给出了一棵扩充后的二叉树，其外路径长度EPL是二叉树中所有外部结点的路径长度之和，即EPL=2X2+3X1+4X4+5X3 十 6X2=50教学内容：6.3.2线索二叉树1、如何记录一个结点的前趋和后继？每个结点增加两个域分别指向前趋和后继利用二叉链表中的空链域存放前趋和后继2、何谓线索二叉树？遍历二叉树的结果是，求得结点的一个线性序列例如先序序列：A B C D E F G H K中序序列：B D C A H G K F E后序序列： D C B H K G F E A定义：增加了线索的二叉树称为线索二叉树。对一
27、棵二叉树以某种遍历使其变成线索二叉树的过程称为线索化。线索二叉树存储我们知道，在有n个结点的二叉链表中共有2n个链域，但只有n-1个有用非空链域， 其余n+1个链域是空的。我们可以利用剩下的n+1个空链域来存放遍历过程中结点的前驱 和后继信息。现作如下规定：若结点有左子树，则其LChild域指向其左孩子，否则LChild 域指向其前驱结点；若结点有右子树，则其RChild域指向其右孩子，否则RChild域指向 其后继结点。为了区分孩子结点和前驱、后继结点，为结点结构增设两个标志域Ltag和 Rtag。当Ltag、Rtag等于0时，表示lchild域指示结点的左儿子或rchild域指示结点的右
28、孩子；当Ltag、Rtag等于1时，表示lchild域指示结点的左前驱或rchild域指示结点的 后驱；线索二叉树的存储结构Typedef struct BiThrNode TelemTypedata;struct BiTreeNode *Lchild , *Rchild;intLtag , Rtag ;BiTreeNode,*BiTree;3、线索链表的遍历算法中序扫描算法1）找到线索二叉树的根结点2）找到第一个要访问的结点（沿其左分支）3）访问左子树为空的结点4）沿其右线索访问其后继结点，if后继结点的Rtag=1则转4）,否则转1）void midoBTree （ BiTree T ）中
29、序遍历线索二叉树BiTree P ;P = T-Lchild; / p指向根结点while ( p!=T ) /空树或遍历结束时，p=Twhile ( p -LTag = =0 ) p = p- Lchild ; / 第一个结点visit ( p -data );while (p -Rtag = =1 & p -rchild !=T ) p = p -Rchild;Visit(p -data); /访问后继结点p= p-Rchild; / p进至其右子树根return OK;4、如何建立线索链表在中序遍历过程中修改结点的左、右指针域，以保存当前访问结点的“前驱”和“后继” 信息。遍历过程中，附
30、设指针pre,并始终保持指针pre指向当前访问的、指针p所指结点 的前驱。算法：为P的左子树线索化建立P的前趋线索建立q的后继线索为P的右子树线索化中序遍历二叉树使其线索化void crt_inthlinked ( Bitree T , Bitree head ) Bitree p, q ;head=(BiThrTree) malloc (sizeof( BiThrNode);head-Ltag = 0 ; head-Rtag = 0 ;head-Rchild=head;if ( T= = Null ) head-Lchild=head;else head-Lchild = T ; q = h
31、ead ; inthread ( T );q-Rchil=head; q-Rtag=1; / 添 加 头 结 点 head-Rchild=q; return OK/*中序遍历线索化以P为根的二叉树，且q为p的前趋*/void crt_inthlinked ( Bitree T , Bitree head ) Bitree p, q ;head=(BiThrTree) malloc (sizeof( BiThrNode);head-Ltag = 0 ; head-Rtag = 0 ;head-Rchild=head;if ( T= = Null ) head-Lchild=head;else h
32、ead-Lchild = T ; q = head ; inthread ( T );q-Rchil=head; q-Rtag=1; / 添加头结点 head-Rchild=q;return OK/*中序遍历线索化以P为根的二叉树，且q为p的前趋void inthread ( Bitree P ) if ( p!=null) inthread ( p-Lchild) ; / 左子树线索化if ( p-Lchild = = null) / 建前驱线索 p-Ltag=1; p-Lchild=q if ( q-Rchild = = null) / 建后继线索 q-Rtag=1; q-Rchild=p
33、 q = p ; /保持q指向p的前驱inthread ( p-Rchild) ; / 右子树线索化第6章 树和二叉树（参考答案）6.1根结点a6.2三个结点的树的形态:(1)三个结点的二叉树的形态:(1)(2)(4)(5)6. 3设树的结点数是n,则n=n0+n1+n2+nm+设树的分支数为B,有n=B+1n=1n1+2n2+mnm+1由(1)和(2)有：n0=n2+2n3+ (m-1)nm+16.4(1) ki-1 (i 为层数)(2) (n-2)/k+1(3) (n-1)*k+i+1(n-1)%k !=0;其右兄弟的编号n+16.5 (1)顺序存储结构1234567(1)(2)89101
34、1121314ABCD#EF#G#H注：#为空结点6.6(1) 前序 ABDGCEFH(2) 中序 DGBAECHF(3) 后序 GDBEHFCA6.7(1) 空二叉树或任何结点均无左子树的非空二叉树(2) 空二叉树或任何结点均无右子树的非空二叉树(3) 空二叉树或只有根结点的二叉树6.8int height(bitree bt)/ bt是以二叉链表为存储结构的二叉树，本算法求二叉树bt的高度 int bl,br; /局部变量，分别表示二叉树左、右子树的高度 if (bt=null) return(0);else bl=height(bt-lchild);br=height(bt-rchild
35、);return(blbr? bl+1: br+1); /左右子树高度的大者加1 (根) /算法结束6.9void preorder(cbt,int n,int i);/ cbt是以完全二叉树形式存储的n个结点的二叉树，i是数/组下标，初始调用时为1。本算法以非递归形式前序遍历该二叉树 int i=1,s,top=0; / s是栈，栈中元素是二叉树结点在cbt中的序号/ top是栈顶指针，栈空时top=0if (n=0) printf( “输入错误”)；exit(0)； while (i0) while(i=n)visit(cbti); / 访问根结点if (2*i+10) i=stop-;
36、/退栈，先序访问右子树 / END OF while (i0)/算法结束 以下是非完全二叉树顺序存储时的递归遍历算法，“虚结点”用*表示 void preorder(bt,int n,int i);/ bt是以完全二叉树形式存储的一维数组，n是数组元素个数。i是数/组下标，初始调用时为1。 if (idata!=T2-data) return(0);/ 根结点值不等else return(equal(T1-lchild,T2-lchild)&equal(T1-rchild,T2-rchild) /判左右子树等价 /算法结束6. 11void levelorder (bitree ht);本算法按层次遍历二叉树htif (ht!=null)initqueue(q);处始化队列，队列元素为二叉树结点的指针enqueue(q,ht);根结点指针入队列while (!empty(q) p=delqueue(q);visit(p); /访问结点if (p-lchild!=null) enqueue (q,p-lchild);/若左子女非空
