程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> 二叉樹先序、中序、後序遍歷的遞歸算法和非遞歸算法，二叉樹遞歸

二叉樹先序、中序、後序遍歷的遞歸算法和非遞歸算法，二叉樹遞歸

編輯：關於C語言

二叉樹先序、中序、後序遍歷的遞歸算法和非遞歸算法，二叉樹遞歸

先序遍歷：若二叉樹為空，則空操作；否則訪問根節點；先序遍歷左子樹；先序遍歷右子樹。

中序遍歷：若二叉樹為空，則空操作；否則中序遍歷左子樹；訪問根節點；中序遍歷右子樹。

後序遍歷：若二叉樹為空，則空操作；否則後序遍歷左子樹；後序遍歷右子樹；訪問根節點。

二叉鏈表：鏈表中的結點包含三個域：數據域和左右指針域。

三叉鏈表：在二叉鏈表的基礎上增加指向雙親結點的指針域。

以下代碼均使用二叉鏈表。

//二叉樹的二叉鏈表存儲表示
typedef char TElemType;
typedef struct BiNode
{
	TElemType data;
	struct BiNode *lchild, *rchild;
} BiNode , *BiTree;

1. 生成二叉樹

可以在遍歷過程中生成結點，建立二叉樹的存儲結構。按先序序列建立二叉樹的二叉鏈表的算法如下：

/* 
 * 按先序次序輸入二叉樹中結點的值(一個字符)，空格字符表示空樹，構造二叉鏈表表示的二叉樹T。
 */
Status CreatBiTree(BiTree *T)
{
	char ch;
	scanf("%c", &ch);

	//如果當前輸入的字符為空格，則(*T)指向空樹。
	if (ch == ' ')
	{
		(*T) = NULL;
	}
	else
	{
		if (!((*T) = (BiTree)malloc(sizeof(BiNode))))
			exit(OVERFLOW);
		(*T)->data = ch;				//生成根結點
		CreatBiTree(&((*T)->lchild));	//構造左子樹
		CreatBiTree(&((*T)->rchild));	//構造右子樹
	}
	return OK;
}

假設輸入字符依次為ABC##DE#G##F###(#表示空格)，則生成的二叉樹如下所示：

2. 二叉樹遍歷遞歸算法

a. 先序遍歷

/*
 * 采用二叉鏈表存儲結構，Visit是對數據元素操作的應用函數，
 * 先序遍歷二叉樹T的遞歸算法，對每個數據元素調用函數Visit。
 */
Status PreOrderTraverse_Recursive(BiTree T, Status(*Visit)(TElemType e))
{
	if (T)
	{
		if (Visit(T->data))
			if (PreOrderTraverse_Recursive(T->lchild, Visit))
				if (PreOrderTraverse_Recursive(T->rchild, Visit))
					return OK;
		return ERROR;	//函數不會執行到這一步，不會返回Error。這樣寫只是為了沒有編譯警告。
	}
	else
		return OK;	//當T為空樹時，停止遞歸。
}

b. 中序遍歷

Status InOrderTraverse_Recursive(BiTree T, Status(*Visit)(TElemType e))
{
	if (T)
	{
		if (InOrderTraverse_Recursive(T->lchild, Visit))
			if (Visit(T->data))
				if (InOrderTraverse_Recursive(T->rchild, Visit))
					return OK;
		return ERROR;
	}
	else
		return OK;
}

c. 後序遍歷

Status PostOrderTraverse_Recursive(BiTree T, Status(*Visit)(TElemType e))
{
	if (T)
	{
		if (PostOrderTraverse_Recursive(T->lchild, Visit))
			if (PostOrderTraverse_Recursive(T->rchild, Visit))
				if (Visit(T->data))
					return OK;
		return ERROR;
	}
	else
		return OK;
}

3. 二叉樹遍歷非遞歸算法

a. 先序遍歷

/*
 * 先序遍歷二叉樹，非遞歸算法。
 */
