真实的国产乱ⅩXXX66竹夫人,五月香六月婷婷激情综合,亚洲日本VA一区二区三区,亚洲精品一区二区三区麻豆

成都創(chuàng)新互聯(lián)網(wǎng)站制作重慶分公司

萬(wàn)字超全詳解：二叉樹(shù)的基本操作（C語(yǔ)言版本）-創(chuàng)新互聯(lián)

為都江堰等地區(qū)用戶提供了全套網(wǎng)頁(yè)設(shè)計(jì)制作服務(wù)，及都江堰網(wǎng)站建設(shè)行業(yè)解決方案。主營(yíng)業(yè)務(wù)為成都網(wǎng)站制作、成都網(wǎng)站設(shè)計(jì)、外貿(mào)營(yíng)銷網(wǎng)站建設(shè)、都江堰網(wǎng)站設(shè)計(jì)，以傳統(tǒng)方式定制建設(shè)網(wǎng)站，并提供域名空間備案等一條龍服務(wù)，秉承以專業(yè)、用心的態(tài)度為用戶提供真誠(chéng)的服務(wù)。我們深信只要達(dá)到每一位用戶的要求，就會(huì)得到認(rèn)可，從而選擇與我們長(zhǎng)期合作。這樣，我們也可以走得更遠(yuǎn)！

文章目錄

前言

一、二叉樹(shù)是什么？

二、二叉樹(shù)的創(chuàng)建（以順序表的形式）

1.先創(chuàng)建數(shù)組（為了順序表做準(zhǔn)備）

2.輸入數(shù)值

3.輸出數(shù)值

4.創(chuàng)建空二叉樹(shù)并在二叉樹(shù)中輸入數(shù)值

5.判斷是否為空二叉樹(shù)

6.返回二叉樹(shù)的深度

7.先序遍歷輸出二叉樹(shù)

8.中序遍歷輸出二叉樹(shù)

9.后序遍歷輸出二叉樹(shù)

10.層序遍歷輸出二叉樹(shù)

11.總結(jié)：（全部代碼實(shí)現(xiàn)）

三、二叉樹(shù)的基本操作（鏈表版本）

1.鏈表節(jié)點(diǎn)結(jié)構(gòu)體

2.先序創(chuàng)建二叉樹(shù)

1）中序后序創(chuàng)建二叉樹(shù)

3.先序遍歷二叉樹(shù)

1）遞歸操作

2）非遞歸操作

4.中序遍歷二叉樹(shù)

1）遞歸操作

2）非遞歸操作

5.后序遍歷二叉樹(shù)

1）遞歸操作

2）非遞歸操作

6.求第k層節(jié)點(diǎn)的個(gè)數(shù)

7.求二叉樹(shù)的深度

8.二叉樹(shù)的葉子節(jié)點(diǎn)的個(gè)數(shù)

9.二叉樹(shù)的總節(jié)點(diǎn)的個(gè)數(shù)

10.遞歸查找指定元素x的節(jié)點(diǎn)

11.全部代碼：

總結(jié)

前言

本文主要內(nèi)容：

?1.對(duì)于二叉樹(shù)的基本操作，創(chuàng)建 、遍歷 、前序、中序、后序輸出等

?2.關(guān)于二叉樹(shù)的自己的體會(huì)

提示：以下是本篇文章正文內(nèi)容，下面案例可供參考

一、二叉樹(shù)是什么？

二叉樹(shù)是數(shù)據(jù)結(jié)構(gòu)中的一種，可以通過(guò)順序表或者鏈表的形式實(shí)現(xiàn)，接下來(lái)讓我們一起來(lái)看看如何通過(guò)順序表或者鏈表的形式來(lái)實(shí)現(xiàn)二叉樹(shù)

二叉樹(shù)圖：

??

二、二叉樹(shù)的創(chuàng)建（以順序表的形式） 1.先創(chuàng)建數(shù)組（為了順序表做準(zhǔn)備）

代碼如下（示例）：

#define MAX_SIZE 100
typedef char TElemType;
typedef TElemType SqBiTree[MAX_SIZE];

TElemType Nil = '#';   我們規(guī)定當(dāng)元素?cái)?shù)值為 ‘#’ 的時(shí)候表示該節(jié)點(diǎn)為NULL
2.輸入數(shù)值

代碼如下（示例）：

void input(TElemType* x) {
?? ?scanf("%c", &x);
}      簡(jiǎn)單明了的傳參  TElemType也就是char類型的變量  x

3.輸出數(shù)值
void visit(TElemType x) {
	printf("%c", x);
}
4.創(chuàng)建空二叉樹(shù)并在二叉樹(shù)中輸入數(shù)值
void InitBiTree(SqBiTree T) {
	//構(gòu)造空二叉樹(shù)
	for (int i = 0; i< MAX_SIZE; i++) {
		T[i] = Nil;//初始值為空  #表示為空
	}
}

