C語言二叉樹的遍歷示例介紹

     在本算法中先利用先序遍歷創建瞭樹,利用瞭遞歸的算法使得算法簡單,操作容易,本來無printf("%c的左/右子樹:", ch);的語句,但由於計算機需要輸入空格字符來判斷左右子樹,為瞭減少人為輸入的失誤,特地加入這條語句,以此保證準確率。

#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;
 
//創建二叉樹函數
 
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的左子樹:", ch);
		CreateBiTree(T->lchild);		
		printf("%c的右子樹:", ch);
		CreateBiTree(T->rchild);	}
	return OK;
}
 
//先序遍歷函數
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;}
}
 
//中序遍歷函數
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;
        }
	}
 
//後序遍歷函數
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;
}
}
 
 
//輸出二叉樹函數
Status PrintElement(TElemType e){	
	printf("%c",e);
	return OK;
}
 
//主函數
int main(){
	BiTree T;
	printf("輸入根結點:");
	CreateBiTree(T);
	printf("先序遍歷:\n");
	PreOrderTraverse(T, PrintElement);
	printf("\n");
	printf("中序遍歷:\n");
	InOrderTraverse(T, PrintElement);
	printf("\n");
	printf("後序遍歷:\n");
	PosOrderTraverse(T, PrintElement);
	return 0;
}

       遍歷操作有四種,其不同在於對根結點的訪問順序不同。在先序遍歷中,首先訪問根結點,然後遞歸地做左子樹的先序遍歷,然後是右子樹的遞歸先序遍歷。 在中序遍歷中,遞歸地對左子樹進行中序遍歷,訪問根結點,最後遞歸中序遍歷右子樹。在後序遍歷中,遞歸地對左子樹和右子樹進行後序遍歷,然後訪問根結點。先序,中序,後序遍歷就是對於根節點的訪問順序。

       但無論哪種遍歷方式,遞歸的方法是最簡便,最直接,最簡單的算法。

      運行截圖:

到此這篇關於C語言二叉樹的遍歷示例介紹的文章就介紹到這瞭,更多相關C語言二叉樹內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!

推薦閱讀: