文章目錄

前言
一、1.樹概念及結構
- 1.1樹的概念
- 1.2 樹的相關概念
- 1.3 樹的表示
- 1.4 樹在實際中的運用（表示檔案系統的目錄樹結構）
二、叉樹概念及結構
- 2.1概念
- 2.2現實中的二叉樹：
- 2.3 特殊的二叉樹：
- 2.4 二叉樹的性質
- 2.5 二叉樹的存盤結構
三、二叉樹的順序結構及實作
- 3.1 二叉樹的順序結構
- 3.2 堆的概念及結構
- 3.3 堆的實作
- 3.4堆的應用
- - 3.4.1 堆排序
  - 3.4.2 TOP-K問題
四、二叉樹鏈式結構的實作
- 4.1 前置說明
- 4.2二叉樹的遍歷
- - 4.2.1 前序、中序以及后序遍歷
  - 4.2.2 層序遍歷
  - 4.2.3判斷二叉樹是否是完全二叉樹
- 4.3 節點個數以及高度等
- 4.5 二叉樹的創建和銷毀

前言

本篇是介紹關于樹的基本概念、性質，進而對一個特殊的樹（二叉樹）進行重點介紹，而在二叉樹中，我們又介紹堆的概念、性質、代碼實作一個堆以及堆的應用，最后再實作二叉樹的遍歷、來讓我們對二叉樹有一定的認識，但是本篇不討論如何用二叉樹存盤資料，因為一顆普通的二叉樹對資料存盤過于復雜，而如果用C語言來實作更是難上加難，對我們沒有太大的用處，所以關于存盤資料的樹，我們之后用更高階的語言（C++）實作，類似搜索二叉樹、平衡搜索二叉樹、AVL樹、紅黑樹到最后的B樹，

一、1.樹概念及結構

1.1樹的概念

樹是一種非線性的資料結構，它是由n（n>=0）個有限結點組成一個具有層次關系的集合，把它叫做樹是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的，

有一個特殊的結點，稱為根結點，根節點沒有前驅結點
除根節點外，其余結點被分成M(M>0)個互不相交的集合T1、T2、……、Tm，其中每一個集合Ti(1<= i <= m)又是一棵結構與樹類似的子樹，每棵子樹的根結點有且只有一個前驅，可以有0個或多個后繼
因此，樹是遞回定義的，

數在現實中的形狀：
在這里插入圖片描述
我們將它抽象出來表示：

注意：樹形結構中，子樹之間不能有交集，否則就不是樹形結構，
下面就是一些錯誤示例：

在這里插入圖片描述

1.2 樹的相關概念

以下面這張圖片為例：
在這里插入圖片描述

節點的度：一個節點含有的子樹的個數稱為該節點的度；如上圖：A的為6，
葉節點或終端節點：度為0的節點稱為葉節點；如上圖：B、C、H、I…等節點為葉節點，
非終端節點或分支節點：度不為0的節點；如上圖：D、E、F、G…等節點為分支節點，
雙親節點或父節點：若一個節點含有子節點，則這個節點稱為其子節點的父節點；如上圖：A是B的父節點，
孩子節點或子節點：一個節點含有的子樹的根節點稱為該節點的子節點；如上圖：B是A的孩子節點
兄弟節點：具有相同父節點的節點互稱為兄弟節點；如上圖：B、C是兄弟節點
樹的度：一棵樹中，最大的節點的度稱為樹的度；如上圖：樹的度為6
節點的層次：從根開始定義起，根為第1層，根的子節點為第2層，以此類推；
樹的高度或深度：樹中節點的最大層次；如上圖：樹的高度為4
堂兄弟節點：雙親在同一層的節點互為堂兄弟；如上圖：H、I互為兄弟節點
節點的祖先：從根到該節點所經分支上的所有節點；如上圖：A是所有節點的祖先
子孫：以某節點為根的子樹中任一節點都稱為該節點的子孫，如上圖：所有節點都是A的子孫
森林：由m（m>0）棵互不相交的樹的集合稱為森林