void CreateBiTree(SqBiTree T) {
	int i = 1;//按照層次次序輸入二叉樹(shù)中結(jié)點(diǎn)的值
	scanf("%s", T + 1);
	while (T[i]!='\0')
	{
		i++;
	}
	T[i] = '#';
}
5.判斷是否為空二叉樹(shù)
int BiTreeEmpty(SqBiTree T) {
	//初始條件：二叉樹(shù)T存在。操作結(jié)果為：若T為空二叉樹(shù)，則返回true 否則false
	if (T[1] == Nil) {
		return 1;//空
	}
	else {
		return 0;
	}
}
6.返回二叉樹(shù)的深度
//返回二叉樹(shù)的深度
int BiTreeDepth(SqBiTree T) {
	int i = MAX_SIZE - 1;
	while (T[i] == '#') {
		i--;
	}
	//現(xiàn)在得到的i是存儲(chǔ)元素的最后一位
	int j = i;
	int dep = 0;
	while (j >= 1) {
		dep++;
		j = j / 2;//根據(jù)的是樹(shù)的深度為 【log2n】+1
	}
	return dep;
 }
7.先序遍歷輸出二叉樹(shù)

這里的先序遍歷是通過(guò)二叉樹(shù)的一個(gè)性質(zhì)來(lái)輸出的，二叉樹(shù)的性質(zhì)之一：把完全二叉樹(shù)的節(jié)點(diǎn)按照順序?qū)懞脤?duì)應(yīng)坐標(biāo)之后，i 節(jié)點(diǎn)的左右孩子的坐標(biāo)位置分別為 2 * i? 和? 2 * i + 1；

void PreTraverse(SqBiTree T, int e) {
	if (T[e] != '#') {
		visit(T[e]);
		PreTraverse(T, 2 * e);
		PreTraverse(T, 2 * e + 1);//遍歷輸出結(jié)點(diǎn) 左子樹(shù) 右子樹(shù)
	}
}    這個(gè)函數(shù)就涉及到二叉樹(shù)的一個(gè)性質(zhì) 通過(guò)2*e和2*e+1來(lái)進(jìn)行遍歷


void  PreOrderTraverse(SqBiTree T) {
	//先序遍歷
	if (!BiTreeEmpty(T)) {
		//非空就調(diào)用PreTraverse
		PreTraverse(T, 1);//從第一個(gè)元素就開(kāi)始
	}
	printf("\n");
}
8.中序遍歷輸出二叉樹(shù)
void InTraverse(SqBiTree T, int e) {
	//中序遍歷使用
	if (T[e] != '#') {
		InTraverse(T, 2 * e);
		visit(T[e]);
		InTraverse(T, 2 * e + 1);//中序遍歷，先左后中再右
	}
}



void InOrderTreaverse(SqBiTree T) {
	if (!BiTreeEmpty(T)) {
		InTraverse(T, 1);
	}
	printf("\n");
}
9.后序遍歷輸出二叉樹(shù)
//后序遍歷
void PostTreaverse(SqBiTree T, int e) {
	if (T[e] != '#') {
		PostTreaverse(T, e * 2);
		PostTreaverse(T, e * 2 + 1);
		visit(T[e]);
	}

}

void PostOrderTraverse(SqBiTree T) {
	if (!BiTreeEmpty(T)){
		PostTreaverse(T, 1);
	}
	printf("\n");
}
10.層序遍歷輸出二叉樹(shù)
//層序遍歷二叉樹(shù)
void LevelOrderTraverse(SqBiTree T) {
	int dep = BiTreeDepth(T);
	int tree_max = pow(dep, 2) - 1;//得到當(dāng)前深度下完全二叉樹(shù)應(yīng)該有多少結(jié)點(diǎn)
	for (int i = 1; i< tree_max; i++) {
		if (T[i] == '#') {
			continue;
		}//不用輸出‘#’  而且獲得的深度來(lái)看，不需要for很多沒(méi)有價(jià)值的 下標(biāo)  牛逼

		visit(T[i]);
	}
}
11.總結(jié)：（全部代碼實(shí)現(xiàn)）
#define _CRT_SECURE_NO_WARNINGS
#include#include#include#include//使用順序結(jié)構(gòu)完成二叉樹(shù)的基本操作

//編寫(xiě)前序、中序、后序以及層次順序遍歷二叉樹(shù)的算法，并計(jì)算二叉樹(shù)的深度、所有的結(jié)點(diǎn)數(shù)

#define MAX_SIZE 100
typedef char TElemType;
typedef TElemType SqBiTree[MAX_SIZE];

TElemType Nil = '#';

