二叉樹基本操作之遞歸和非遞歸遍歷、分支節(jié)點(diǎn)數(shù)詳解
更新時(shí)間：2023年09月25日 08:32:09 作者：小熊不吃香菜
這篇文章主要介紹了二叉樹基本操作之遞歸和非遞歸遍歷、分支節(jié)點(diǎn)數(shù)詳解,二叉樹是由n(n>=0)個(gè)結(jié)點(diǎn)的有限集合構(gòu)成,此集合或者為空集,或者由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的左右子樹組成,并且左右子樹都是二叉樹,需要的朋友可以參考下
二叉樹的定義
二叉樹是由n(n>=0)個(gè)結(jié)點(diǎn)的有限集合構(gòu)成，此集合或者為空集，或者由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的左右子樹組成，并且左右子樹都是二叉樹.
遞歸定義:叉樹可以是空集合，根可以有空的左子樹或空的右子樹。二叉樹不是樹的特殊情況，它們是兩個(gè)概念。
typedef char ElemType;
typedef struct BiTNode{
ElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;二叉樹的遍歷
原表達(dá)式：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
運(yùn)用隊(duì)列來存儲樹的結(jié)點(diǎn)首先A入隊(duì)，輸出A結(jié)點(diǎn)，然后隊(duì)首結(jié)點(diǎn)A出隊(duì)，將A的孩子結(jié)點(diǎn)B，C分別入隊(duì)。訪問隊(duì)首結(jié)點(diǎn)B，輸出并出隊(duì)，將B的孩子結(jié)點(diǎn)D，E入隊(duì)。訪問隊(duì)首結(jié)點(diǎn)C，輸出并出隊(duì)，C結(jié)點(diǎn)只有右孩子，將C的右孩子結(jié)點(diǎn)G入隊(duì)。訪問隊(duì)首結(jié)點(diǎn)D，輸出并出隊(duì)，D沒有孩子結(jié)點(diǎn)，不入隊(duì)。訪問隊(duì)首結(jié)點(diǎn)E，輸出并出隊(duì)，將E的孩子結(jié)點(diǎn)F入隊(duì)。訪問隊(duì)首結(jié)點(diǎn)G，輸出并出隊(duì)，G沒有孩子結(jié)點(diǎn)，不入隊(duì)。訪問隊(duì)首結(jié)點(diǎn)F，輸出并出隊(duì)，F(xiàn)沒有孩子結(jié)點(diǎn)，不入隊(duì)。此時(shí)隊(duì)列為空，結(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é)點(diǎn)\n");
printf("1. 先序遍歷\n");
printf("2. 中序遍歷\n");
printf("3. 后序遍歷\n");
printf("4. 非遞歸層次遍歷\n");
printf("5. 非遞歸先序遍歷\n");
printf("6. 二叉樹高度\n");
printf("7. 葉結(jié)點(diǎn)數(shù)目\n");
printf("8. 單分支結(jié)點(diǎn)數(shù)目\n");
printf("9. 雙分支結(jié)點(diǎn)數(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é)點(diǎn)數(shù)目為: ");
tmp=LeafNumber(BT);
printf("%d\n",tmp);
break;
case 8:
printf("\n單分支結(jié)點(diǎn)數(shù)目為: ");
tmp=singleBiTree(BT);
printf("%d\n",tmp);
break;
case 9:
printf("\n雙分支結(jié)點(diǎn)數(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é)點(diǎn)數(shù)詳解的文章就介紹到這了,更多相關(guān)二叉樹基本操作內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
文章介紹了如何在Spring?Boot項(xiàng)目中整合JWT（JSON?Web?Token）,包括JWT的結(jié)構(gòu)、使用方法、測試以及配置,主要內(nèi)容涵蓋了依賴配置、數(shù)據(jù)庫表設(shè)計(jì)、實(shí)體類、數(shù)據(jù)訪問層、服務(wù)層、JWT工具類、攔截器配置和控制器測試等多個(gè)方面2024-11-11
GateWay路由規(guī)則與動態(tài)路由詳細(xì)介紹
這篇文章主要介紹了GateWay路由規(guī)則與GateWay動態(tài)路由，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-09-09
公司某服務(wù)內(nèi)存持續(xù)增長,疑似內(nèi)存泄漏,未觸發(fā)OOM,排查方法包括檢查JVM配置、分析GC執(zhí)行狀態(tài)、導(dǎo)出堆內(nèi)存快照并用IDEA Profiler工具定位大對象及代碼2025-07-07
這篇文章主要介紹了Java List與數(shù)組互轉(zhuǎn)方式，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-07-07
這篇文章主要介紹了Java System.exit()退出程序方式,具有很好的參考價(jià)值,希望對大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2024-06-06
這篇文章主要介紹了深入理解Java虛擬機(jī)體系結(jié)構(gòu)，具有一定借鑒價(jià)值,需要的朋友可以參考下2018-01-01
Java實(shí)現(xiàn)狀態(tài)模式的示例代碼
狀態(tài)模式是一種行為型設(shè)計(jì)模式,允許對象根據(jù)其內(nèi)部狀態(tài)改變行為,本文主要介紹了Java實(shí)現(xiàn)狀態(tài)模式的示例代碼,文中通過示例代碼介紹的非常詳細(xì),需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2025-02-02
SpringBoot根據(jù)各地區(qū)時(shí)間設(shè)置接口有效時(shí)間的實(shí)現(xiàn)方式
這篇文章給大家介紹了SpringBoot根據(jù)各地區(qū)時(shí)間設(shè)置接口有效時(shí)間的實(shí)現(xiàn)方式,文中通過代碼示例給大家講解的非常詳細(xì),對大家的學(xué)習(xí)或工作有一定的幫助,需要的朋友可以參考下2024-01-01
Closeable是Java中的一個(gè)標(biāo)記接口,用于表示可以被關(guān)閉的對象,它定義了一個(gè)標(biāo)準(zhǔn)的方法來釋放對象占用的系統(tǒng)資源,下面給大家介紹Java中的Closeable接口,感興趣的朋友一起看看吧2025-05-05
這篇文章主要介紹了springboot?jpa之返回表中部分字段的處理詳解，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-12-12