Status PreOrderTraverse_NonRecursive(BiTree T, Status(*Visit)(TElemType e))
{
	Stack *S;	//棧S中存儲指向樹結點的指針。
	BiTree p;
	S = (Stack*)malloc(sizeof(Stack));
	InitStack(S);
	Push(S, T);	//根指針進棧。
	while (!StackEmpty(S))
	{
		//獲取棧頂指針，如果棧頂指針不為空，訪問該結點。並將該結點的左子樹進棧。
		if (GetTop(S, &p) && p)
		{
			if (!Visit(p->data))
				return ERROR;
			Push(S, p->lchild);
		}
		//棧頂指針為空，表明之前壓入的左子樹或者右子樹為空。
		else
		{
			Pop(S, &p);	//空指針退棧
			if (!StackEmpty(S))
			{
				Pop(S, &p); //已被訪問過的根結點退棧。此時，該退棧結點的左子樹已被全部訪問過。
				Push(S, p->rchild);	//右子樹進棧。
			}
		}
	}
	return OK;
}

b. 中序遍歷

/* 
 * 采用二叉鏈表存儲結構，Visit是對數據元素進行操作的應用函數，
 * 中序遍歷二叉樹的非遞歸算法，對每個數據元素調用函數Visit。
 */
Status InOrderTraverse_NonRecursive(BiTree T, Status(*Visit)(TElemType e))
{
	Stack *S;
	BiTree p;
	S = (Stack *)malloc(sizeof(Stack));
	InitStack(S);
	Push(S, T);	//根指針進棧
	while (!StackEmpty(S))
	{
		//向左走到盡頭
		while (GetTop(S, &p) && p)
		{
			Push(S, p->lchild);
		}

		//空指針退棧
		Pop(S, &p);

		//訪問節點，並向右一步
		if (!StackEmpty(S))
		{
			Pop(S, &p);
			if (!Visit(p->data))
				return ERROR;
			Push(S, p->rchild);
		}
	}
	return OK;
}

或者

/*
 * 采用二叉鏈表存儲結構，Visit是對數據元素進行操作的應用函數，
 * 中序遍歷二叉樹的非遞歸算法，對每個數據元素調用函數Visit。
 */
Status InOrderTraverse_NonRecursive_2(BiTree T, Status(*Visit)(TElemType e))
{
	Stack *S;
	BiTree p = T;
	S = (Stack *)malloc(sizeof(Stack));
	InitStack(S);

	while (p || !StackEmpty(S))
	{
		//根指針進棧，遍歷左子樹
		if (p)
		{
			Push(S, p);
			p = p->lchild;
		}
		//根指針退棧，訪問根結點，遍歷右子樹
		else
		{
			Pop(S, &p);
			if (!Visit(p->data))
				return ERROR;
			p = p->rchild;
		}
	}
	return OK;
}

c. 後序遍歷

/*
 * 後序遍歷二叉樹，非遞歸算法
 */
Status PostOrderTraverse_NonRecursive(BiTree T, Status(*Visit)(TElemType e))
{
	Stack *S;
	BiTree p, pre=NULL;//pre指向已訪問過的最後一個結點。
	S = (Stack*)malloc(sizeof(Stack));
	InitStack(S);
	Push(S, T);//根指針進棧

	while (!StackEmpty(S))
	{
		//獲取棧頂指針，如果當前結點有左子樹，並且左子樹結點不是剛被訪問的節點。如果當前結點有右子樹，並且右子樹結點不是剛被訪問的結點。
		//表明棧頂指針指向的樹結點未被訪問，且左子樹和右子樹均未被訪問。此時，將結點的左子樹進棧。
		if (GetTop(S, &p) && p->lchild && pre != p->lchild && !(p->rchild && pre == p->rchild))
			Push(S, p->lchild);
		//如果棧頂指針的右子樹存在，且未被訪問。則將右子樹進棧
		else if (p->rchild && pre != p->rchild)
			Push(S, p->rchild);
		//如果左子樹和右子樹均被訪問過，則結點退棧，並進行訪問。更新pre。
		else
		{
			Pop(S, &p);
			if (!Visit(p->data))
				return ERROR;
			pre = p;
		}
	}
	return OK;
}

4.測試完整代碼

/*
 * 假設輸入字符為：ABC##DE#G##F###，實際輸入時，#用空格代替。
 */
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

typedef int Status;
#define OK 1
#define ERROR 0
#define OVERFLOW -2

//二叉樹的二叉鏈表存儲表示
typedef char TElemType;
typedef struct BiNode
{
	TElemType data;
	struct BiNode *lchild, *rchild;
} BiNode , *BiTree;

//棧的順序存儲結構
#define STACK_INIT_SIZE 100      //存儲空間初始分配量
#define STACKINCREMENT 10       //存儲空間分配增量

typedef struct
{
	BiTree *base;
	BiTree *top;
	int stacksize;
} Stack;