void input(TElemType* x) {
	scanf("%c", &x);

}
void visit(TElemType x) {
	printf("%c", x);
}
void InitBiTree(SqBiTree T) {
	//構(gòu)造空二叉樹(shù)
	for (int i = 0; i< MAX_SIZE; i++) {
		T[i] = Nil;//初始值為空  #表示為空
	}
}

void CreateBiTree(SqBiTree T) {
	int i = 1;//按照層次次序輸入二叉樹(shù)中結(jié)點(diǎn)的值
	scanf("%s", T + 1);
	while (T[i]!='\0')
	{
		i++;
	}
	T[i] = '#';
}

int BiTreeEmpty(SqBiTree T) {
	//初始條件：二叉樹(shù)T存在。操作結(jié)果為：若T為空二叉樹(shù)，則返回true 否則false
	if (T[1] == Nil) {
		return 1;//空
	}
	else {
		return 0;
	}
}


//返回二叉樹(shù)的深度
int BiTreeDepth(SqBiTree T) {
	int i = MAX_SIZE - 1;
	while (T[i] == '#') {
		i--;
	}
	//現(xiàn)在得到的i是存儲(chǔ)元素的最后一位
	int j = i;
	int dep = 0;
	while (j >= 1) {
		dep++;
		j = j / 2;//根據(jù)的是樹(shù)的深度為 【log2n】+1
	}
	return dep;
 }

void PreTraverse(SqBiTree T, int e) {
	if (T[e] != '#') {
		visit(T[e]);
		PreTraverse(T, 2 * e);
		PreTraverse(T, 2 * e + 1);//遍歷輸出結(jié)點(diǎn) 左子樹(shù) 右子樹(shù)
	}
}


void  PreOrderTraverse(SqBiTree T) {
	//先序遍歷
	if (!BiTreeEmpty(T)) {
		//非空就調(diào)用PreTraverse
		PreTraverse(T, 1);//從第一個(gè)元素就開(kāi)始
	}
	printf("\n");
}


void InTraverse(SqBiTree T, int e) {
	//中序遍歷使用
	if (T[e] != '#') {
		InTraverse(T, 2 * e);
		visit(T[e]);
		InTraverse(T, 2 * e + 1);//中序遍歷，先左后中再右
	}
}



void InOrderTreaverse(SqBiTree T) {
	if (!BiTreeEmpty(T)) {
		InTraverse(T, 1);
	}
	printf("\n");
}

//后序遍歷
void PostTreaverse(SqBiTree T, int e) {
	if (T[e] != '#') {
		PostTreaverse(T, e * 2);
		PostTreaverse(T, e * 2 + 1);
		visit(T[e]);
	}

}

void PostOrderTraverse(SqBiTree T) {
	if (!BiTreeEmpty(T)){
		PostTreaverse(T, 1);
	}
	printf("\n");
}

//層序遍歷二叉樹(shù)
void LevelOrderTraverse(SqBiTree T) {
	int dep = BiTreeDepth(T);
	int tree_max = pow(dep, 2) - 1;//得到當(dāng)前深度下完全二叉樹(shù)應(yīng)該有多少結(jié)點(diǎn)
	for (int i = 1; i< tree_max; i++) {
		if (T[i] == '#') {
			continue;
		}//不用輸出‘#’  而且獲得的深度來(lái)看，不需要for很多沒(méi)有價(jià)值的 下標(biāo)  牛逼

		visit(T[i]);
	}
}



int main()
{
	TElemType e;
	SqBiTree Bt;
	InitBiTree(Bt);
	CreateBiTree(Bt);
	printf("先序遍歷結(jié)果為：");
	PreOrderTraverse(Bt);
	printf("中序遍歷結(jié)果為：");
	InOrderTreaverse(Bt);
	printf("后序遍歷結(jié)果為：");
	PostOrderTraverse(Bt);
	LevelOrderTraverse(Bt);
	return 0;
}

三、二叉樹(shù)的基本操作（鏈表版本） 1.鏈表節(jié)點(diǎn)結(jié)構(gòu)體
//使用鏈表的 形式來(lái)實(shí)現(xiàn)二叉樹(shù)的基本操作

#define MaxSize 20
typedef struct TreeNode {
	int data;//數(shù)據(jù)域
	struct TreeNode* lchild;
	struct TreeNode* rchild;//指向左右孩子結(jié)點(diǎn)

}BiNode,*BiTree;
2.先序創(chuàng)建二叉樹(shù)
//先序創(chuàng)建二叉樹(shù)
BiTree CreateTree() {
	int data;
	scanf("%d", &data);  //這樣每一次輸入都會(huì)進(jìn)行傳值操作  直到輸入的數(shù)值小于0然后開(kāi)始右結(jié)點(diǎn)  使用遞歸的方法進(jìn)行創(chuàng)建二叉樹(shù)
	BiTree root;
	if (data<= 0) {
		return NULL;
	}
	else {
		root = (BiTree)malloc(sizeof(BiNode));
		root->data = data;
		root->lchild = CreateTree();
		root->rchild = CreateTree();//先序傳參  制造先序二叉樹(shù)
		
	}
	return root;
}
1）中序后序創(chuàng)建二叉樹(shù)

