二叉樹基本操作之遞歸和非遞歸遍歷、分支節(jié)點數(shù)詳解
二叉樹的定義
二叉樹是由n(n>=0)個結(jié)點的有限集合構(gòu)成,此集合或者為空集,或者由一個根結(jié)點及兩棵互不相交的左右子樹組成,并且左右子樹都是二叉樹.
遞歸定義:叉樹可以是空集合,根可以有空的左子樹或空的右子樹。二叉樹不是樹的特殊情況,它們是兩個概念。
typedef char ElemType; typedef struct BiTNode{ ElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree;
二叉樹的遍歷
原表達式:a+b*(c-d)-e/f
先序遍歷:-+a*b-cd/ef
中序遍歷:a+b*c-d-e/f
后序遍歷:abcd-*+ef/-
先序遞歸遍歷過程
即先序遍歷完成
void PreOrderTraverse(BiTree BT) { if(BT) { if(!(BT->data)) return; printf("%c",BT->data); PreOrderTraverse(BT->lchild); PreOrderTraverse(BT->rchild); } }
中序遍歷和后序遍歷同上
層次非遞歸遍歷
該樹的層次遞歸遍歷為:ABCDEGF
運用隊列來存儲樹的結(jié)點首先A入隊,輸出A結(jié)點,然后隊首結(jié)點A出隊,將A的孩子結(jié)點B,C分別入隊。訪問隊首結(jié)點B,輸出并出隊,將B的孩子結(jié)點D,E入隊。訪問隊首結(jié)點C,輸出并出隊,C結(jié)點只有右孩子,將C的右孩子結(jié)點G入隊。訪問隊首結(jié)點D,輸出并出隊,D沒有孩子結(jié)點,不入隊。訪問隊首結(jié)點E,輸出并出隊,將E的孩子結(jié)點F入隊。訪問隊首結(jié)點G,輸出并出隊,G沒有孩子結(jié)點,不入隊。訪問隊首結(jié)點F,輸出并出隊,F(xiàn)沒有孩子結(jié)點,不入隊。此時隊列為空,結(jié)束遍歷。
void leverTraverse(BiTree BT) { Squeue Q; BiTree pt=BT; InitQueue(&Q); EnQueue(&Q,pt); while(!EmptyQueue(Q)) { Dequeue(&Q,&pt); printf("%c",pt->data); if(pt->lchild) EnQueue(&Q,pt->lchild); if(pt->rchild) EnQueue(&Q,pt->rchild); } }
完整代碼:
// erchashu.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include "stdlib.h" #include "string.h" #define MAXSIZE 50 int max=0; typedef char ElemType; typedef struct BiTNode{ ElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; typedef struct SQueue{ BiTree *base; int front; int rear; }Squeue; void InitBiTree(BiTree *BT) { *BT=NULL; } void PreCreatBiTree(BiTree *BT) { ElemType ch; printf("輸入數(shù)據(jù):\n"); getchar(); ch=getchar(); if(ch=='#') *BT=NULL; else { *BT=(BiTree)malloc(sizeof(BiTNode)); (*BT)->data=ch; PreCreatBiTree(&(*BT)->lchild); PreCreatBiTree(&(*BT)->rchild); } } void PreOrderTraverse(BiTree BT) { if(BT) { if(!(BT->data)) return; printf("%c",BT->data); PreOrderTraverse(BT->lchild); PreOrderTraverse(BT->rchild); } } void InOrderTraverse(BiTree BT) { if(BT) { if(!(BT->data)) return; InOrderTraverse(BT->lchild); printf("%c",BT->data); InOrderTraverse(BT->rchild); } } void PostOrderTraverse(BiTree BT) { if(BT) { if(!(BT->data)) return; PostOrderTraverse(BT->lchild); PostOrderTraverse(BT->rchild); printf("%c",BT->data); } } void InitQueue(Squeue *Q) { (*Q).base=(BiTree *)malloc(sizeof(BiTNode)*MAXSIZE); (*Q).front=(*Q).rear=0; } void EnQueue(Squeue *Q,BiTree BT) { (*Q).base[(*Q).rear++]=BT; } int EmptyQueue(Squeue Q) { if(Q.front==Q.rear) return 1; return 0; } void Dequeue(Squeue *Q,BiTree *pt) { if((*Q).front==(*Q).rear) return; *pt=(*Q).base[(*Q).front]; (*Q).front=((*Q).front +1) % MAXSIZE; } void leverTraverse(BiTree BT) { Squeue Q; BiTree pt=BT; InitQueue(&Q); EnQueue(&Q,pt); while(!EmptyQueue(Q)) { Dequeue(&Q,&pt); printf("%c",pt->data); if(pt->lchild) EnQueue(&Q,pt->lchild); if(pt->rchild) EnQueue(&Q,pt->rchild); } } void NRPreOrderTraverse(BiTree BT) { BiTree pt=BT,stack[MAXSIZE]; int top=0; while(pt || top) { if(pt) { printf("%c",pt->data); stack[top++]=pt; pt=pt->lchild; } else { pt=stack[--top]; pt=pt->rchild; } } } int BiTreedepth(BiTree BT,int depth) { if(BT) { if(BT->lchild) BiTreedepth(BT->lchild,depth+1); if(BT->rchild) BiTreedepth(BT->rchild,depth+1); } if(depth>max) max=depth; return depth; } int LeafNumber(BiTree BT) { if(!BT) return 0; else { if((!BT->lchild) && (!BT->rchild)) return 1; else return LeafNumber(BT->lchild)+LeafNumber(BT->rchild); } } int singleBiTree(BiTree BT) { if(!BT) return 0; else { if(BT->lchild && !BT->rchild) return singleBiTree(BT->lchild)+1; else { if(!BT->lchild && BT->rchild) return singleBiTree(BT->lchild)+1; else return singleBiTree(BT->lchild)+singleBiTree(BT->rchild); } } } int doubleBiTree(BiTree BT) { int book=0; if(!BT) return 0; if(BT->lchild && BT->rchild) book=1; return book+doubleBiTree(BT->lchild)+doubleBiTree(BT->rchild); } void revoluteBiTree(BiTree *BT) { BiTree T; if(!(*BT)->lchild && !(*BT)->rchild) return; else { T=(*BT)->lchild; (*BT)->lchild=(*BT)->rchild; (*BT)->rchild=T; } if((*BT)->lchild) { revoluteBiTree(&(*BT)->lchild); } if((*BT)->rchild) { revoluteBiTree(&(*BT)->rchild); } } int main(int argc, char* argv[]) { BiTree BT; int tmp; int flag=1,select; InitBiTree(&BT); while(flag) { printf("\n請選擇:\n"); printf("0. 先序創(chuàng)建二叉樹用#代表空結(jié)點\n"); printf("1. 先序遍歷\n"); printf("2. 中序遍歷\n"); printf("3. 后序遍歷\n"); printf("4. 非遞歸層次遍歷\n"); printf("5. 非遞歸先序遍歷\n"); printf("6. 二叉樹高度\n"); printf("7. 葉結(jié)點數(shù)目\n"); printf("8. 單分支結(jié)點數(shù)目\n"); printf("9. 雙分支結(jié)點數(shù)目\n"); printf("10. 交換二叉樹\n"); printf("11.退出程序\n"); printf("請輸入要執(zhí)行的操作:\n"); scanf("%d",&select); switch(select) { case 0: PreCreatBiTree(&BT); break; case 1: printf("\n先序遍歷為:\n"); PreOrderTraverse(BT); break; case 2: printf("\n中序遍歷為:\n"); InOrderTraverse(BT); break; case 3: printf("\n后序遍歷為:\n"); PostOrderTraverse(BT); break; case 4: printf("\n層次非遞歸遍歷為:\n"); leverTraverse(BT); break; case 5: printf("\n先序非遞歸遍歷為:\n"); NRPreOrderTraverse(BT); break; case 6: printf("\n高度為: "); BiTreedepth(BT,1); printf("%d\n",max); break; case 7: printf("\n葉結(jié)點數(shù)目為: "); tmp=LeafNumber(BT); printf("%d\n",tmp); break; case 8: printf("\n單分支結(jié)點數(shù)目為: "); tmp=singleBiTree(BT); printf("%d\n",tmp); break; case 9: printf("\n雙分支結(jié)點數(shù)目為: "); tmp=doubleBiTree(BT); printf("%d\n",tmp); break; case 10: printf("\n已交換二叉樹\n"); revoluteBiTree(&BT); break; default: flag=0; printf("Press any key to exit!\n"); break; } } printf("\n"); return 0; }
到此這篇關(guān)于二叉樹基本操作之遞歸和非遞歸遍歷、分支節(jié)點數(shù)詳解的文章就介紹到這了,更多相關(guān)二叉樹基本操作內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
SpringMVC JSON數(shù)據(jù)傳輸參數(shù)超詳細講解
有時候參數(shù)的傳遞還需要更多的參數(shù),比如一個獲取用戶信息的請求中既有用戶ID等基本參數(shù),還要求對查詢結(jié)果進行分頁,針對這種場景,一般都會將分頁參數(shù)封裝成一個對象,然后將它和基本參數(shù)一起傳給控制器2023-02-02@valid 無法觸發(fā)BindingResult的解決
這篇文章主要介紹了@valid 無法觸發(fā)BindingResult的解決方案,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2021-12-12從零搭建SpringBoot+MyBatisPlus快速開發(fā)腳手架
這篇文章主要為大家介紹了從零搭建SpringBoot+MyBatisPlus快速開發(fā)腳手架示例教程,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2022-06-06