最近一段時間學習了數(shù)據結構中二叉樹的基本操作，包括二叉樹的結構、二叉樹的創(chuàng)建、遞歸先序中序后序遍歷、非遞歸遍歷等，想著把二叉樹的相關知識和自己的見解放到網上來讓網友看看是否正確，想和網友一起共同交流。

先了解一下二叉樹的三個基本性質：

性質1：在非空二叉樹中，第i層上至多有2i-1個結點(i≧1)。

性質2：深度為k的二叉樹至多有2k-1個結點（k≧1) 。

性質3：對任何一棵二叉樹，若其葉子結點數(shù)為n0，度為2的結點數(shù)為n2，則n0=n2+1。

二叉樹的存儲也是有兩種方式：順序存儲和鏈式存儲。

這里給出鏈式存儲的定義：包括一個數(shù)據域、一個左孩子、一個右孩子。

typedef int TElemType;
typedef struct BiTNode{
	TElemType data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

?要創(chuàng)建一個二叉樹，可以通過先序遍歷創(chuàng)建二叉樹的方法：

大體過程為：

1. 輸入根結點，判斷是否為-1（空），若為-1，則二叉樹為空，否則不為空。
2. 為其動態(tài)內存分配空間，輸入左子節(jié)點，因為是先序遍歷創(chuàng)建，要遵循根、左、右的順序，所以對左子節(jié)點再遞歸調用該函數(shù)直到NULL。
3. 再輸入右子節(jié)點，同理，用相同的方法對右子節(jié)點遞歸調用該函數(shù)直到NULL。

代碼如下：

void createBiTree(BiTree *t)
{
	//先序遍歷創(chuàng)建二叉樹 
	int e;
	scanf("%d",&e);
	if(e==-1)
		*t=NULL;//二叉樹為空
	else
	{
		*t=(BiTree)malloc(sizeof(BiTNode));//動態(tài)內存分配
		(*t)->data=e;
		printf("請輸入%d的左子節(jié)點的值：",e);
		createBiTree(&(*t)->lchild);
		printf("請輸入%d的右子節(jié)點的值：",e);
		createBiTree(&(*t)->rchild);
	}
}

?創(chuàng)建好一個二叉樹后，就要對他進行遍歷。

先序遍歷：

遞歸：?若二叉樹為空，則遍歷結束；否則

⑴ 訪問根結點；⑵ 先序遍歷左子樹(遞歸調用本算法)；⑶ 先序遍歷右子樹(遞歸調用本算法)。

非遞歸：若二叉樹為空，則返回；否則，令p=T；⑴ 訪問p所指向的結點；⑵ q=p->Rchild ，若q不為空，則q進棧；⑶ p=p->Lchild ，若p不為空，轉(1)，否則轉(4)；⑷? 退棧到p ，轉(1)，直到棧空為止。

中序遍歷：

遞歸：若二叉樹為空，則遍歷結束；否則⑴ 中序遍歷左子樹(遞歸調用本算法)；⑵ 訪問根結點；⑶ 中序遍歷右子樹(遞歸調用本算法)。

非遞歸：

若二叉樹為空，則返回；否則，令p=T⑴ 若p不為空，p進棧， p=p->Lchild ；⑵ 否則(即p為空)，退棧到p，訪問p所指向的結點；⑶ p=p->Rchild ，轉(1)；直到?？諡橹?。

后序遍歷：

遞歸：??若二叉樹為空，則遍歷結束；否則⑴ 后序遍歷左子樹(遞歸調用本算法)；⑵ 后序遍歷右子樹(遞歸調用本算法) ；⑶ 訪問根結點 。

非遞歸：若二叉樹為空，則返回；否則，令p=T；⑴ 第一次經過根結點p，不訪問；p進棧S1 ， tag 賦值0，進棧S2，p=p->Lchild 。⑵ 若p不為空，轉(1)，否則，取狀態(tài)標志值tag ：?⑶ 若tag=0：對棧S1，不訪問，不出棧；修改S2棧頂元素值(tag賦值1) ，取S1棧頂元素的右子樹，即p=S1[top]->Rchild ，轉(1)；⑷ 若tag=1：S1退棧，訪問該結點；

直到?？諡橹?。

遞歸先序遍歷的代碼如下：

void PreOrderTraverse(BiTree t)
{
	//遞歸先序遍歷 
	if(t!=NULL)
	{
		printf("%d",t->data);
		PreOrderTraverse(t->lchild);
		PreOrderTraverse(t->rchild);
	}
}

?遞歸中序遍歷的代碼如下：

void InOrderTraverse(BiTree t)
{
	//遞歸中序遍歷 
	if(t!=NULL)
	{
		InOrderTraverse(t->lchild);
		printf("%d",t->data);
		InOrderTraverse(t->rchild);
	}
}

遞歸后序遍歷的代碼如下：

void PostOrderTraverse(BiTree t)
{
	//遞歸后序遍歷
	if(t!=NULL)
	{
		PostOrderTraverse(t->lchild);
		PostOrderTraverse(t->rchild);
		printf("%d",t->data);
	} 
}

?整體過程就是這樣，要想實際測試，完整代碼如下：

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 200
typedef int TElemType;
typedef struct BiTNode{
	TElemType data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
void createBiTree(BiTree *t)
{
	//先序遍歷創(chuàng)建二叉樹 
	int e;
	scanf("%d",&e);
	if(e==-1)
		*t=NULL;
	else
	{
		*t=(BiTree)malloc(sizeof(BiTNode));
		(*t)->data=e;
		printf("請輸入%d的左子節(jié)點的值：",e);
		createBiTree(&(*t)->lchild);
		printf("請輸入%d的右子節(jié)點的值：",e);
		createBiTree(&(*t)->rchild);
	}
}
void PreOrderTraverse(BiTree t)
{
	//遞歸先序遍歷 
	if(t!=NULL)
	{
		printf("%d",t->data);
		PreOrderTraverse(t->lchild);
		PreOrderTraverse(t->rchild);
	}
}
void InOrderTraverse(BiTree t)
{
	//遞歸中序遍歷 
	if(t!=NULL)
	{
		InOrderTraverse(t->lchild);
		printf("%d",t->data);
		InOrderTraverse(t->rchild);
	}
}
void PostOrderTraverse(BiTree t)
{
	//遞歸后序遍歷
	if(t!=NULL)
	{
		PostOrderTraverse(t->lchild);
		PostOrderTraverse(t->rchild);
		printf("%d",t->data);
	} 
}
void aPreOrderTraverse(BiTree t)
{
	//非遞歸先序遍歷
	BiTree stack[MAXSIZE];
	int top=0;
	if(t==NULL)
		return;
	BiTree p=t;
	while(!(p==NULL&&top==0))
	{
		while(p)
		{
			printf("%d",p->data);//先訪問根結點 
			stack[top]=p;//將p入棧 
			top++;
			p=p->lchild;//p指向左孩子 
		}
		if(top<=0)return;
		else
		{
			top--;
			p=stack[top];
			p=p->rchild;//p指向右孩子 
		}	
	} 
}
int main()
{
	BiTree t;
	printf("請輸入根節(jié)點的值：");
	createBiTree(&t);
	printf("遞歸先序遍歷二叉樹為：");
	PreOrderTraverse(t);
	printf("\n");
	printf("遞歸中序遍歷二叉樹為：");
	InOrderTraverse(t);
	printf("\n");
	printf("遞歸后序遍歷二叉樹為：");
	PostOrderTraverse(t);
	printf("\n"); 
	printf("非遞歸先序遍歷二叉樹為：");
	aPreOrderTraverse(t);
	printf("\n");
}

測試結果如下：

測試的二叉樹為：

?結果為：

如果有不正確或者能夠更好的地方，歡迎大家多多指教！文章來源地址http://www.zghlxwxcb.cn/news/detail-761548.html

到了這里，關于【數(shù)據結構】二叉樹的創(chuàng)建和遍歷（先序、中序、后序）的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！