欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

二叉樹基本操作之遞歸和非遞歸遍歷、分支節(jié)點數(shù)詳解

 更新時間：2023年09月25日 08:32:09   作者：小熊不吃香菜  
這篇文章主要介紹了二叉樹基本操作之遞歸和非遞歸遍歷、分支節(jié)點數(shù)詳解,二叉樹是由n(n>=0)個結(jié)點的有限集合構成,此集合或者為空集,或者由一個根結(jié)點及兩棵互不相交的左右子樹組成,并且左右子樹都是二叉樹,需要的朋友可以參考下

二叉樹的定義

二叉樹是由n(n>=0)個結(jié)點的有限集合構成，此集合或者為空集，或者由一個根結(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;
}

到此這篇關于二叉樹基本操作之遞歸和非遞歸遍歷、分支節(jié)點數(shù)詳解的文章就介紹到這了,更多相關二叉樹基本操作內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

相關文章

  • java用兩個例子充分闡述多態(tài)的可拓展性介紹

    java用兩個例子充分闡述多態(tài)的可拓展性介紹

    下面小編就為大家?guī)硪黄猨ava用兩個例子充分闡述多態(tài)的可拓展性介紹。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧
    2016-06-06
  • Java?web實現(xiàn)購物車案例

    Java?web實現(xiàn)購物車案例

    這篇文章主要為大家詳細介紹了Java?web實現(xiàn)購物車案例，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
    2022-08-08
  • 基于java實現(xiàn)具有時效性文件鏈接

    基于java實現(xiàn)具有時效性文件鏈接

    這篇文章主要為大家詳細介紹了如何基于java實現(xiàn)具有時效性的文件鏈接,文中的示例代碼講解詳細,具有一定的借鑒價值,感興趣的小伙伴可以了解一下
    2023-12-12
  • Java基礎學習之標簽

    Java基礎學習之標簽

    在Java中,標簽必須在循環(huán)之前使用, 一個循環(huán)之中嵌套另一個循環(huán)的開關,從多重嵌套中continue或break,該文詳細介紹了標簽的相關知識,對正在學習java基礎的小伙伴們還很有幫助,需要的朋友可以參考下
    2021-05-05
  • Java消息隊列Kafka的簡單概述

    Java消息隊列Kafka的簡單概述

    這篇文章主要介紹了Java消息隊列Kafka的簡單概述,消息系統(tǒng)負責將數(shù)據(jù)從一個應用程序傳輸?shù)搅硪粋€應用程序，應用程序可以專注于數(shù)據(jù)，不擔心如何共享它,需要的朋友可以參考下
    2023-07-07
  • MybatisPlus 主鍵策略的幾種實現(xiàn)方法

    MybatisPlus 主鍵策略的幾種實現(xiàn)方法

    MybatisPlus-Plus支持多種主鍵生成策略,可以通過@TableId注解的type屬性配置,主要策略包括AUTO、INPUT、ASSING_ID、ASSING_UUID和NONE,每種策略適用于不同的場景,下面就來介紹一下
    2024-10-10
  • SpringMVC JSON數(shù)據(jù)傳輸參數(shù)超詳細講解

    SpringMVC JSON數(shù)據(jù)傳輸參數(shù)超詳細講解

    有時候參數(shù)的傳遞還需要更多的參數(shù)，比如一個獲取用戶信息的請求中既有用戶ID等基本參數(shù)，還要求對查詢結(jié)果進行分頁，針對這種場景，一般都會將分頁參數(shù)封裝成一個對象，然后將它和基本參數(shù)一起傳給控制器
    2023-02-02
  • @valid 無法觸發(fā)BindingResult的解決

    @valid 無法觸發(fā)BindingResult的解決

    這篇文章主要介紹了@valid 無法觸發(fā)BindingResult的解決方案，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教
    2021-12-12
  • java 排序算法之快速排序

    java 排序算法之快速排序

    這篇文章主要介紹了java 排序算法之快速排序，文中通過圖片和代碼講解相關知識非常詳細，大家如果有需要的話可以參考一下這篇文章
    2021-09-09
  • 從零搭建SpringBoot+MyBatisPlus快速開發(fā)腳手架

    從零搭建SpringBoot+MyBatisPlus快速開發(fā)腳手架

    這篇文章主要為大家介紹了從零搭建SpringBoot+MyBatisPlus快速開發(fā)腳手架示例教程，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪
    2022-06-06

最新評論