?中序、后序創(chuàng)建二叉樹(shù)的代碼實(shí)現(xiàn)就是更改先序創(chuàng)建二叉樹(shù)中的??root->data = data;? 位置

更改遞歸的先后就可以，到這個(gè)地方大家應(yīng)該就明白如何操作了（我看了一圈的csdn也沒(méi)有多少人去說(shuō)明這個(gè)事情，這是我在群里問(wèn)了其他人的回復(fù)：更換遞歸和root->data = data；的位置）

3.先序遍歷二叉樹(shù) 1）遞歸操作

所有的二叉樹(shù)的遍歷，不管先序、中序、后序，都可以通過(guò)遞歸的形式是實(shí)現(xiàn)。這個(gè)是最簡(jiǎn)單，最好理解的方式。在不強(qiáng)調(diào)不能使用遞歸的前提下，建議優(yōu)先使用遞歸。

先序、中序、后序，只是跟上文那個(gè)什么序進(jìn)行遍歷創(chuàng)建二叉樹(shù)一個(gè)道理，更改遞歸的位置即可~

//先序遍歷
//1.遞歸操作  實(shí)現(xiàn)先序遍歷
void PreTreeTraverse(BiTree root) {
	if (root) {
		//只要根節(jié)點(diǎn)不是空
		printf("%d", root->data);
		PreTreeTraverse(root->lchild);
		PreTreeTraverse(root->rchild);
	}
}
2）非遞歸操作

非遞歸操作中，先序、中序、后序操作都有不同，所以這個(gè)比較難理解和記憶，但是有一個(gè)共同點(diǎn)是，都需要使用輔助棧的形式（定義一個(gè)類似于棧的 BiTree數(shù)組）?。?！

這個(gè)寫(xiě)法大概思路是創(chuàng)建輔助棧，然后創(chuàng)建新節(jié)點(diǎn)，然后判斷是否根節(jié)點(diǎn)為NULL（NULL的話不需要 遍歷直接返回），設(shè)置棧數(shù)組的變量top? 提前賦值為-1（任意都可以? 按照個(gè)人習(xí)慣來(lái)），然后是top++（top現(xiàn)在為0）將root賦值給stack[0]? 然后進(jìn)入while循環(huán)（判斷依據(jù)是棧中有沒(méi)有元素 top>-1），因?yàn)槭窍刃蛩灾苯虞敵鰎oot節(jié)點(diǎn)數(shù)據(jù)，然后使用 if 語(yǔ)句判斷是否有左右孩子（先判斷右孩子的原因是，使得最后一個(gè)放進(jìn)去的是左孩子節(jié)點(diǎn)，這樣出棧的時(shí)候，是左孩子先出）

//2.非遞歸操作
//引入輔助棧
void PreOrderTraverseNonRec(BiTree root) {
	BiTree stack[MaxSize];
	BiTree p;
	int top = -1;
	if (root != NULL) {
		//表示非空樹(shù)
		top++;
		stack[top] = root;//將root放在stack數(shù)組中
		//棧不空的時(shí)候循環(huán)
		while (top >-1) {    //這個(gè)寫(xiě)法牛逼的地方在于 首先是先輸出根結(jié)點(diǎn)的數(shù)值然后出棧top--然后判斷是否有右孩子，放進(jìn)棧里面 然后
			//出棧并訪問(wèn)結(jié)點(diǎn)       //這個(gè)時(shí)候如果有孩子的話 top>-1 還能進(jìn)入while循環(huán) 然后輸出左孩子（有的話）然后出棧 在判斷這個(gè)孩子有沒(méi)有左右孩子，一旦是沒(méi)有了，你們前面壓棧的右孩子就可以輸出了
			                     //輸出右孩子之后，出棧 然后進(jìn)行判斷右孩子是由有左右孩子   模擬遞歸操縱s
			p = stack[top];
			top--;
			printf("%d", p->data);
			//右孩子入棧
			if (p->rchild != NULL) {
				top++;
				stack[top] = p->rchild;
			}
			//左孩子入棧
			if (p->lchild != NULL) {
				top++;
				stack[top] = p->rchild;
			}
		}
	}
}
4.中序遍歷二叉樹(shù) 1）遞歸操作

這個(gè)時(shí)候就能發(fā)現(xiàn)，有一定的規(guī)律在遞歸操作上

//有了先序遍歷操作就可以寫(xiě)出來(lái)中序和后序遍歷操作

