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!