上面這么多的概念，我們沒必要全部精通，我們重點掌握葉節點或終端節點、雙親節點或父節點、孩子節點或子節點、樹的高度或深度、節點的祖先、森林，其他了解一下，

1.3 樹的表示

樹結構相對線性表就比較復雜了，要存盤表示起來就比較麻煩了，既然保存值域，也要保存結點和結點之間的關系，實際中樹有很多種表示方式如：雙親表示法，孩子表示法、孩子雙親表示法以及孩子兄弟表示法等，我們這里就簡單的了解其中最常用的孩子兄弟表示法，可以說這是比較優秀的表示方法了，這個是什么意思呢？我們用一個結構體來表示：

typedef int DataType;
struct Node
{
 struct Node* _firstChild1; // 第一個孩子結點
 struct Node* _pNextBrother; // 指向其下一個兄弟結點
 DataType _data; // 結點中的資料域
};

用一張圖片形象的表示：
在這里插入圖片描述

1.4 樹在實際中的運用（表示檔案系統的目錄樹結構）

在這里插入圖片描述

二、叉樹概念及結構

2.1概念

一棵二叉樹是結點的一個有限集合，該集合:

1. 或者為空
1. 由一個根節點加上兩棵別稱為左子樹和右子樹的二叉樹組成

用圖片表示就是：
在這里插入圖片描述
從上圖可以看出：

1. 二叉樹不存在度大于2的結點
  位元科技
1. 二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹
  注意：對于任意的二叉樹都是由以下幾種情況復合而成的：

注意：對于任意的二叉樹都是由以下幾種情況復合而成的：
在這里插入圖片描述

2.2現實中的二叉樹：

在這里插入圖片描述

在這里插入圖片描述
上面這兩種圖片都可以形象的表示出來二叉樹，

2.3 特殊的二叉樹：

滿二叉樹：一個二叉樹，如果每一個層的結點數都達到最大值，則這個二叉樹就是滿二叉樹，也就是說，如果一個二叉樹的層數為K，且結點總數是 2^k - 1，則它就是滿二叉樹，
完全二叉樹：完全二叉樹是效率很高的資料結構，完全二叉樹是由滿二叉樹而引出來的，對于深度為K的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為K的滿二叉樹中編號從1至n的結點一一對應時稱之為完全二叉樹，要注意的是滿二叉樹是一種特殊的完全二叉樹，用我們的話來說就是，前k-1層是滿的節點，最后一層不是滿的節點且從左到右是連續的，

在這里插入圖片描述

2.4 二叉樹的性質

若規定根節點的層數為1，則一棵非空二叉樹的第i層上最多有 2^(i - 1)個結點.
若規定根節點的層數為1，則深度為h的二叉樹的最大結點數是 2^ h - 1
對任何一棵二叉樹, 如果度為0其葉結點個數為n0 , 度為2的分支結點個數為 n2,則有 n0＝ n2＋1
若規定根節點的層數為1，具有n個結點的滿二叉樹的深度，h= log（n+1） (ps：是log以2
為底，n+1為對數)
對于具有n個結點的完全二叉樹，如果按照從上至下從左至右的陣列順序對所有節點從0開始編號，則對于序號為i的結點有：

若i>0，i位置節點的雙親序號：(i-1)/2；i=0，i為根節點編號，無雙親節點

若2i+1<n，左孩子序號：2i+1，2i+1>=n否則無左孩子

若2i+2<n，右孩子序號：2i+2，2i+2>=n否則無右孩子

2.5 二叉樹的存盤結構

