任務描述

設二叉樹中每個結(jié)點的元素均為一個字符，按先序遍歷的順序建立二叉鏈表，編寫三個遞歸算法分別實現(xiàn)二叉樹的先序、中序和后序遍歷。

編程要求

輸入

多組數(shù)據(jù)。每組數(shù)據(jù)一行，為二叉樹的前序序列（序列中元素為‘0’時，表示該結(jié)點為空）。當輸入只有一個“0”時，輸入結(jié)束。

輸出

每組數(shù)據(jù)輸出三行，為二叉樹的先序、中序和后序序列。

測試說明

平臺會對你編寫的代碼進行測試：

測試輸入： abcd00e00f00ig00h00 abd00e00cf00g00 0

預期輸出： abcdefigh dcebfagih decfbghia abdecfg dbeafcg debfgca

來源

BJFUOJ

開始你的任務吧，祝你成功！

注：從微信或notepad++粘貼代碼，似乎可能含有不可見字符，會導致stray報錯

在C語言中，stray錯誤（stray error）是指在代碼中出現(xiàn)了一個無效或意外的字符。這通常是由于拼寫錯誤、格式錯誤、錯誤的符號或其他編碼錯誤引起的。當編譯器無法識別這些字符時，它會生成stray錯誤。

復制粘貼代碼可能導致stray錯誤。當從網(wǎng)頁或其他文本編輯器中復制代碼并粘貼到代碼編輯器中時，有時會出現(xiàn)格式問題，其中包括不可見的字符或額外的空格。這些不可見的字符或額外的空格可能會導致編譯器產(chǎn)生stray錯誤。文章來源地址http://www.zghlxwxcb.cn/news/detail-768070.html

#include<iostream>
#include<string.h>
using namespace std;
int flag;
typedef struct BiTNode
{
	char data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
void CreateBiTree(BiTree &T,char S[],int &i)
{//先序建立二叉樹
	if(S[i]=='0')
		T=NULL;
	else
	{
		T=new BiTNode;
		T->data=S[i];
		CreateBiTree(T->lchild,S,++i);
		CreateBiTree(T->rchild,S,++i);
	}
}
void PreOrderTraverse(BiTree T)
{//二叉樹的先序遍歷
/**************begin************/
	
 if(T)
  {
	cout<<T->data;
    PreOrderTraverse(T->lchild);
    PreOrderTraverse(T->rchild);
  }

    /**************end************/
}
void InOrderTraverse(BiTree T)
{//二叉樹的中序遍歷
/**************begin************/

if(T)
{
 InOrderTraverse(T->lchild);
 cout<<T->data;
 InOrderTraverse(T->rchild);
}


    /**************end************/
}
void PostOrderTraverse(BiTree T)
{//二叉樹的后序遍歷
/**************begin************/


if(T)
  {
    PostOrderTraverse(T->lchild);
    PostOrderTraverse(T->rchild);
	cout<<T->data;
  }


    /**************end************/
}
int main()
{
	char S[100];
	while(cin>>S)
	{
		if(strcmp(S,"0")==0) break;
		int i=-1;
	  	BiTree T;
		CreateBiTree(T,S,++i);
		PreOrderTraverse(T);
		cout<<endl;
  	    InOrderTraverse(T);
		cout<<endl;
		PostOrderTraverse(T);
		cout<<endl;
	}
	return 0;
}

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)：二叉樹：第3關(guān)：基于二叉鏈表的二叉樹的遍歷的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！