//函數聲明
Status InitStack(Stack *S);
Status Push(Stack *S, BiTree p);
Status Pop(Stack *S, BiTree *p);
Status GetTop(Stack *S, BiTree *p);
Status StackEmpty(Stack *S);

Status CreatBiTree(BiTree *T);
Status PreOrderTraverse_Recursive(BiTree T, Status(*Visit)(TElemType e));
Status InOrderTraverse_Recursive(BiTree T, Status(*Visit)(TElemType e));
Status PostOrderTraverse_Recursive(BiTree T, Status(*Visit)(TElemType e));
Status PreOrderTraverse_NonRecursive(BiTree T, Status(*Visit)(TElemType e));
Status InOrderTraverse_NonRecursive(BiTree T, Status(*Visit)(TElemType e));
Status InOrderTraverse_NonRecursive_2(BiTree T, Status(*Visit)(TElemType e));
Status PostOrderTraverse_NonRecursive(BiTree T, Status(*Visit)(TElemType e));

Status PrintElement(TElemType e);

int main()
{
	BiTree T;
	CreatBiTree(&T);
	//先序
	PreOrderTraverse_Recursive(T, PrintElement); putchar('\n');
	PreOrderTraverse_NonRecursive(T, PrintElement); putchar('\n');
	//中序
	InOrderTraverse_Recursive(T, PrintElement); putchar('\n');
	InOrderTraverse_NonRecursive(T, PrintElement); putchar('\n');
	InOrderTraverse_NonRecursive_2(T, PrintElement); putchar('\n');
	//後序
	PostOrderTraverse_Recursive(T, PrintElement); putchar('\n');
	PostOrderTraverse_NonRecursive(T, PrintElement); putchar('\n');
	return 0;
}

/* 
 * 按先序次序輸入二叉樹中結點的值(一個字符)，空格字符表示空樹，構造二叉鏈表表示的二叉樹T。
 */
Status CreatBiTree(BiTree *T)
{
	char ch;
	scanf("%c", &ch);

	//如果當前輸入的字符為空格，則(*T)指向空樹。
	if (ch == ' ')
	{
		(*T) = NULL;
	}
	else
	{
		if (!((*T) = (BiTree)malloc(sizeof(BiNode))))
			exit(OVERFLOW);
		(*T)->data = ch;				//生成根結點
		CreatBiTree(&((*T)->lchild));	//構造左子樹
		CreatBiTree(&((*T)->rchild));	//構造右子樹
	}
	return OK;
}

/*
 * 采用二叉鏈表存儲結構，Visit是對數據元素操作的應用函數，
 * 先序遍歷二叉樹T的遞歸算法，對每個數據元素調用函數Visit。
 */
Status PreOrderTraverse_Recursive(BiTree T, Status(*Visit)(TElemType e))
{
	if (T)
	{
		if (Visit(T->data))
			if (PreOrderTraverse_Recursive(T->lchild, Visit))
				if (PreOrderTraverse_Recursive(T->rchild, Visit))
					return OK;
		return ERROR;	//函數不會執行到這一步，不會返回Error。這樣寫只是為了沒有編譯警告。
	}
	else
		return OK;	//當T為空樹時，停止遞歸。
}

Status InOrderTraverse_Recursive(BiTree T, Status(*Visit)(TElemType e))
{
	if (T)
	{
		if (InOrderTraverse_Recursive(T->lchild, Visit))
			if (Visit(T->data))
				if (InOrderTraverse_Recursive(T->rchild, Visit))
					return OK;
		return ERROR;
	}
	else
		return OK;
}

Status PostOrderTraverse_Recursive(BiTree T, Status(*Visit)(TElemType e))
{
	if (T)
	{
		if (PostOrderTraverse_Recursive(T->lchild, Visit))
			if (PostOrderTraverse_Recursive(T->rchild, Visit))
				if (Visit(T->data))
					return OK;
		return ERROR;
	}
	else
		return OK;
}

/*
 * 先序遍歷二叉樹，非遞歸算法。
 */
