題目描述
樹形結構是一類重要的非線性數據結構，其中以樹和二叉樹最為常用。對於每一個結點至多只有兩課子樹的一類樹，稱其為二叉樹。二叉樹的鏈式存儲結構是一類重要的數據結構，其形式定義如下：
而二叉樹的前序、中序遍歷是非常重要的能夠訪問二叉樹所有結點的算法，下面分別列出一種先序遍歷和兩種中序遍歷的算法。
第一種中序遍歷的方法（算法6.3）：
第二種中序遍歷的方法（算法6.2）：
通過讀入一個字符串，建立二叉樹的算法如下：
在本題中，將會給出一個按照先序遍歷得出的字符串，空格代表空的子節點，大寫字母代表節點內容。請通過這個字符串建立二叉樹，並按照題目描述中的一種先序遍歷和兩種中序遍歷的算法分別輸出每一個非空節點。
輸入
輸入只有一行，包含一個字符串S，用來建立二叉樹。保證S為合法的二叉樹先序遍歷字符串，節點內容只有大寫字母，且S的長度不超過100。www.2cto.com
輸出
共有三行，每一行包含一串字符，表示分別按先序、中序、中序得出的節點內容，每個字母後輸出一個空格。請注意行尾輸出換行。
樣例輸入
ABC DE G F
樣例輸出
A B C D E G F
C B E G D F A
C B E G D F A
提示 [+]
*** 提示已隱藏，點擊上方 [+] 可顯示 ***
來源
數據結構算法教學題
[cpp]
/*********************************
* 日期：2013-3-7
* 作者：SJF0115
* 題號: 天勤OJ 題目1485: 二叉鏈表存儲的二叉樹
* 來源：http://acmclub.com/problem.php?id=1485
* 結果：AC
* 來源：數據結構算法教學題
* 總結：
**********************************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char array[101];
//二叉樹結點
typedef struct BiTNode{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//按先序序列創建二叉樹
int CreateBiTree(BiTree &T,int &index,int &n){
if(index >= n){
return 0;
}
//按先序次序輸入二叉樹中結點的值（一個字符），空格表示空樹
if(array[index] == ' '){
T = NULL;
index++;
}
else{
T = (BiTree)malloc(sizeof(BiTNode));
//生成根結點
T->data = array[index];
index++;
//構造左子樹
CreateBiTree(T->lchild,index,n);
//構造右子樹
CreateBiTree(T->rchild,index,n);
}
return 0;
}
//輸出
void Visit(BiTree T){
printf("%c ",T->data);
}
//先序遍歷
void PreOrder(BiTree T){
if(T != NULL){
//訪問根節點
Visit(T);
//訪問左子結點
PreOrder(T->lchild);
//訪問右子結點
PreOrder(T->rchild);
}
}
//中序遍歷
void InOrder(BiTree T){
if(T != NULL){
//訪問左子結點
InOrder(T->lchild);
//訪問根節點
Visit(T);
//訪問右子結點
InOrder(T->rchild);
}
}
//後序遍歷
void PostOrder(BiTree T){
if(T != NULL){
//訪問左子結點
PostOrder(T->lchild);
//訪問右子結點
PostOrder(T->rchild);
//訪問根節點
Visit(T);
}
}
int main()
{
int len,index;
while(gets(array)){
BiTree T;
len = strlen(array);
index = 0;
//創建二叉樹
CreateBiTree(T,index,len);
//先序遍歷
PreOrder(T);
printf("\n");
//中序遍歷
index = 0;
InOrder(T);
printf("\n");
//中序遍歷
index = 0;
InOrder(T);
printf("\n");
}
return 0;
}
/*********************************
* 日期：2013-3-7
* 作者：SJF0115
* 題號: 天勤OJ 題目1485: 二叉鏈表存儲的二叉樹
* 來源：http://acmclub.com/problem.php?id=1485
* 結果：AC
* 來源：數據結構算法教學題
* 總結：
**********************************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char array[101];
//二叉樹結點
typedef struct BiTNode{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//按先序序列創建二叉樹
int CreateBiTree(BiTree &T,int &index,int &n){
if(index >= n){
return 0;
}
//按先序次序輸入二叉樹中結點的值（一個字符），空格表示空樹
if(array[index] == ' '){
T = NULL;
index++;
}
else{
T = (BiTree)malloc(sizeof(BiTNode));
//生成根結點
T->data = array[index];
index++;
//構造左子樹
CreateBiTree(T->lchild,index,n);
//構造右子樹
CreateBiTree(T->rchild,index,n);
}
return 0;
}
//輸出
void Visit(BiTree T){
printf("%c ",T->data);
}
//先序遍歷
void PreOrder(BiTree T){
if(T != NULL){
//訪問根節點
Visit(T);
//訪問左子結點
PreOrder(T->lchild);
//訪問右子結點
PreOrder(T->rchild);
}
}
//中序遍歷
void InOrder(BiTree T){
if(T != NULL){
//訪問左子結點
InOrder(T->lchild);
//訪問根節點
Visit(T);
//訪問右子結點
InOrder(T->rchild);
}
}
//後序遍歷
void PostOrder(BiTree T){
if(T != NULL){
//訪問左子結點
PostOrder(T->lchild);
//訪問右子結點
PostOrder(T->rchild);
//訪問根節點
Visit(T);
}
}
int main()
{
int len,index;
while(gets(array)){
BiTree T;
len = strlen(array);
index = 0;
//創建二叉樹
CreateBiTree(T,index,len);
//先序遍歷
PreOrder(T);
printf("\n");
//中序遍歷
index = 0;
InOrder(T);
printf("\n");
//中序遍歷
index = 0;
InOrder(T);
printf("\n");
}
return 0;
}