1. 順序存盤
順序結構存盤就是使用陣列來存盤，一般使用陣列只適合表示完全二叉樹，因為不是完全二叉樹會有空間的浪費，而現實中使用中只有堆才會使用陣列來存盤，二叉樹順序存盤在物理上是一個陣列，在邏輯上是一顆二叉樹，
在這里插入圖片描述
2. 鏈式存盤
二叉樹的鏈式存盤結構是指，用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關系，通常的方法是鏈表中每個結點由三個域組成，資料域和左右指標域，左右指標分別用來給出該結點左孩子和右孩子所在的鏈結點的存盤地址，鏈式結構又分為二叉鏈和三叉鏈，當前我們學習中一般都是二叉鏈，
在這里插入圖片描述

在這里插入圖片描述

三、二叉樹的順序結構及實作

3.1 二叉樹的順序結構

普通的二叉樹是不適合用陣列來存盤的，因為可能會存在大量的空間浪費，而完全二叉樹更適合使用順序結構存盤，現實中我們通常把堆(一種二叉樹)使用順序結構的陣列來存盤，需要注意的是這里的堆和作業系統虛擬行程地址空間中的堆是兩回事，一個是資料結構，一個是作業系統中管理記憶體的一塊區域分段
在這里插入圖片描述

3.2 堆的概念及結構

如果有一個關鍵碼的集合K = {K0 ，K1 ，K2 ，K3…，K(n-1) }，把它的所有元素按完全二叉樹的順序存盤方式存盤在一個一維陣列中，并滿足：Ki <=K(2i+1) (2i-1為下標) 且 Ki<=K(2i+2)（2i+2為下標） ( Ki>=K(2i+1) 且 Ki>=(2i+2) ) i = 0，1，2…，則稱為小堆(或大堆)，將根節點最大的堆叫做最大堆或大根堆，根節點最小的堆叫做最小堆或小根堆，
概念有點復雜，用一張圖片來表示：
在這里插入圖片描述

堆的性質：

堆中某個節點的值總是不大于或不小于其父節點的值；
堆總是一棵完全二叉樹，

3.3 堆的實作

Heap.h

#pragma once

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
#include<time.h>

typedef int HPDataType;
//完全二叉樹用陣列實作
//假設先建一個小堆
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;

void HeapInit(HP* hp);
void HeapDestroy(HP* hp);
void HeapPrint(HP* hp);
void HeapPush(HP* hp, HPDataType x);
void HeapPop(HP* hp);//刪堆頂資料
HPDataType HeapTop(HP* hp);
bool HeapEmpty(HP* hp);
int HeapSize(HP* hp);

void HeapSwap(HPDataType* px, HPDataType* py);//交換兩個數
void AdjustUp(HPDataType* a, int child);//插入時向上調整資料
void AdjustDown(HPDataType* a, int n, int parent);//堆頂資料向下調整

Heap.c

#define _CRT_SECURE_NO_WARNINGS
#include"Heap.h"

void HeapInit(HP* hp)
{
	assert(hp);
	hp->a = NULL;
	hp->capacity = hp->size = 0;
}

void HeapDestroy(HP* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));
	free(hp->a);
	hp->capacity = hp->size = 0;
}

void HeapPrint(HP* hp)
{
	assert(hp);
	for (int i = 0; i < hp->size; i++)
	{
		printf("%d ", hp->a[i]);
	}
	printf("\n");
}

void HeapSwap(HPDataType* px, HPDataType* py)
{
	HPDataType tmp = *px;
	*px = *py;
	*py = tmp;
}

void AdjustUp(HPDataType* a, int child)//插入時向上調整資料
{
	assert(a);
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] > a[parent])
		{
			HeapSwap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}

}

void HeapPush(HP* hp, HPDataType x)
{
	assert(hp);
	//插入資料時是否已滿
	if (hp->capacity == hp->size)
	{
		int newCapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newCapacity);
		if (NULL == tmp)
		{
			printf("realloc fail");
			exit(-1);
		}
		hp->a = tmp;
		hp->capacity = newCapacity;
	}

	hp->a[hp->size] = x;
	hp->size++;

	//插入時向上調整資料
	AdjustUp(hp->a, hp->size-1);

}

