求二叉樹的先序遍歷

Time Limit: 1000ms?? Memory limit: 65536K??有疑問？點這里^_^

題目描述

已知一棵二叉樹的中序遍歷和后序遍歷，求二叉樹的先序遍歷

輸入

輸入數據有多組，第一行是一個整數t (t<1000)，代表有t組測試數據。每組包括兩個長度小于50 的字符串，第一個字符串表示二叉樹的中序遍歷序列，第二個字符串表示二叉樹的后序遍歷序列。?

輸出

輸出二叉樹的先序遍歷序列

示例輸入

2 dbgeafc dgebfca lnixu linux

示例輸出

abdegcf xnliu

仔細想如何尋找左右子數在三種序列中的開始位置地址

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct node
{
??? char data;
??? struct node *left,*right;
};
struct node *creat(int n,char *str1,char *str2)
{
??? struct node *root;
??? int i;
??? if(n==0)
??????? return NULL;
??? root=(struct node *)malloc(sizeof(struct node ));
??? root->data=str2[n-1];//找到根節點
??? printf("%c",root->data);
??? for(i=0;i<n;i++)//找到str1中的根節點的位置
??? {
??????? if(str1[i]==str2[n-1])
??????????? break;
??? }
??? root->left=creat(i,str1,str2);//（左子樹的長度，str1中左子樹開始位置的地址，str2中左子樹開始位置的地址）
??? root->right=creat(n-i-1,str1+i+1,str2+i);//（右子樹的長度，str1中右子樹開始位置的地址，str2中右子樹開始位置的地址）
??? return root;
};
int main()
{
??? int n,len;
??? char str1[100],str2[100];
??? scanf("%d",&n);
??? while(n--)
??? {
??????? memset(str1,0,sizeof(str1));
??????? memset(str2,0,sizeof(str2));
??????? scanf("%s",str1);
??????? scanf("%s",str2);
??????? len=strlen(str1);
??????? creat(len,str1,str2);
??????? printf("\n");
??? }
??? return 0;
}

轉載于:https://www.cnblogs.com/jiangyongy/p/3971662.html

總結

以上是生活随笔為你收集整理的【1489】求二叉树的先序遍历 SDUTOJ的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。