//2.中序遍歷
//1）遞歸操作
void InTreeTreaver(BiTree root) {
	if (root) {
		//判斷根節(jié)點(diǎn)是否為空
		InTreeTreaver(root->lchild);
		printf("%d", root->data);
		InTreeTreaver(root->rchild);
	}
}
2）非遞歸操作
//2)非遞歸
void InTreeTreaver2(BiTree root) {
	//創(chuàng)建臨時(shí)棧
	BiTree stack[MaxSize];
	BiTree p;
	int top = -1;
	if (root) {
		p = root;
		while (top >-1 || p != NULL) {
			//掃描所有的左孩子進(jìn)棧   其實(shí)在左孩子進(jìn)棧的過(guò)程中就只剩下右孩子
			while (p != NULL) {
				top++;
				stack[top] = p;
				p = p->lchild;
			}
			//掃描完成之后開(kāi)始出棧
			if (top >-1) {
				p = stack[top];
				printf("%d", p->data);
				top--;
				//掃描右孩子
				p = p->rchild;
			}
		}
	}
}

5.后序遍歷二叉樹(shù) 1）遞歸操作
//3.后序遍歷

void PostTreeTraverse(BiTree root) {
	if (root) {
		PostTreeTraverse(root->lchild);
		PostTreeTraverse(root->rchild);
		printf("%d", root->data);
	}
}
2）非遞歸操作
//2)非遞歸
 //后序遍歷二叉樹(shù):非遞歸實(shí)現(xiàn) 
void PostOrderTraverseNonRec(BiTree root) {
	BiTree stack[MaxSize];
	BiTree p;
	int top = -1;
	int sign;
	if (root != NULL) {
		do {
			//root節(jié)點(diǎn)入棧
			while (root != NULL) {
				top++;
				stack[top] = root;
				root = root->lchild;
			}
			//p指向棧頂前一個(gè)已訪問(wèn)節(jié)點(diǎn)
			p = NULL;
			//置root為已訪問(wèn)
			sign = 1;
			while (top != -1 && sign) {
				//取出棧頂節(jié)點(diǎn)
				root = stack[top];
				//右孩子不存在或右孩子已訪問(wèn)則訪問(wèn)root
				if (root->rchild == p) {
					printf("%d ", root->data);
					top--;
					//p指向被訪問(wèn)的節(jié)點(diǎn)
					p = root;
				}
				else {
					//root指向右孩子節(jié)點(diǎn)
					root = root->rchild;
					//置未訪問(wèn)標(biāo)記
					sign = 0;
				}
			}
		} while (top != -1);
	}
}
6.求第k層節(jié)點(diǎn)的個(gè)數(shù)

/遇到葉子節(jié)點(diǎn) ?正好 ?因?yàn)槟阆胍氖堑趉層 所以就k-1遞歸 然后等你到第k層的時(shí)候也就是k=1的時(shí)候 自然就返回1 了

你輸入的第k層，在遞歸k-1次之后到達(dá)第k層，自然就返回1了 ，然后就得到對(duì)應(yīng)第k層的數(shù)值了

int LevelNodeNum(BiTree root,int k) {
	//進(jìn)行判斷是否為空 或者k數(shù)值不對(duì)
	if (root == NULL || k< 1) {
		return 0;
	}

	if (k == 1) {
		return 1;//遇到葉子節(jié)點(diǎn)  正好  因?yàn)槟阆胍氖堑趉層 所以就k-1遞歸 然后等你到第k層的時(shí)候也就是k=1的時(shí)候 自然就返回1 了
	}
	else {
		return LevelNodeNum(root->lchild, k - 1) + LevelNodeNum(root->rchild,k - 1);
	}
}
7.求二叉樹(shù)的深度
//求二叉樹(shù)的大深度

//使用遞歸的方式來(lái)實(shí)現(xiàn)
int maxTreeDeapth(BiTree root) {
	if (root) {
		int maxLeft = maxTreeDeapth(root->lchild);
		int maxRight = maxTreeDeapth(root->rchild);
		if (maxLeft >maxRight) {
			return maxLeft + 1;
		}
		else {
			return maxRight + 1;
		}
	}
	return 0;
}
8.二叉樹(shù)的葉子節(jié)點(diǎn)的個(gè)數(shù)
//求二叉樹(shù)葉子節(jié)點(diǎn)個(gè)數(shù)

int LeafNodeNum(BiTree root) {
	//這一步是為了判斷是否為空樹(shù)  空樹(shù)自然葉子節(jié)點(diǎn)為0
	if (root == NULL) {
		return 0;
	}


	if (root->lchild == NULL && root->rchild == NULL) {
		return 1;//葉子節(jié)點(diǎn)的特點(diǎn)  沒(méi)有孩子  所以用遞歸  可以得到葉子節(jié)點(diǎn)的個(gè)數(shù)
	}
	else {
		return LeafNodeNum(root->lchild) + LeafNodeNum(root->rchild);

	}

}
9.二叉樹(shù)的總節(jié)點(diǎn)的個(gè)數(shù)