Status PreOrderTraverse_NonRecursive(BiTree T, Status(*Visit)(TElemType e))
{
	Stack *S;	//棧S中存儲指向樹結點的指針。
	BiTree p;
	S = (Stack*)malloc(sizeof(Stack));
	InitStack(S);
	Push(S, T);	//根指針進棧。
	while (!StackEmpty(S))
	{
		//獲取棧頂指針，如果棧頂指針不為空，訪問該結點。並將該結點的左子樹進棧。
		if (GetTop(S, &p) && p)
		{
			if (!Visit(p->data))
				return ERROR;
			Push(S, p->lchild);
		}
		//棧頂指針為空，表明之前壓入的左子樹或者右子樹為空。
		else
		{
			Pop(S, &p);	//空指針退棧
			if (!StackEmpty(S))
			{
				Pop(S, &p); //已被訪問過的根結點退棧。此時，該退棧結點的左子樹已被全部訪問過。
				Push(S, p->rchild);	//右子樹進棧。
			}
		}
	}
	return OK;
}

/* 
 * 采用二叉鏈表存儲結構，Visit是對數據元素進行操作的應用函數，
 * 中序遍歷二叉樹的非遞歸算法，對每個數據元素調用函數Visit。
 */
Status InOrderTraverse_NonRecursive(BiTree T, Status(*Visit)(TElemType e))
{
	Stack *S;
	BiTree p;
	S = (Stack *)malloc(sizeof(Stack));
	InitStack(S);
	Push(S, T);	//根指針進棧
	while (!StackEmpty(S))
	{
		//向左走到盡頭
		while (GetTop(S, &p) && p)
		{
			Push(S, p->lchild);
		}

		//空指針退棧
		Pop(S, &p);

		//訪問節點，並向右一步
		if (!StackEmpty(S))
		{
			Pop(S, &p);
			if (!Visit(p->data))
				return ERROR;
			Push(S, p->rchild);
		}
	}
	return OK;
}

/*
 * 采用二叉鏈表存儲結構，Visit是對數據元素進行操作的應用函數，
 * 中序遍歷二叉樹的非遞歸算法，對每個數據元素調用函數Visit。
 */
Status InOrderTraverse_NonRecursive_2(BiTree T, Status(*Visit)(TElemType e))
{
	Stack *S;
	BiTree p = T;
	S = (Stack *)malloc(sizeof(Stack));
	InitStack(S);

	while (p || !StackEmpty(S))
	{
		//根指針進棧，遍歷左子樹
		if (p)
		{
			Push(S, p);
			p = p->lchild;
		}
		//根指針退棧，訪問根結點，遍歷右子樹
		else
		{
			Pop(S, &p);
			if (!Visit(p->data))
				return ERROR;
			p = p->rchild;
		}
	}
	return OK;
}

/*
 * 後序遍歷二叉樹，非遞歸算法
 */
Status PostOrderTraverse_NonRecursive(BiTree T, Status(*Visit)(TElemType e))
{
	Stack *S;
	BiTree p, pre=NULL;//pre指向已訪問過的最後一個結點。
	S = (Stack*)malloc(sizeof(Stack));
	InitStack(S);
	Push(S, T);//根指針進棧

	while (!StackEmpty(S))
	{
		//獲取棧頂指針，如果當前結點有左子樹，並且左子樹結點不是剛被訪問的節點。如果當前結點有右子樹，並且右子樹結點不是剛被訪問的結點。
		//表明棧頂指針指向的樹結點未被訪問，且左子樹和右子樹均未被訪問。此時，將結點的左子樹進棧。
		if (GetTop(S, &p) && p->lchild && pre != p->lchild && !(p->rchild && pre == p->rchild))
			Push(S, p->lchild);
		//如果棧頂指針的右子樹存在，且未被訪問。則將右子樹進棧
		else if (p->rchild && pre != p->rchild)
			Push(S, p->rchild);
		//如果左子樹和右子樹均被訪問過，則結點退棧，並進行訪問。更新pre。
		else
		{
			Pop(S, &p);
			if (!Visit(p->data))
				return ERROR;
			pre = p;
		}
	}
	return OK;
}

//遍歷數據元素時所調用函數
Status PrintElement(TElemType e)
{
	putchar(e);
	return OK;
}

//初始化棧
Status InitStack(Stack *s)
{
	s->base = (BiTree*)malloc(sizeof(BiTree)*STACK_INIT_SIZE);
	s->top = s->base;
	s->stacksize = STACK_INIT_SIZE;
	return OK;
}

//獲得棧頂元素
Status GetTop(Stack *s, BiTree *c)
{
	if (StackEmpty(s))
		return ERROR;
	*c = *(s->top - 1);
	return OK;
}