void AdjustDown(HPDataType* a, int n, int parent)//堆頂資料向下調整
{
	//不用定義兩個孩子，只需要一個左孩子，去找右孩子
	int child = parent * 2 + 1;
	while (child < n)
	{
		//判斷左孩子和右孩子誰小,是否沒有右孩子
		if (child+1 < n && a[child + 1] > a[child])
		{
			child++;
		}
		//比較孩子和雙親誰的大小
		if (a[child] > a[parent])
		{
			HeapSwap(&a[child], &a[parent]);
			parent = child;
			child = child * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapPop(HP* hp)//刪堆頂資料
{
	assert(hp);
	assert(!HeapEmpty(hp));
	//先交換堆頂的資料和最后一個的資料
	HeapSwap(&hp->a[0], &hp->a[hp->size - 1]);
	hp->size--;

	//堆頂資料向下調整
	AdjustDown(hp->a, hp->size, 0);
	
}

HPDataType HeapTop(HP* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));
	return hp->a[0];
}

bool HeapEmpty(HP* hp)
{
	assert(hp);
	return hp->size == 0;
}

int HeapSize(HP* hp)
{
	assert(hp);
	return hp->size;
}

3.4堆的應用

3.4.1 堆排序

堆排序即利用堆的思想來進行排序，總共分為兩個步驟：

建堆
升序：建大堆
降序：建小堆
利用堆洗掉思想來進行排序

建堆和堆洗掉中都用到了向下調整，因此掌握了向下調整，就可以完成堆排序，

void HeapSort(int* a, int n);//堆排序


void HeapSort(int* a, int n)//堆排序
{
	//假設排升序
	// 若果建小堆的話，我們在排升序的話時間復雜度就是O(n^2),沒有意義
	// 所以我們如果排升序的話就建大堆，排降序的話就建小堆   
	//方法一,從1開始往上調
	/*for (int i = 1; i < n; i++)
	{
		AdjustUp(a, i);
	}*/
	//方法二，從倒數第一個不為葉子節點開始網下調
	//建堆的復雜度為O(n)
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	//依次選數
	for (int end = n - 1; end > 0; end--)
	{
		HeapSwap(&a[end], &a[0]);
		/*再調堆，選出次小的數*/
		AdjustDown(a, end, 0);
	}

}

3.4.2 TOP-K問題

TOP-K問題：即求資料結合中前K個最大的元素或者最小的元素，一般情況下資料量都比較大，
比如：專業前10名、世界500強、富豪榜、游戲中前100的活躍玩家等，
對于Top-K問題，能想到的最簡單直接的方式就是排序，但是：如果資料量非常大，排序就不太可取了(可能
資料都不能一下子全部加載到記憶體中)，最佳的方式就是用堆來解決，基本思路如下：
一：用資料集合中前K個元素來建堆

前k個最大的元素，則建小堆
前k個最小的元素，則建大堆
二：用剩余的N-K個元素依次與堆頂元素來比較，不滿足則替換堆頂元素
將剩余N-K個元素依次與堆頂元素比完之后，堆中剩余的K個元素就是所求的前K個最小或者最大的元素，

void TestTopk();//查找前k個數
void PrintTopK(int* a, int n, int k);//找出前k個數，列印前k個數

void PrintTopK(int* a, int n, int k)
{
	HP hp;
	HeapInit(&hp);
	int i = 0;
	//	建立一個k個數的堆
	//假設找出前k個最大的數，就建小堆
	for (i = 0; i < k; i++)
	{
		HeapPush(&hp, a[i]);
	}
	//將剩下的n-k個數插入堆
	//如果之前建的是大堆，插入數的時候就會堵住
	//相反建的小堆的話，來的數越大就會越往下沉
	for (i = k; i < n; i++)
	{
		HPDataType top = HeapTop(&hp);
		//判斷堆頂的資料和插入的資料大小
		if (a[i] > top)
		{
			HeapPop(&hp);
			HeapPush(&hp, a[i]);
		}
	}

	//列印資料
	for (i = 0; i < k; i++)
	{
		printf("%d ", hp.a[i]);
	}
	printf("\n");
	HeapDestroy(&hp);
}

void TestTopk()
{
	//假設在檔案中有10000個資料
	int n = 10000;
	int* a = (int*)malloc(sizeof(int) * n);
	srand(time(0));
	for (int i = 0; i < n; ++i)
	{
		a[i] = rand() % 1000000;
	}
	//隨機位置設定前10個數
	a[5] = 1000000 + 1;
	a[1231] = 1000000 + 2;
	a[531] = 1000000 + 3;
	a[5121] = 1000000 + 4;
	a[115] = 1000000 + 5;
	a[2335] = 1000000 + 6;
	a[9999] = 1000000 + 7;
	a[76] = 1000000 + 8;
	a[423] = 1000000 + 9;
	a[3144] = 1000000 + 10;
	//找出前10個數
	PrintTopK(a, n, 10);
}

四、二叉樹鏈式結構的實作

4.1 前置說明

在學習二叉樹的基本操作前，需先要創建一棵二叉樹，然后才能學習其相關的基本操作，由于現在大家對二叉樹結構掌味訓不夠深入，為了降低大家學習成本，此處手動快速創建一棵簡單的二叉樹，快速進入二叉樹操作學習，等二叉樹結構了解的差不多時，我們反過頭再來研究二叉樹真正的創建方式，
二叉樹是：

空樹
非空：根節點，根節點的左子樹、根節點的右子樹組成的

從概念中可以看出，二叉樹定義是遞回式的，因此后序基本操作中基本都是按照該概念實作的，

4.2二叉樹的遍歷

4.2.1 前序、中序以及后序遍歷

學習二叉樹結構，最簡單的方式就是遍歷，所謂二叉樹遍歷(Traversal)是按照某種特定的規則，依次對二叉樹中的節點進行相應的操作，并且每個節點只操作一次，訪問結點所做的操作依賴于具體的應用問題，遍歷是二叉樹上最重要的運算之一，也是二叉樹上進行其它運算的基礎

我們先手動建立一顆樹


BTNode* BuyNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (NULL == node)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	node->data = x;
	node->left = NULL;
	node->right = NULL;
	return node;
}