求二叉樹(shù)的葉子節(jié)點(diǎn)的個(gè)數(shù)和求總結(jié)點(diǎn)的個(gè)數(shù)，不同的是在使用遞歸的時(shí)候，如果是為了求葉子節(jié)點(diǎn)只需要在這個(gè)節(jié)點(diǎn)沒(méi)有左右孩子的時(shí)候 return 1? 在遞歸的時(shí)候不會(huì)+1

但是在求總結(jié)點(diǎn)個(gè)數(shù)的時(shí)候，使用遞歸的時(shí)候都會(huì)+1，這個(gè)+1表示的是加上這個(gè)節(jié)點(diǎn)了，其他方面沒(méi)有不同

//二叉樹(shù)的總節(jié)點(diǎn)個(gè)數(shù)

//使用遞歸的方法實(shí)現(xiàn)

int CountNode(BiTree root) {
	if (root) {
		if (root->lchild == NULL && root->rchild == NULL) {
			return 1;//遇到葉子節(jié)點(diǎn)返回1
		}
		else {
			return CountNode(root->lchild) + CountNode(root->rchild)+1;
			//每一次正常運(yùn)行都會(huì)加一并表示節(jié)點(diǎn)，直到遇到葉子節(jié)點(diǎn)返回?cái)?shù)值1
		}
	}
}
10.遞歸查找指定元素x的節(jié)點(diǎn)

先進(jìn)行左孩子遞歸一直找，找不到的時(shí)候就會(huì)使用右孩子遞歸了，如果再找不到就返回NULL，表示沒(méi)有這個(gè)元素為x的節(jié)點(diǎn)

//查找元素為x的節(jié)點(diǎn)
//采用遞歸的方法

BiTree SearchNode(BiTree root, int x) {
	if (root) {//這個(gè)是判斷是否為NULL空樹(shù)   第二是為了判斷左右孩子是否為NULL
		if (root->data == x) {
			return root;//如果數(shù)據(jù)對(duì)了就返回相應(yīng)節(jié)點(diǎn)
		}
		else {
			BiTree p;//創(chuàng)建新節(jié)點(diǎn)位置
			p = SearchNode(root->lchild, x);//使用遍歷 先左孩子進(jìn)行比較 
			if (!p) {//左孩子比較完成之后在進(jìn)行右孩子遞歸比較  只要有有孩子就可以一直比較
				p = SearchNode(root->rchild, x);

			}
			return p;
		}
	}
	return NULL;
}
11.全部代碼：
#define _CRT_SECURE_NO_WARNINGS
#include#include#include#include//使用鏈表的 形式來(lái)實(shí)現(xiàn)二叉樹(shù)的基本操作

#define MaxSize 20
typedef struct TreeNode {
	int data;//數(shù)據(jù)域
	struct TreeNode* lchild;
	struct TreeNode* rchild;//指向左右孩子結(jié)點(diǎn)

}BiNode,*BiTree;


//我們規(guī)定，節(jié)點(diǎn)值必須為大于0的數(shù)值 ，如果是0表示奇數(shù)繼續(xù)往下創(chuàng)建子節(jié)點(diǎn)的操作

//二叉樹(shù)的操作通常使用遞歸的方法，二叉樹(shù)的操作可以分為兩類，一類是需要改變二叉樹(shù)的結(jié)構(gòu)，比如二叉樹(shù)的創(chuàng)建，結(jié)點(diǎn)的刪除等等
//這類操作，傳入的二叉樹(shù)的 結(jié)點(diǎn)參數(shù)為二叉樹(shù)指針的地址，這種參數(shù)的傳入，便于更改二叉樹(shù)結(jié)構(gòu)體的指針

//我們使用遞歸的方法創(chuàng)建左右子樹(shù)


//第一種創(chuàng)建二叉樹(shù)，使用一級(jí)指針

//先序創(chuàng)建二叉樹(shù)
BiTree CreateTree() {
	int data;
	scanf("%d", &data);  //這樣每一次輸入都會(huì)進(jìn)行傳值操作  直到輸入的數(shù)值小于0然后開(kāi)始右結(jié)點(diǎn)  使用遞歸的方法進(jìn)行創(chuàng)建二叉樹(shù)
	BiTree root;
	if (data<= 0) {
		return NULL;
	}
	else {
		root = (BiTree)malloc(sizeof(BiNode));
		root->data = data;
		root->lchild = CreateTree();
		root->rchild = CreateTree();//先序傳參  制造先序二叉樹(shù)
		
	}
	return root;
}

