快捷導(dǎo)航

C語(yǔ)言二叉樹(shù)的遍歷示例介紹

更新時(shí)間：2022年01月07日 16:35:58 作者：不吃香菜的香菜頭子

大家好，本篇文章主要講的是C語(yǔ)言二叉樹(shù)的遍歷示例介紹，感興趣的同學(xué)趕快來(lái)看一看吧，對(duì)你有幫助的話記得收藏一下，方便下次瀏覽

在本算法中先利用先序遍歷創(chuàng)建了樹(shù)，利用了遞歸的算法使得算法簡(jiǎn)單，操作容易，本來(lái)無(wú)printf("%c的左/右子樹(shù)：", ch);的語(yǔ)句，但由于計(jì)算機(jī)需要輸入空格字符來(lái)判斷左右子樹(shù)，為了減少人為輸入的失誤，特地加入這條語(yǔ)句，以此保證準(zhǔn)確率。

#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define OVERFLOW 3
 
typedef int Status;  
typedef int Boolean; 
typedef char TElemType;
 
typedef struct BiTNode{
	TElemType	   data;
	struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
 
//創(chuàng)建二叉樹(shù)函數(shù)
 
Status CreateBiTree(BiTree &T){
	TElemType ch;
	scanf("%c", &ch);
	getchar();
	if(ch == ' '){	T = NULL;}
	else {
		if( !(T=(BiTree)malloc(sizeof(BiTNode))))(exit(OVERFLOW));
		T->data = ch;				
		printf("%c的左子樹(shù)：", ch);
		CreateBiTree(T->lchild);		
		printf("%c的右子樹(shù)：", ch);
		CreateBiTree(T->rchild);	}
	return OK;
}
 
//先序遍歷函數(shù)
Status PreOrderTraverse(BiTree T, Status (* Visit)(TElemType e)){
	if(T){
		if(Visit(T->data)){
			if(PreOrderTraverse(T->lchild, Visit)){
				if(PreOrderTraverse(T->rchild, Visit)){
					return OK;
               }	
            }	
         }
		return ERROR;
    }
	else {return OK;}
}
 
//中序遍歷函數(shù)
Status InOrderTraverse(BiTree T, Status (* Visit)(TElemType e)){
	if(T){
		if(PreOrderTraverse(T->lchild, Visit) ){
			if(Visit(T->data)){
				if(PreOrderTraverse(T->rchild, Visit) ){
					return OK;
           }
	   }	
   }
		return ERROR;
        }
	else {
		return OK;
        }
	}
 
//后序遍歷函數(shù)
Status PosOrderTraverse(BiTree T, Status (* Visit)(TElemType e)){
	if(T){
		if(PreOrderTraverse(T->lchild, Visit) ){
			if(PreOrderTraverse(T->rchild, Visit) ){
				if(Visit(T->data)){return OK;
}
	}	
}
		return ERROR;}
	else {return OK;
}
}
 
 
//輸出二叉樹(shù)函數(shù)
Status PrintElement(TElemType e){	
	printf("%c",e);
	return OK;
}
 
//主函數(shù)
int main(){
	BiTree T;
	printf("輸入根結(jié)點(diǎn)：");
	CreateBiTree(T);
	printf("先序遍歷：\n");
	PreOrderTraverse(T, PrintElement);
	printf("\n");
	printf("中序遍歷：\n");
	InOrderTraverse(T, PrintElement);
	printf("\n");
	printf("后序遍歷：\n");
	PosOrderTraverse(T, PrintElement);
	return 0;
}

遍歷操作有四種，其不同在于對(duì)根結(jié)點(diǎn)的訪問(wèn)順序不同。在先序遍歷中，首先訪問(wèn)根結(jié)點(diǎn)，然后遞歸地做左子樹(shù)的先序遍歷，然后是右子樹(shù)的遞歸先序遍歷。在中序遍歷中，遞歸地對(duì)左子樹(shù)進(jìn)行中序遍歷，訪問(wèn)根結(jié)點(diǎn)，最后遞歸中序遍歷右子樹(shù)。在后序遍歷中，遞歸地對(duì)左子樹(shù)和右子樹(shù)進(jìn)行后序遍歷，然后訪問(wèn)根結(jié)點(diǎn)。先序，中序，后序遍歷就是對(duì)于根節(jié)點(diǎn)的訪問(wèn)順序。

但無(wú)論哪種遍歷方式，遞歸的方法是最簡(jiǎn)便，最直接，最簡(jiǎn)單的算法。

運(yùn)行截圖：