BTNode* CreatBinaryTree()//建一個二叉樹
{
	BTNode* A = BuyNode('A');
	BTNode* B = BuyNode('B');
	BTNode* C = BuyNode('C');
	BTNode* D = BuyNode('D');
	BTNode* E = BuyNode('E');
	BTNode* F = BuyNode('F');

	A->left = B;
	A->right = C;
	B->left = D;
	C->left = E;
	C->right = F;
	return A;
}

此時這棵樹用圖片表示就是：
在這里插入圖片描述
按照規則，二叉樹的遍歷有：前序/中序/后序的遞回結構遍歷：

前序遍歷(Preorder Traversal 亦稱先序遍歷)——訪問根結點的操作發生在遍歷其左右子樹之前，
中序遍歷(Inorder Traversal)——訪問根結點的操作發生在遍歷其左右子樹之中（間），
后序遍歷(Postorder Traversal)——訪問根結點的操作發生在遍歷其左右子樹之后，

由于被訪問的結點必是某子樹的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解釋為根、根的左子樹和根的右子樹，NLR、LNR和LRN分別又稱為先根遍歷、中根遍歷和后根遍歷，

// 二叉樹前序遍歷
void PreOrder(BTNode* root);
// 二叉樹中序遍歷
void InOrder(BTNode* root);
// 二叉樹后序遍歷
void PostOrder(BTNode* root);

前序、中序和后續遍歷的代碼實作：

void PrevOrder(BTNode* root)//前序遍歷
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	else
	{
		printf("%c ", root->data);
		PrevOrder(root->left);
		PrevOrder(root->right);
	}
}

void InOrder(BTNode* root)//中序遍歷
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	else
	{
		InOrder(root->left);
		printf("%c ", root->data);
		InOrder(root->right);
	}
}