//先序遍歷
//1.遞歸操作  實(shí)現(xiàn)先序遍歷
void PreTreeTraverse(BiTree root) {
	if (root) {
		//只要根節(jié)點(diǎn)不是空
		printf("%d", root->data);
		PreTreeTraverse(root->lchild);
		PreTreeTraverse(root->rchild);
	}
}

//2.非遞歸操作
//引入輔助棧
void PreOrderTraverseNonRec(BiTree root) {
	BiTree stack[MaxSize];
	BiTree p;
	int top = -1;
	if (root != NULL) {
		//表示非空樹(shù)
		top++;
		stack[top] = root;//將root放在stack數(shù)組中
		//棧不空的時(shí)候循環(huán)
		while (top >-1) {    //這個(gè)寫(xiě)法牛逼的地方在于 首先是先輸出根結(jié)點(diǎn)的數(shù)值然后出棧top--然后判斷是否有右孩子，放進(jìn)棧里面 然后
			//出棧并訪問(wèn)結(jié)點(diǎn)       //這個(gè)時(shí)候如果有孩子的話 top>-1 還能進(jìn)入while循環(huán) 然后輸出左孩子（有的話）然后出棧 在判斷這個(gè)孩子有沒(méi)有左右孩子，一旦是沒(méi)有了，你們前面壓棧的右孩子就可以輸出了
			                     //輸出右孩子之后，出棧 然后進(jìn)行判斷右孩子是由有左右孩子   模擬遞歸操縱s
			p = stack[top];
			top--;
			printf("%d", p->data);
			//右孩子入棧
			if (p->rchild != NULL) {
				top++;
				stack[top] = p->rchild;
			}
			//左孩子入棧
			if (p->lchild != NULL) {
				top++;
				stack[top] = p->rchild;
			}
		}
	}
}


//有了先序遍歷操作就可以寫(xiě)出來(lái)中序和后序遍歷操作

//2.中序遍歷
//1）遞歸操作
void InTreeTreaver(BiTree root) {
	if (root) {
		//判斷根節(jié)點(diǎn)是否為空
		InTreeTreaver(root->lchild);
		printf("%d", root->data);
		InTreeTreaver(root->rchild);
	}
}
//2)非遞歸
void InTreeTreaver2(BiTree root) {
	//創(chuàng)建臨時(shí)棧
	BiTree stack[MaxSize];
	BiTree p;
	int top = -1;
	if (root) {
		p = root;
		while (top >-1 || p != NULL) {
			//掃描所有的左孩子進(jìn)棧   其實(shí)在左孩子進(jìn)棧的過(guò)程中就只剩下右孩子
			while (p != NULL) {
				top++;
				stack[top] = p;
				p = p->lchild;
			}
			//掃描完成之后開(kāi)始出棧
			if (top >-1) {
				p = stack[top];
				printf("%d", p->data);
				top--;
				//掃描右孩子
				p = p->rchild;
			}
		}
	}
}

//3.后序遍歷

void PostTreeTraverse(BiTree root) {
	if (root) {
		PostTreeTraverse(root->lchild);
		PostTreeTraverse(root->rchild);
		printf("%d", root->data);
	}
}

//2)非遞歸
 //后序遍歷二叉樹(shù):非遞歸實(shí)現(xiàn) 
void PostOrderTraverseNonRec(BiTree root) {
	BiTree stack[MaxSize];
	BiTree p;
	int top = -1;
	int sign;
	if (root != NULL) {
		do {
			//root節(jié)點(diǎn)入棧
			while (root != NULL) {
				top++;
				stack[top] = root;
				root = root->lchild;
			}
			//p指向棧頂前一個(gè)已訪問(wèn)節(jié)點(diǎn)
			p = NULL;
			//置root為已訪問(wèn)
			sign = 1;
			while (top != -1 && sign) {
				//取出棧頂節(jié)點(diǎn)
				root = stack[top];
				//右孩子不存在或右孩子已訪問(wèn)則訪問(wèn)root
				if (root->rchild == p) {
					printf("%d ", root->data);
					top--;
					//p指向被訪問(wèn)的節(jié)點(diǎn)
					p = root;
				}
				else {
					//root指向右孩子節(jié)點(diǎn)
					root = root->rchild;
					//置未訪問(wèn)標(biāo)記
					sign = 0;
				}
			}
		} while (top != -1);
	}
}
//求二叉樹(shù)的大深度

//使用遞歸的方式來(lái)實(shí)現(xiàn)
int maxTreeDeapth(BiTree root) {
	if (root) {
		int maxLeft = maxTreeDeapth(root->lchild);
		int maxRight = maxTreeDeapth(root->rchild);
		if (maxLeft >maxRight) {
			return maxLeft + 1;
		}
		else {
			return maxRight + 1;
		}
	}
	return 0;
}

