内容字号:默认大号超大号

段落设置:段首缩进取消段首缩进

字体设置:切换到微软雅黑切换到宋体

首页 > 电脑技术 > 正文

已知一棵二叉树的前序和中序遍历结果,输出后序

2018-10-10 出处:网络 整理:zhishizhan.net

    话题:已知一棵二叉树的前序和中序遍历结果,输出后序遍历结果。哪位同学

    回答:首先明确:一颗二叉树的前序遍历=根节点+左子树前序遍历 +右子树前序遍历 一颗二叉树的中序遍历=左子树中序遍历+根节点+右子树中序遍历 那么从前序遍历中取第一个点,就是根节点,知道了根节点,就可以找到中序遍历中跟节点的位置,那么就可以在中序遍历中找到左子树和右子树。 program tree(input, output); var s1, s2 : string; procedure try(l1, r1, l2, r2 : integer); {制造前序遍历为s1[l1] 至 s1[r1],中序遍历为s2[l2] 至s2[r2]的树 } var m : integer; begin m := pos(s1[l1], s2); {s1[l1]就是根节点,那么就可以在中序遍历s2中找到根节点,m就是根节点在 中序遍历中的位置,根节点m前面的是左子树的中序遍历,后面的是右子树的中序遍历} if m gt; l2 then try(l1 + 1, l1 + m - l2, l2, m - 1); {递归处理左子树} if m lt; r2 then try(l1 + m - l2 + 1, r1, m + 1, r2); {递归处理右子树} write(s1[l1]) {输出当前根节点} end; begin readln(s1); readln(s2); try(1, length(s1), 1, length(s2)); {一开始是对整个s1(前序遍历),整个s2(后续遍历)进行处理} writeln end. 可以画个图看看,会明白的。 祝lz学业有成!

    参考回答://如果有不懂的可以hi我 #includelt;stdio.hgt; #includelt;stdlib.hgt; typedef struct tnode { char data; struct tnode *lchild; struct tnode *rchild; }tnode; tnode *Tree_creat(tnode *t) { char ch; ch=getchar(); if(ch==' ') t=NULL; else { if(!(t=(tnode *)malloc(sizeof(tnode)))) printf("Error!"); t-gt;data=ch;//printf("[%c]",t-gt;data); t-gt;lchild=Tree_creat(t-gt;lchild); t-gt;rchild=Tree_creat(t-gt;rchild); } return t; } void preorder(tnode *t) { if(t!=NULL) { printf("%c ",t-gt;data); preorder(t-gt;lchild); preorder(t-gt;rchild); } } void main() { tnode *t=NULL; t=Tree_creat(t); preorder(t); }已知一棵二叉树的前序和中序遍历结果,输出后序

    话题:输入二叉树的前序和中序遍历结果,输出后序遍历结果 C#

    回答:#include#includetypedef struct node *tree_pointer;struct node{char ch;tree_pointer left_child,right_child;};tree_pointer tree=NULL;char preorder[20],inorder[20];void postorder(tree_pointer ptr){if(ptr){postorder(ptr-gt;left_child);postorder(ptr-gt;right_child);printf("%c",ptr-gt;ch);}}tree_pointer create(int in_start,int in_end,int pre_start,int pre_end){int left_in_start,left_in_end,right_in_start,right_in_end;int left_pre_start,left_pre_end,right_pre_start,right_pre_end;int i;tree_pointer root=NULL;if(pre_endgt;=pre_start){root=(tree_pointer)malloc(sizeof(node));for(i=in_start;ilt;=in_end;i++){if(preorder[pre_start]==inorder[i])break;}left_in_start=in_start;left_in_end=i-1;right_in_start=i+1;right_in_end=in_end;left_pre_start=pre_start+1;left_pre_end=left_pre_start+(left_in_end-left_in_start);right_pre_start=left_pre_end+1;right_pre_end=pre_end;root-gt;left_child=create(left_in_start,left_in_end,left_pre_start,left_pre_end);root-gt;right_child=create(right_in_start,right_in_end,right_pre_start,right_pre_end);root-gt;ch=preorder[pre_start];return root;}return NULL;}void main(){int count=0;printf("请输入二叉树的前序遍历(字符型,且两结点间无空格,回车表输入完毕):\n");while((preorder[count]=getchar())!='\n')count++;printf("请输入二叉树的中序遍历(字符型,且两结点间无空格,回车表输入完毕):\n");count=0;while((inorder[count]=getchar())!='\n')count++;tree=create(0,count-1,0,count-1);printf("二叉树的后序遍历为:");postorder(tree);printf("\n");}

    话题:用树的前序遍历和中序遍历可以导出树的后序遍历?

    回答:是的:一个二叉树的前序遍历是abdgcefh,中序遍历是dgbaechf,可以得到后序遍历是gdbehfca

    参考回答:展开全部是的:一个二叉树的前序遍历是abdgcefh,中序遍历是dgbaechf,可以得到后序遍历是gdbehfca

    话题:求C语言编译程序:从键盘输入某一二叉树前序遍历及中序遍历序列,

    回答:输入树的节点,输入0结束1 2 3 4 5 6 7 8 9 0中序打印1-2-3-4-5-6-7-8-9-后序打印9-8-7-6-5-4-3-2-1-前序打印1-2-3-4-5-6-7-8-9-////////////////////////////////////////////////////////////////////////////////////////// #include #include typedef struct tree { struct tree *left; int date; struct tree *right; }treenode,*b_tree; ///////按顺序入节点/////////////////////b_tree insert(b_tree root,int node){ b_tree newnode; b_tree currentnode; b_tree parentnode; newnode=(b_tree)malloc(sizeof(treenode)); newnode-date=node; newnode-right=NULL; newnode-left=NULL; if(root==NULL) return newnode; else { currentnode=root; while(currentnode!=NULL) { parentnode=currentnode; if(currentnode-datenode) currentnode=currentnode-left; else currentnode=currentnode-right; } if(parentnode-datenode) parentnode-left=newnode; else parentnode-right=newnode; } return root;} //////建立树///////////////////b_tree creat(int *date,int len){ b_tree root=NULL; int i; for(i=0;ileft); printf("%d-",root-date); print1(root-right);}}//////后序打印////////////////void print2(b_tree root){if(root!=NULL){ print2(root-left); print2(root-right); printf("%d-",root-date);}}//////前序打印////////////////void print3(b_tree root){if(root!=NULL){ printf("%d-",root-date); print3(root-left); print3(root-right);}}///////测试函数//////////////////void main(){ b_tree root=NULL; int i,index; int value; int nodelist[20]; printf("输入树的节点,输入0结束\n"); index=0; scanf("%d",value); while(value!=0) { nodelist[index]=value; index=index+1; scanf("%d",value); } root=creat(nodelist,index); printf("\n中序打印\n"); print1(root); printf("\n后序打印\n"); print2(root); printf("\n前序打印\n"); print3(root);}

    参考回答:#include using namespace std;struct BiNode{char data;BiNode *lchild, *rchild;};typedef BiNode *BiTree;int CreateBiTree(BiTree amp;T, const char *s1, const char *s2, int len){if (lenlt;=0){T = NULL;return 1;}else{T = new BiNode;T-gt;data = *s1;int i;for ( i=0; ilchild, s1+1, s2, i);CreateBiTree(T-gt;rchild, s1+i+1, s2+i+1, len-(i+1));}return 1;}int DestroyBiTree(BiTree amp;T){if (T==NULL) return 1;DestroyBiTree(T-gt;lchild);DestroyBiTree(T-gt;rchild);delete T;T = NULL;return 1;}int ATraverse(BiTree amp;T){if (T==NULL) return 1;ATraverse(T-gt;lchild);ATraverse(T-gt;rchild);coutlt;data;return 1;}main(){char a[2000],b[2000];while(cinab){BiTree T;int count=0;int n;for(n=0;a[n]!='\0';n++); CreateBiTree(T,a,b,n);ATraverse(T);coutlt;lt;" ";coutlt;lt;endl; DestroyBiTree(T); } }//用c++写的,主要因为没有分就不给你改成c了!

    话题:输入前序遍历和中序遍历,求后序遍历 (用pascal)

    回答:var s1,s2:string;procedure solve(s1,s2:string);var k:integer;beginif length(s1)=1 then write(s1)//s1长度为1就直接输出else begink:=pos(s1[1],s2);//s1[1]为根,k为当前根在中序遍历中的位置if kgt;1 then solve(copy(s1,2,k-1),copy(s2,1,k-1));//递归求解左子树if klt;length(s2) then solve(copy(s1,k+1,length(s1)-k),copy(s2,k+1,length(s2)-k));//递归求解右子树write(s2[k]);//后序遍历最后输出根end;end;beginreadln(s1);//前序遍历序列readln(s2);//中序遍历序列solve(s1,s2);//递归求解end.

    参考回答:Var first,mid:string;len:integer; procedure solve(first:string;spos_f,epos_f:integer;mid:string;spos_m,epos_m:integer);Var i,root_m:integer; Begin if spos_fgt;epos_f then exit; For i:=spos_m to epos_m do if first[spos_f]=mid[i] Then Begin root_m:=i;break;end; solve(first,spos_f+1,spos_f+(root_m-SPOS_M),mid,spos_m,root_m-1); solve(first,spos_f+(root_m-spos_m)+1,epos_f,mid,root_m+1,epos_m); write(first[spos_f]);end; Begin readln(first);readln(mid);solve(first,1,length(first),mid,1,length(mid));//递归求出后序遍厉end.已知一棵二叉树的前序和中序遍历结果,输出后序

    话题:输入先序遍历和中序遍历,输出后序遍历,打印出二叉树,用递归做,

    回答://先序遍历#include iostreamusing namespace std;struct TreeNode{ int val; TreeNode *left, *right;};//先序遍历void PreorderTraversal(TreeNode* root) { if (!root) return; cout root-val endl; if (root-left) PreorderTraversal(root-left); if (root-right) PreorderTraversal(root-right);}//中序遍历void InorderTraversal (TreeNode* root){ if (!root) return; if (root-left) InorderTraversal(root-left); cout root-val endl; if (root-right) InorderTraversal(root-right);}//后序遍历void PostorderTraversal (TreeNode* root){ if (!root) return; if (root-left) InorderTraversal(root-left); if (root-right) InorderTraversal(root-right); cout root-val endl;}int main(){ } 展开全部

    话题:用C实现:输入二叉树的前序和中序遍历,输出相应后序遍历和层次遍

    回答:/* ds7_1.c: 二叉树的创建、显示、查找、遍历、入 */ #include "stdio.h" #include "string.h" #define MAXSIZE 50 typedef struct node { char data; struct node *lchild; struct node *rchild; } REE; REE *tree; /* ================ */ void DispTree(REE *t,int level,char lr) { int i; if (t!= NULL) { for ( i = 1; i printf("%c -- %c\n",t-data,lr); DispTree(t-lchild,level+1,'L'); DispTree(t-rchild,level+1,'R'); } } /* ================ */ REE *LocateTree_DLR(REE *t, char ch) { REE *s; if (t-data == ch || t == NULL ) return (t); s = LocateTree_DLR ( t - lchild, ch ) ; if ( s != NULL ) return (s); else return ( LocateTree_DLR ( t - rchild , ch ) ) ; } /* ================ */ REE *CreateTree() { char ch[5]; REE *root, *s, *p; /* create boot */ gets(ch); strupr(ch); if (ch[0] == '#') return( NULL ); root = (REE *) malloc ( sizeof(REE)); root-data = ch[0]; root-lchild = NULL ; root-rchild = NULL ; gets(ch); strupr(ch); while ( ch[0]!= '#') { if ( LocateTree_DLR(root,ch[0]) == NULL ) { p = LocateTree_DLR(root, ch[1]); if (p == NULL ) printf("%c 位置结点不存在,重新输入!\n",ch[1]); else { if (ch[2] == 'L' p-lchild != NULL) printf("%c 位置不合理,重新输入!\n",ch[2]); else if (ch[2] == 'R' p-rchild != NULL) printf("%c 位置不合理,重新输入!\n",ch[2]); else { s = (REE *) malloc ( sizeof(REE)); s-data = ch[0]; s-lchild = NULL; s-rchild = NULL; if (ch[2] == 'L') p-lchild = s; else if (ch[2] == 'R') p-rchild = s; } } } else printf("%c 结点已存在,重新输入!\n", ch[0]); gets(ch); strupr(ch); } return (root); } /* ================ */ void TraversalTree_DLR(REE *t) { if (t != NULL) { printf("%c ", t - data); TraversalTree_DLR ( t - lchild ) ; TraversalTree_DLR ( t - rchild ) ; } } /* ================ */ void TraversalTree_LDR(REE *t) { if (t != NULL) { TraversalTree_LDR ( t - lchild ) ; printf("%c ", t - data); TraversalTree_LDR ( t - rchild ) ; } } /* ================ */ void TraversalTree_LRD(REE *t) { if (t != NULL) { TraversalTree_LRD ( t - lchild ) ; TraversalTree_LRD ( t - rchild ) ; printf("%c ", t - data); } } /* ================ */ int TreeInsertNode(REE **root, char key, char lr, char x) { REE *p, *q; if ( *root == NULL ) { (*root) = (REE *)malloc(sizeof(REE)); (*root) - data = x; (*root) - lchild = (*root) - rchild = NULL; return (1); } p = LocateTree_DLR(*root, key); if ( p == NULL ) return(0); q = (REE *)malloc(sizeof(REE)); q - data = x; if ( ( lr == 'L' p-lchild == NULL ) || ( lr == 'R' p-rchild == NULL ) ) { if (lr == 'L') p-lchild = q; else p-rchild = q; q - lchild = q - rchild = NULL ; } else { if (lr == 'L') { q - lchild = p - lchild; q - rchild = NULL; p - lchild = q; } else { q - rchild = p - rchild; q - lchild = NULL; p - rchild = q; } } return (1); } /* ================ */ main(){ tree = CreateTree(); DispTree(tree,0,'T'); TreeInsertNode(tree, 'C', 'L', 'Y'); DispTree(tree,0,'T'); printf("\n先序遍历: "); TraversalTree_DLR ( tree ) ; printf("\n中序遍历: "); TraversalTree_LDR ( tree ) ; printf("\n后序遍历: "); TraversalTree_LRD ( tree ) ; }

    话题:已知二叉树中序和后序遍历怎么求前序遍历遍历啊?

    回答:自己写个stack 我给你写的前后中写法吧。 前 MyStacklt;TreeNode *gt; stack; while(true) { while (lpCurNode) { if (lpfun!=NULL) { (this-gt;*lpfun)(lpCurNode); stack.Push(lpCurNode); } lpCurNode=lpCurNode-gt;m_lpLeft; } if (!stack.Pop(lpCurNode)) { break; } lpCurNode=lpCurNode订钉斥固俪改筹爽船鲸-gt;m_lpRight; } 中 MyStacklt;TreeNode *gt; stack; while (true) { while(lpCurNode) { stack.Push(lpCurNode); lpCurNode=lpCurNode-gt;m_lpLeft; } if (!stack.Pop(lpCurNode)) //出PUSH { break; } if (lpfun!=NULL) { (this-gt;*lpfun)(lpCurNode); //输出然后再if右边有没有值,有再进PUSH } lpCurNode=lpCurNode-gt;m_lpRight; } 后 MyStacklt;TreeNode *gt; stack; TreeNode* lpFang=NULL; while(true) { while(lpCurNode) { stack.Push(lpCurNode); lpCurNode=lpCurNode-gt;m_lpLeft; } if (!stack.Pop(lpCurNode)) { break; } if (lpCurNode-gt;m_lpRight==NULL||lpCurNode-gt;m_lpRight==lpFang) { lpFang=lpCurNode; if (lpfun!=NULL) { (this-gt;*lpfun)(lpCurNode); } lpCurNode=NULL; continue; } else stack.Push(lpCurNode); lpCurNode=lpCurNode-gt;m_lpRight; }

    话题:先序和中序建立二叉树,然后输出后序遍历,用C语言的

    回答:#define EL 10 #define TEL 2*EL+1 #define LEN sizeof(struct node) #include "stdio.h" #include "stdlib.h" char pre[TEL]="ABCDEFGHIJ"; char pin[TEL]="CBEDAGHFJI"; typedef struct node { char data; struct node * lch,*rch; }Node,*ree; Node root; ree rt=amp;root; int pos(char c,char s[],int st) {char *p; p=s+st; while(*p!=c amp;amp; *p!='\0') p++; return p-s; } void create(ree *t,int i1,int i2,int len) {int r,llen,rlen; if(lenlt;=0) *t=NULL; else {*t=(ree)malloc(LEN); (*t)-gt;data=pre[i1]; r=pos(pre[i1],pin,i2); llen=r-i2; rlen=len-(llen+1); create(amp;(*t)-gt;lch,i1+1,i2,llen); create(amp;(*t)-gt;rch,i1+llen+1,r+1,rlen); } } void travel(ree t) {if(t) {travel(t-gt;lch); travel(t-gt;rch); putchar(t-gt;data); } } int main() {create(amp;rt,0,0,EL); if(rt) travel(rt); }已知一棵二叉树的前序和中序遍历结果,输出后序

    话题:已知前序和中序,输出后序遍历

      回答:需要进一步解释吗?展开全部#include void fun(char* pcReadAt1, char* pcReadAt2, char* pcWriteAt, int iNumOf);int main(){ char s1[11], s2[11], s3[11] = "0123456789"; scanf("%s%s", s1, s2); fun(s1, s2, s3, 10); printf("%s\n", s3); return 0;}void fun(char* pcReadAt1, char* pcReadAt2, char* pcWriteAt, int iNumOf){ // 头节点 char cHead = *pReadAt1; int iNumOfLeft = 0; // 排错 if ( 0 != iNumOf ) { // 将头节点写在最后面 pWriteAt[iNumOf - 1] = cHead; if ( 1 != iNumOf ) { // 求头节点在中序中的位置 for ( iNumOfLeft = 0; cHead != pcReadAt2[iNumOfLeft]; ++iNumOfLeft ); // 对两个子树 fun( pcReadAt1 + 1, pcReadAt2, pcWriteAt, iNumOfLeft ); fun( pcReadAt1 + iNumOfLeft + 1, pcReadAt2 + iNumOfLeft + 1, pcWriteAt + iNumOfLeft, iNumOf - 1 - iNumOfLeft ); } } return;}

    分享给小伙伴们:

    相关文章

    搞笑图片