void PostOrder(BTNode* root)//后序遍歷
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	else
	{
		PostOrder(root->left);
		PostOrder(root->right);
		printf("%c ", root->data);
	}
}

4.2.2 層序遍歷

層序遍歷：除了先序遍歷、中序遍歷、后序遍歷外，還可以對二叉樹進行層序遍歷，設二叉樹的根節點所在層數為1，層序遍歷就是從所在二叉樹的根節點出發，首先訪問第一層的樹根節點，然后從左到右訪問第2層上的節點，接著是第三層的節點，以此類推，自上而下，自左至右逐層訪問樹的結點的程序就是層序遍歷，
此時我們還是先建立一顆數：

BTNode* BuyNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (NULL == node)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	node->data = x;
	node->left = NULL;
	node->right = NULL;
	return node;
}

BTNode* CreatBinaryTree()//建一個二叉樹
{
	BTNode* A = BuyNode('A');
	BTNode* B = BuyNode('B');
	BTNode* C = BuyNode('C');
	BTNode* D = BuyNode('D');
	BTNode* E = BuyNode('E');
	BTNode* F = BuyNode('F');

	A->left = B;
	A->right = C;
	B->left = D;
	C->left = E;
	C->right = F;
	return A;
}

在這里插入圖片描述
由于層序遍歷的性質我們選擇用佇列實作層序遍歷：

//層序遍歷
void LevelOrder(BTNode* root);

代碼實作

//層序遍歷
//1.先入根
//2.當前節點出來，把孩子帶進去，這樣上一層出來的時候帶入下一層
//3.佇列為空的時候就說明最后一層就沒有節點了，
void LevelOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	Queue q;
	QueueInit(&q);
	//先將第一個節點入進去
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		//保存頭節點
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		printf("%c ", front->data);
		//帶頭結點節點的孩子
		if (front->left != NULL)
		{
			QueuePush(&q, front->left);

		}
		if (front->right != NULL)
		{
			QueuePush(&q, front->right);
		}
	}
	printf("\n");
	QueueDestroy(&q);
}

如果對堆疊代碼不熟悉可以參考下面這篇博客：
【資料結構從0到1】第三篇：堆疊和佇列

4.2.3判斷二叉樹是否是完全二叉樹

我們根據上面樹的層序遍歷，可以依照同樣的方法來判斷一顆樹是否是完全二叉樹：

// 判斷二叉樹是否是完全二叉樹
bool BinaryTreeComplete(BTNode* root);

代碼實作：

// 判斷二叉樹是否是完全二叉樹
//1.先入根
//2.當前節點出來，把孩子帶進去，這樣上一層出來的時候帶入下一層
//3.當頭節點為空的時候就不在入孩子節點
//4.判斷佇列里面是否含有非空節點，
bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	//先將頭節點入進去
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		//
		if (front == NULL)
		{
			break;
		}
		QueuePush(&q, front->left);
		QueuePush(&q, front->right);
	}
	while(!(QueueEmpty(&q)))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front)
		{
			QueueDestroy(&q);
			return false;
		}
	}
	QueueDestroy(&q);
	return true;
}

4.3 節點個數以及高度等

//二叉樹節點個數
int BinaryTreeSize(BTNode* root);
// 二叉樹葉子節點個數
int BinaryTreeLeafSize(BTNode* root);
// 二叉樹深度/高度
int BinaryTreeDepth(BTNode* root);
// 二叉樹第k層節點個數
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉樹查找值為x的節點
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);

代碼實作：

int BinaryTreeSize(BTNode* root)//二叉樹節點個數
{
	return root == NULL ? 0 : 
		BinaryTreeSize(root->left) + \
	    BinaryTreeSize(root->right) + 1;
}

// 二叉樹葉子節點個數
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	else
	{
		return BinaryTreeLeafSize(root->left) + \
		BinaryTreeLeafSize(root->right);
	}	
}