//求二叉樹(shù)葉子節(jié)點(diǎn)個(gè)數(shù)

int LeafNodeNum(BiTree root) {
	//這一步是為了判斷是否為空樹(shù)  空樹(shù)自然葉子節(jié)點(diǎn)為0
	if (root == NULL) {
		return 0;
	}


	if (root->lchild == NULL && root->rchild == NULL) {
		return 1;//葉子節(jié)點(diǎn)的特點(diǎn)  沒(méi)有孩子  所以用遞歸  可以得到葉子節(jié)點(diǎn)的個(gè)數(shù)
	}
	else {
		return LeafNodeNum(root->lchild) + LeafNodeNum(root->rchild);

	}

}

////// 求k層節(jié)點(diǎn)個(gè)數(shù)
//////int LevelNodeNum(BiTree root,int k) {
	//進(jìn)行判斷是否為空 或者k數(shù)值不對(duì)
	if (root == NULL || k< 1) {
		return 0;
	}

	if (k == 1) {
		return 1;//遇到葉子節(jié)點(diǎn)  正好  因?yàn)槟阆胍氖堑趉層 所以就k-1遞歸 然后等你到第k層的時(shí)候也就是k=1的時(shí)候 自然就返回1 了
	}
	else {
		return LevelNodeNum(root->lchild, k - 1) + LevelNodeNum(root->rchild,k - 1);
	}
}

//二叉樹(shù)的總節(jié)點(diǎn)個(gè)數(shù)

//使用遞歸的方法實(shí)現(xiàn)

int CountNode(BiTree root) {
	if (root) {
		if (root->lchild == NULL && root->rchild == NULL) {
			return 1;//遇到葉子節(jié)點(diǎn)返回1
		}
		else {
			return CountNode(root->lchild) + CountNode(root->rchild)+1;
			//每一次正常運(yùn)行都會(huì)加一并表示節(jié)點(diǎn)，直到遇到葉子節(jié)點(diǎn)返回?cái)?shù)值1
		}
	}
}


//查找元素為x的節(jié)點(diǎn)
//采用遞歸的方法

BiTree SearchNode(BiTree root, int x) {
	if (root) {//這個(gè)是判斷是否為NULL空樹(shù)   第二是為了判斷左右孩子是否為NULL
		if (root->data == x) {
			return root;//如果數(shù)據(jù)對(duì)了就返回相應(yīng)節(jié)點(diǎn)
		}
		else {
			BiTree p;//創(chuàng)建新節(jié)點(diǎn)位置
			p = SearchNode(root->lchild, x);//使用遍歷 先左孩子進(jìn)行比較 
			if (!p) {//左孩子比較完成之后在進(jìn)行右孩子遞歸比較  只要有有孩子就可以一直比較
				p = SearchNode(root->rchild, x);

			}
			return p;
		}
	}
	return NULL;
}
int main()
{
	BiTree root = NULL;
	root = CreateTree();
	PreTreeTraverse(root);
	printf("\n");
	int len = maxTreeDeapth(root);
	printf("%d",len);
	printf("\n");
	int num=LevelNodeNum(root, 2);
	printf("%d\n", num);
	printf("%d\n", CountNode(root));
	return 0;
}
總結(jié)

1.? 對(duì)于二叉樹(shù)的學(xué)習(xí)，我已經(jīng)使用過(guò)了順序表的形式和鏈表的形式，感覺(jué)上，第一次在二叉樹(shù)上發(fā)現(xiàn)了遞歸的神奇用處，之前使用的遞歸的時(shí)候都是一些很小的問(wèn)題的解決，這一次在二叉樹(shù)的遍歷上面，無(wú)論是如何實(shí)現(xiàn)的二叉樹(shù)，在進(jìn)行先序、中序、后序等遍歷的時(shí)候，使用遞歸的方法是最為簡(jiǎn)單，也是最好理解的。

2.雖然在學(xué)過(guò)Java之后覺(jué)得C為基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)真的好麻煩，Java會(huì)有相應(yīng)的框架，一時(shí)畏難心理就有了，但是在最近的學(xué)習(xí)來(lái)看，數(shù)據(jù)結(jié)構(gòu)是一門很有意思的課程，在這個(gè)地方，感受到數(shù)據(jù)結(jié)構(gòu)的魅力，希望大家不要畏難，感受敲完代碼理解代碼的那一刻的快樂(lè)，大家加油！??！

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧


當(dāng)前文章：萬(wàn)字超全詳解：二叉樹(shù)的基本操作（C語(yǔ)言版本）-創(chuàng)新互聯(lián)
文章出自：http://weahome.cn/article/pgdpj.html

其他資訊

在線咨詢

微信咨詢

電話咨詢

028-86922220（工作日）

18980820575（7×24）

提交需求

返回頂部