<pre name="code" class="cpp">#include <stdio.h> #include <malloc.h>typedef char elemType;typedef struct BTree {elemType data;struct BTree* lTree;struct BTree* rTree;struct BTree* next;//打印二叉樹時建立隊(duì)列需要 }Tree;typedef struct QList {Tree* first;//隊(duì)頭Tree* rear;//隊(duì)尾int queneSize;//隊(duì)大小 }Quene;//隊(duì)列初始化 生成空隊(duì)列 Quene* createQuene() {Quene* Q;Q=(Quene*)malloc(sizeof(Quene));Q->first=Q->rear=NULL;Q->queneSize=0;return Q; }//入隊(duì) void enterQuene(Quene* Q,Tree* T) {Tree* p;p=(Tree*)malloc(sizeof(Tree));p->data=T->data;p->lTree=T->lTree;p->rTree=T->rTree;p->next=NULL;Q->queneSize++;if(Q->first==NULL)//空隊(duì)列Q->first=Q->rear=p;else{Q->rear->next=p;Q->rear=p;}}//出隊(duì) Tree* deleteQuene(Quene* Q,elemType *elem) {Tree* p;p=(Tree*)malloc(sizeof(Tree));*elem=Q->first->data;p=Q->first;Q->first=p->next;Q->queneSize--;if(Q->queneSize==0)//重要Q->rear=NULL;return p;//free(p);//p=NULL; }//遍歷隊(duì)列 void displayQuene(Quene* Q) {printf("遍歷隊(duì)列\(zhòng)r\n");int i=Q->queneSize;Tree* p=(Tree*)malloc(sizeof(Tree));p=Q->first;while(i--){printf("%c\t",p->data);p=p->next;}printf("\r\n"); }//判斷隊(duì)列是否為空 bool isEmptyQuene(Quene* Q) {return Q->first==NULL&&Q->rear==NULL&&Q->queneSize==0; }//創(chuàng)建二叉樹 Tree* createTree() {Tree* T;T=(Tree*)malloc(sizeof(Tree));char ch;scanf("%c",&ch);if(ch=='#')return NULL;T->data=ch;T->next=NULL;T->lTree=createTree();T->rTree=createTree();return T; }//判斷是否為空樹 bool isEmptyTree(Tree* T) {return T==NULL; }//先序遍歷二叉樹 void preOrder(Tree* T) {if(T){preOrder(T->lTree);printf("%c\t",T->data);preOrder(T->rTree);} }//中序遍歷二叉樹 void inOrder(Tree* T) {if(T){printf("%c\t",T->data);inOrder(T->lTree);inOrder(T->rTree);} }//后序遍歷二叉樹 void postOrder(Tree* T) {if(T){postOrder(T->lTree);postOrder(T->rTree);printf("%c\t",T->data);} }//打印二叉樹（重點(diǎn)）從上往下打印二叉樹 void printTree_elem(Tree* T) {printf("層次遍歷打印二叉樹\r\n");if(T == NULL)return;Quene* Q;Q=createQuene();printf("%c\t",T->data);if(T->lTree)enterQuene(Q,T->lTree);if(T->rTree)enterQuene(Q,T->rTree);while(!isEmptyQuene(Q)){elemType temp;Tree* p;p=deleteQuene(Q,&temp);printf("%c\t",temp);if(p->lTree)enterQuene(Q,p->lTree);if(p->rTree)enterQuene(Q,p->rTree);}printf("\r\n"); }//打印二叉樹（重點(diǎn)）圖形 隊(duì)列 bool printTree(Tree* T,int nLayer) {if(T==NULL){for(int i=0;i<nLayer;i++){printf(" ");}printf("%c\n",'#');return false;}printTree(T->rTree,nLayer+3);for(int i=0;i<nLayer;i++){printf(" ");}printf("%c\n",T->data);printTree(T->lTree,nLayer+3);return true; }//清空二叉樹 void clearTree(Tree* T) {if(T ==NULL)return;if(T->lTree!=NULL)clearTree(T->lTree);if(T->rTree!=NULL)clearTree(T->rTree);free(T);//T=NULL;return; } //銷毀二叉樹 void destroyTree(Tree* T) {if(T)clearTree(T); }//返回樹的深度 int deptTree(Tree* T) {int ldept,rdept;ldept=0;rdept=0;if(T->lTree||T->rTree){if(T->lTree)ldept=deptTree(T->lTree);if(T->rTree)rdept=deptTree(T->rTree);}return 1+(ldept>rdept?ldept:rdept);//1 根節(jié)點(diǎn) }//返回結(jié)點(diǎn)數(shù) int cntTree(Tree* T) {int cnt=0;if(T)cnt++;if(T->lTree)cnt+=cntTree(T->lTree);if(T->rTree)cnt+=cntTree(T->rTree);return cnt; }//返回子樹結(jié)點(diǎn)深度 void deptNode(Tree* T,Tree* p,int *dept,int *flag) {if(T->data==p->data)//找到該子樹{*flag=1;return;}if(!*flag)(*dept)++;if(!*flag)if(T->lTree){deptNode(T->lTree,p,&(*dept),&(*flag));if(*flag)return;}if(!*flag)if(T->rTree){deptNode(T->rTree,p,&(*dept),&(*flag));if(*flag)return;}if(!*flag){(*dept)=(*dept)-1;return;} }int main() {Tree* T;printf("創(chuàng)建二叉樹\r\n");T=createTree();printf("先序遍歷二叉樹\r\n");preOrder(T);printf("\r\n");printf("中序遍歷二叉樹\r\n");inOrder(T);printf("\r\n");printf("后序遍歷二叉樹\r\n");postOrder(T);printf("\r\n");printf("二叉樹的深度:%d\r\n",deptTree(T));printf("二叉樹的結(jié)點(diǎn)數(shù):%d\r\n",cntTree(T));/*//測試：返回子樹結(jié)點(diǎn)的深度Tree* p;p=(Tree*)malloc(sizeof(Tree));p->lTree=NULL;p->rTree=NULL;int dept=1;//子樹深度int flag=0;//搜索標(biāo)志 找到時置1 // p->data='a'; // p->data='b'; // p->data='c'; // p->data='d'; // p->data='e'; // p->data='f';p->data='g';deptNode(T,p,&dept,&flag);printf("子樹結(jié)點(diǎn)%c的深度為:%d\r\n",p->data,dept);*/printTree_elem(T);printf("打印豎狀二叉樹\r\n");printTree(T,0); }

總結(jié)

以上是生活随笔為你收集整理的二叉树(C语言)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。