// 二叉樹深度/高度
int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	else
	{
		//查找左樹的深度
		int leftDepth = BinaryTreeDepth(root->left);
		//查找右樹的深度
		int rightDepth = BinaryTreeDepth(root->right);
		return leftDepth > rightDepth ? leftDepth + 1: rightDepth + 1;
	}
}

 /*二叉樹第k層節點個數*/
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	assert(k >= 1);
	if (root == NULL)
	{
		return 0;
	}
	//求第一層就是1個節點，或則當到了第k減為1，說明就到了第k層，回傳1
	if (k == 1)
	{
		return 1;
	}
	else
	{
		//找左樹和右樹的第k層節點數
		return BinaryTreeLevelKSize(root->left, k - 1) + \
			BinaryTreeLevelKSize(root->right, k - 1);
	}
}

// 二叉樹查找值為x的節點
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	//當前節點的值為x，就回傳
	if (root->data == x)
	{
		return root;
	}
	else
	{
		//先查找左樹上是否有x,找到就回傳當前位置
		BTNode* leftRet = BinaryTreeFind(root->left, x);
		if (leftRet != NULL)
		{
			return leftRet;
		}
		//再查找右樹上是否有x,找到就回傳當前位置
		BTNode* rightRet = BinaryTreeFind(root->right, x);
		if (rightRet != NULL)
		{
			return rightRet;

		}
	}
	//如果左右兩樹都沒有x,就回傳空
	return NULL;
}

4.5 二叉樹的創建和銷毀

樹的建立：
二叉樹的構建及遍歷 OJ鏈接

//思路：1.先通過輸入的前序陣列將這棵樹建立
//      2.中序列印這顆樹
#include<stdio.h>
#include<stdlib.h>

struct TreeNode
{
    struct TreeNode* left;
    struct TreeNode* right;
    char val;
};

struct TreeNode* CreateTree(char* str, int* pi)
{
    if(str[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }
    
    struct TreeNode* root= (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = str[*pi];
    (*pi)++;
    root->left = CreateTree(str, pi);
    root->right = CreateTree(str, pi);
    return root;
}

void InOrder(struct TreeNode* root)
{
    if(root == NULL)
    {
        return;
    }
    else
    {
        InOrder(root->left);
        printf("%c ", root->val);
        InOrder(root->right);
    }
}

int main()
{
    char str[100];
    scanf("%s", str);
    int i = 0;
   //建樹
    struct TreeNode* root = CreateTree(str, &i);
    //中序列印
    InOrder(root);
    return 0;
}

樹的銷毀：

// 二叉樹銷毀
void BinaryTreeDestory(BTNode* root);

代碼實作：

// 二叉樹銷毀
void BinaryTreeDestory(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	BinaryTreeDestory(root->left);
	BinaryTreeDestory(root->right);
	free(root);
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/356978.html

標籤：java

上一篇：學好類與物件輕松入門資料結構（上）--------快樂人的JAVA初學日記[5]

下一篇：經典Java-SpringCloud面試題

【資料結構從0到1】第四篇：二叉樹

文章目錄

前言

一、1.樹概念及結構

1.1樹的概念

1.2 樹的相關概念

1.3 樹的表示

1.4 樹在實際中的運用（表示檔案系統的目錄樹結構）

二、叉樹概念及結構

2.1概念

2.2現實中的二叉樹：

2.3 特殊的二叉樹：

2.4 二叉樹的性質

2.5 二叉樹的存盤結構

三、二叉樹的順序結構及實作

3.1 二叉樹的順序結構

3.2 堆的概念及結構

3.3 堆的實作

3.4堆的應用

3.4.1 堆排序

3.4.2 TOP-K問題

四、二叉樹鏈式結構的實作

4.1 前置說明

4.2二叉樹的遍歷

4.2.1 前序、中序以及后序遍歷

4.2.2 層序遍歷

4.2.3判斷二叉樹是否是完全二叉樹

4.3 節點個數以及高度等

4.5 二叉樹的創建和銷毀