//判斷棧是否為空
Status StackEmpty(Stack *s)
{
	if (s->base == s->top)
		return OK;
	return ERROR;
}

//進棧
Status Push(Stack *s, BiTree c)
{
	//如果空間不夠，增加空間的分配
	if (s->top - s->base >= s->stacksize)
	{
		s->base = (BiTree*)realloc(s->base, sizeof(BiTree)*(s->stacksize + STACKINCREMENT));
		s->stacksize = s->stacksize + STACKINCREMENT;
	}

	*(s->top++) = c;
	return OK;
}

//出棧
Status Pop(Stack *s, BiTree *c)
{
	if (StackEmpty(s))
		return ERROR;
	*c = *(--s->top);
	return OK;
}

5.測試結果

注：程序中生成的樹為上圖中的樹

二叉樹遍歷的遞歸算法（C程序，先序中序或後序）

//***********************************************************
//頭文件
#include<stdio.h>
#include<stdlib.h>
//***********************************************************
//宏定義
#define OK 1
#define ERROR 0
#define OVERFLOW 0

//***********************************************************

typedef struct BiTNode{
//二叉樹二叉鏈表存儲結構
char data;
struct BiTNode *lChild,*rChild;
}BiTNode,*BiTree;
//***********************************************************
int CreateBiTree(BiTree &T){
//按先序次序輸入二叉中樹結點的值，空格表示空樹
//構造二叉鏈表表示的二叉樹T
char ch;
fflush(stdin);
scanf("%c",&ch);
if(ch==' ')T=NULL;
else{
if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))
return(OVERFLOW);
T->data=ch;
CreateBiTree(T->lChild);
CreateBiTree(T->rChild);
}
return(OK);
}
//*********************************************************
void PreOrderTraverse(BiTree T){
//采用二叉鏈表存儲結構，先序遍歷二叉樹的遞歸算法
if(T){
printf("%c",T->data);
PreOrderTraverse(T->lChild);
PreOrderTraverse(T->rChild);
}
}
/***********************************************************
void InOrderTraverse(BiTree T){
//采用二叉鏈表存儲結構，中序遍歷二叉樹的遞歸算法
if(T){
InOrderTraverse(T->lChild);
......余下全文>>

編寫一個程序，實現二叉樹的先序遍歷，中序遍歷，後序遍歷的各種遞歸與非遞歸算法，以及層次遍歷的算法

文件 main.cpp 代碼如下：

#include<malloc.h> // malloc()等
#include<stdio.h> // 標准輸入輸出頭文件，包括EOF(=^Z或F6)，NULL等
#include<stdlib.h> // atoi()，exit()
#include<math.h> // 數學函數頭文件，包括floor()，ceil()，abs()等

#define ClearBiTree DestroyBiTree // 清空二叉樹和銷毀二叉樹的操作一樣

typedef struct BiTNode
{
int data; // 結點的值
BiTNode *lchild,*rchild; // 左右孩子指針
}BiTNode,*BiTree;

int Nil=0; // 設整型以0為空
void visit(int e)
{ printf("%d ",e); // 以整型格式輸出
}
void InitBiTree(BiTree &T)
{ // 操作結果：構造空二叉樹T
T=NULL;
}

void CreateBiTree(BiTree &T)
{ // 算法6.4：按先序次序輸入二叉樹中結點的值(可為字符型或整型，在主程中定義)，
// 構造二叉鏈表表示的二叉樹T。變量Nil表示空(子)樹。修改
int number;
scanf("%d",&number); // 輸入結點的值
if(number==Nil) // 結點的值為空
T=NULL;
else // 結點的值不為空
{ T=(BiTree)malloc(sizeof(BiTNode)); // 生成根結點
if(!T)
exit(OVERFLOW);
T->data=number; // 將值賦給T所指結點
CreateBiTree(T->lchild); // 遞歸構造左子樹
CreateBiTree(T->rchild); // 遞歸構造右子樹
}
}

void DestroyBiTree(BiTree &T)
{ // 初始條件：二叉樹T存在。操作結果：銷毀二叉樹T
if(T) // 非空樹
{ DestroyBiTree(T->lchild); // 遞歸銷毀左子樹，如無左子樹，則不執行任何操作
DestroyBiTree(T->rchild); // 遞歸銷毀右子樹，如無右子樹，則不執行任何操作
free(T); // 釋放根結點
T=NULL; // 空指針賦0
}
}

void PreOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始條件：二叉樹T......余下全文>>