主頁 >  其他 > 資料結構：如果寫代碼，就寫一棵樹

資料結構：如果寫代碼，就寫一棵樹

2021-09-20 11:38:07 其他

目錄

  • 前言
  • 1. 樹的概念及結構
    • 1. 樹的概念
    • 1.2 樹中的一些名稱
      • 1.2.2 節點
      • 1.2.3 子樹
      • 1.2.4 樹的高度或深度
      • 1.2.5 度
      • 1.2.6 樹中的親戚關系
    • 1.3 非樹
    • 1.4 樹的表示
      • 1.4.1 雙親表示法
      • 1.4.2 孩子表示法
      • 1.4.3 孩子兄弟表示法
    • 1.5 樹在實際中的應用
  • 2. 樹的計劃生育——二叉樹
    • 2.1 二叉樹的概念
    • 2.2 特殊的二叉樹
      • 2.2.1 滿二叉樹
      • 2.2.2 完全二叉樹
    • 2.3 二叉樹的性質
    • 2.4 二叉樹的存盤結構
      • 2.4.1 順序存盤
      • 2.4.2 鏈式存盤
  • 3. 二叉樹的順序結構及實作（堆）
    • 3.1 堆的概念及結構
      • 3.1.1 大根堆小根堆
      • 3.1.2 下標規律
    • 3.2 堆的實作
      • 3.2.1 堆向下調整演算法
        • 3.2.1.1 思路分析
        • 3.2.1.2 代碼實作
      • 3.2.2 向上調整排序演算法
        • 3.2.2.1 思路分析
        • 3.2.2.2 代碼實作
      • 3.2.3 堆的創建
      • 3.2.4 堆的排序
      • 3.2.5 堆的基本功能的實作（以大根堆為例）
        • 3.2.5.1 堆的插入
        • 3.2.5.2 堆的洗掉
        • 3.2.5.3 獲取堆頂元素、判空、求大小
        • 3.2.5.4 完整代碼及運行測驗
  • 4. 二叉樹鏈式結構及實作
    • 4.1 二叉樹鏈式結構的遍歷
      • 4.1.1 前序遍歷（先根遍歷）
      • 4.1.2 中序遍歷（中根遍歷）
      • 4.1.3 后序遍歷（后根遍歷）
      • 4.1.4 層序遍歷
      • 4.1.5 前中后序遍歷的代碼實作
    • 4.2 二叉樹節點計數方法
      • 4.2.1 遍歷計數
      • 4.2.2 拆解計數
    • 4.3 求葉子的個數
    • 4.4 求樹的深度
    • 4.5 求第k層節點個數
    • 4.6 查找值為x的節點
    • 4.7 銷毀二叉樹
    • 4.8 單值二叉樹判斷
    • 4.9 對稱二叉樹
    • 4.10 判斷兩棵樹是否相同
    • 4.11 判斷一棵樹為另一棵樹的子樹
    • 4.12 平衡二叉樹
    • 4.13 完整代碼
  • 后記

前言

hello，大家好，這期文章呢，來介紹一下關于樹的知識點，在介紹樹之前呢，首先先要了解什么是樹，如果你已經學會了離散數學，那么概念你自然已經懂的了，如果你學過離散但和博主一樣學了等于沒學，那你還需要和博主一起重新了解一下什么叫樹，
提到樹啊，我們總會想起那句著名的話“如果有來生，要做一棵樹，站成永恒”，其實實作做一棵樹的夢想也許不必等到來生，打開VS，給自己寫一棵吧，
圖片來源于網路

1. 樹的概念及結構

1. 樹的概念

樹是一種非線性的資料結構，它是由n（n>=0）個有限結點組成一個具有層次關系的集合，把它叫做樹是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的，有一個特殊的結點，稱為根結點，根節點沒有前驅結點除根節點外，其余結點被分成M(M>0)個互不相交的集合T1、T2、……、Tm，其中每一個集合Ti(1<= i<= m)又是一棵結構與樹類似的子樹，每棵子樹的根結點有且只有一個前驅，可以有0個或多個后繼因此，樹是遞回定義的，

在這里插入圖片描述

當然，并不是所有樹都如此繁茂，比如空樹，
在這里插入圖片描述

1.2 樹中的一些名稱

在這里插入圖片描述

1.2.2 節點

父節點和子節點：A、B、C、D、E、F、G……都是節點，其中，A為B、C、D、E、F、G的父節點（或雙親節點），B、C、D、E、F、G為A的子節點（或孩子節點），同理，D為H、I的父節點，H、I為D的子節點，I為L、M、N的父節點，L、M、N為i的子節點，
根節點和葉節點：沒有父節點的節點成為根節點，沒有子節點的節點稱為葉節點，A為根節點，H、G、L、M、N、O、P為葉節點，

1.2.3 子樹

以非根節點的其他節點為根節點構成的“小樹”為字樹，
在這里插入圖片描述
在這里插入圖片描述
這些均為子樹，

1.2.4 樹的高度或深度

節點的層次：從根開始定義起，根為第1層，根的子節點為第2層，以此類推；
樹的高度或深度：樹中節點的最大層次； 如上圖：樹的高度為4，

1.2.5 度

節點的度：一個節點含有的子樹的個數稱為該節點的度； 如上圖：A的為6，B的為0，D的為2，
樹的度：一棵樹中，最大的節點的度稱為樹的度； 如上圖：樹的度為6，
葉節點或終端節點：度為0的節點稱為葉節點，如B、C、F、H、G、L、M、N、O、P，
非終端節點或分支節點：度不為0的節點，如A、D、G、I、K，

1.2.6 樹中的親戚關系

雙親節點或父節點：若一個節點含有子節點，則這個節點稱為其子節點的父節點，
孩子節點或子節點：一個節點含有的子樹的根節點稱為該節點的子節點
兄弟節點：具有相同父節點的節點互稱為兄弟節點，如O和P，
堂兄弟節點：雙親在同一層的節點互為堂兄弟如H和G，
節點的祖先：從根到該節點所經分支上的所有節點
子孫：以某節點為根的子樹中任一節點都稱為該節點的子孫
森林：由m（m>0）棵互不相交的樹的集合稱為森林，

1.3 非樹

樹需要滿足以下條件：
1.子樹不相交
在這里插入圖片描述

2.除根節點外每一個節點都有且僅有一個父節點，
在這里插入圖片描述

3.一棵N個節點的樹有N-1條邊，
在這里插入圖片描述
根據以上條件可以看出，樹里面是不包含環的，有環則不為樹，

1.4 樹的表示

由于樹的結構復雜，表示起來也十分困難，在樹的多種表示方式中如：雙親表示法，孩子表示法、孩子兄弟表示法等等，最常用的孩子兄弟表示法，

1.4.1 雙親表示法

每個值存雙親的下標，這種表示方法雖然可能知道雙親，但遺憾的是不能知道孩子，如果要找孩子，就要遍歷整個結構，

#define MAX_TREE_SIZE 100
typedef struct TreeNode
{
	int  data;  //結點資料域
	int parent; //雙親位置
}TNode;
typedef struct
{              
	TNode nodes[MAX_TREE_SIZE];    //結點陣列
	int  r, n;                     //根節點的位置和結點數
};

1.4.2 孩子表示法

每一棵樹都是有根和子樹構成，子樹也是一樣的構成，但是樹并不確定有多少個孩子，
我們要使用孩子表示法，就要給每一個孩子對應一個指標，但并不是每一個節點都擁有相同數量的孩子，這就會造成很大的浪費，

struct TreeNode
{
	int data;
	struct TreeNode*child1;
	struct TreeNode*child2;
	struct TreeNode*child2;
	……
};

我們也可以采用動態增長的順序表來通過指標陣列來實作孩子指標，在C++中也可以通過vector來解決問題，但這種方法仍然沒有從本質上解決問題，還是有許多麻煩，

struct TreeNode
{
	int data;
	SeqList childarr;//指標陣列，順序表中存的是struct TreeNode*
};

所以這種方法是不太友好的，

1.4.3 孩子兄弟表示法

struct TreeNode
{
	int data;
	struct TreeNode*FirstChild;//指向第一個孩子的節點
	struct TreeNode*pNextBrother;//指向下一個兄弟的節點
};

這是一種很奇妙的表示方法，由孩子找孩子，解決了多孩子不好找問題，
在這里插入圖片描述
每一個節點都有兩個指標，一個指向兄弟，有兄弟則指向兄弟，沒有兄弟指向空，一個指標指向最左邊的子節點也就是第一個孩子，由第一個孩子去找到第二個孩子，以此類推，
這不由得使我想起了喬祖望，這個不靠譜的渣爹，他管過孩子是甩手掌柜，所有的孩子都是由老大一成來帶的，喬祖望就相當于父節點，而一成就是最左邊的子節點，而連接喬家的兄弟姐妹的感情的，就是指向兄弟節點的指標，
圖片來源于網路

1.5 樹在實際中的應用

目錄系統就是樹的一個典型應用，
在這里插入圖片描述

2. 樹的計劃生育——二叉樹

我們通過上面對樹的介紹，已經對樹有了初步了了解，我們也已經發現，一棵樹如果孩子太多，就會很麻煩，要是樹也能計劃生育一下就好了，只生一個好，樹樹皆好找，但是樹也是逐漸放開了二胎政策的，于是二叉樹就出現了，（放開了三胎政策后，會不會三叉樹成為主流呢？）

在這里插入圖片描述

2.1 二叉樹的概念

一棵二叉樹是結點的一個有限集合，該集合或者為空，或者是由一個根節點加上兩棵別稱為左子樹和右子樹
的二叉樹組成，
二叉樹的特點：

  1. 每個結點最多有兩棵子樹，即二叉樹不存在度大于2的結點，
  2. 二叉樹的子樹有左右之分，其子樹的次序不能顛倒，

也就是說，二叉樹里面，一個父節點可以沒有孩子，或者一個孩子，或者兩個孩子，孩子不能再多了，最多兩個，而且，大孩子和小孩子要區分開，順序不能顛倒，
在這里插入圖片描述
上圖為一個二叉樹，里面有獨生子女家庭，有二胎家庭，也有丁克家庭，但沒有三胎及以上的家庭，
注意，這樣的也是二叉樹哦，
在這里插入圖片描述

2.2 特殊的二叉樹

2.2.1 滿二叉樹

滿二叉樹：一個二叉樹，如果每一個層的結點數都達到最大值，則這個二叉樹就是滿二叉樹，也就是說，如果一個二叉樹的層數為K，且結點總數是(2^k) -1 ，則它就是滿二叉樹，

所謂的滿二叉樹就是，除了最小的一輩沒有孩子外，其他的都是二胎家庭，下一層的節點是上一節的二倍，
在這里插入圖片描述

2.2.2 完全二叉樹

完全二叉樹：完全二叉樹是效率很高的資料結構，完全二叉樹是由滿二叉樹而引出來的，對于深度為K的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為K的滿二叉樹中編號從1至n的結點一一對應時稱之為完全二叉樹， 要注意的是滿二叉樹是一種特殊的完全二叉樹，

完全二叉樹是一種允許非最小一輩丁克的二叉樹，也就是，最小一輩沒孩子，其他輩分的，要么生二胎，要么選擇丁克，完全二叉樹前n-1層都是滿的，最后一層可以不滿，但從左到右是連續的，不可以跳著不滿，簡而言之就是，老大不生老二不可以生，老大一胎老二不許二胎，
在這里插入圖片描述
這樣是不可以的：
在這里插入圖片描述

注意，滿二叉樹是一種特殊的完全二叉樹，
在這里插入圖片描述

2.3 二叉樹的性質

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

根據以上性質，我們來看幾道題：

  1. 某二叉樹共有 399 個結點，其中有 199 個度為 2 的結點，則該二叉樹中的葉子結點數為（ ）
    A 不存在這樣的二叉樹
    B 200
    C 198
    D 199
    根據度為0比度為二多一，所以要選200.而200+199正好得399，又可以證明是二叉樹，
    2.在具有 2n 個結點的完全二叉樹中，葉子結點個數為（ ）
    A n
    B n+1
    C n-1
    D n/2
    設度為0的葉子有m個，設度為1的節點有p個，度為2的有q個，則有m+p+q=2n,并且m=q+1.而且，對于完全二叉樹度為1的節點最多有一個，如果p=0.則2q+1=2n，n是正整數，所以不存在，所以p=1.則有2q+1+1=2n，所以m=n，答案為A，
    3.一棵完全二叉樹的節點數位為531個，那么這棵樹的高度為（ ）
    A 11
    B 10
    C 8
    D 12
    設深度為h，最后一層相對于滿二叉樹缺的節點為x，x的范圍為0到2^(h-1)-1.所以可以將選項帶入進行求證，最后選B，

2.4 二叉樹的存盤結構

2.4.1 順序存盤

順序結構存盤就是使用陣列來存盤，一般使用陣列只適合表示完全二叉樹，因為不是完全二叉樹會有空間的浪費，二叉樹順序存盤在物理上是一個陣列，在邏輯上是一顆二叉樹，

在這里插入圖片描述
順序存盤在存盤非完全二叉樹時會存在空間的浪費，

2.4.2 鏈式存盤

二叉樹的鏈式存盤結構是指，用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關系， 通常的方法是鏈表中每個結點由三個域組成，資料域和左右指標域，左右指標分別用來給出該結點左孩子和右孩子所在的鏈結點的存盤地址 ，鏈式結構又分為二叉鏈和三叉鏈

二叉鏈：只能找孩子
在這里插入圖片描述
三叉鏈：可以找孩子，也可以找父親
在這里插入圖片描述
二叉鏈表和三叉鏈表：
在這里插入圖片描述

// 二叉鏈
struct BinaryTreeNode
{
struct BinTreeNode* pLeft; // 指向當前節點左孩子
struct BinTreeNode* pRight; // 指向當前節點右孩子
BTDataType data; // 當前節點值域
}
// 三叉鏈
struct BinaryTreeNode
{
struct BinTreeNode* pParent; // 指向當前節點的雙親
struct BinTreeNode* pLeft; // 指向當前節點左孩子
struct BinTreeNode* pRight; // 指向當前節點右孩子
BTDataType data; // 當前節點值域
}；

鏈式存盤無論是完全二叉樹還是非完全二叉樹都不存在空間的浪費的情況，

3. 二叉樹的順序結構及實作（堆）

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

3.1 堆的概念及結構

如果有一個關鍵碼的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉樹的順序存盤方式存盤在一個一維陣列中，并滿足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，則稱為小堆(或大堆)，將根節點最大的堆叫做最大堆或大根堆，根節點最小的堆叫做最小堆或小根堆，
堆的性質：
堆中某個節點的值總是不大于或不小于其父節點的值；
堆總是一棵完全二叉樹，

3.1.1 大根堆小根堆

堆的物理結構是陣列，堆的邏輯結構是一個完全二叉樹，大根堆中所有的父親大于等于孩子，小根堆中所有的父親小于等于孩子，
大根堆：
在這里插入圖片描述
小根堆：
在這里插入圖片描述

3.1.2 下標規律

在這里插入圖片描述

3.2 堆的實作

3.2.1 堆向下調整演算法

3.2.1.1 思路分析

現在我們給出一個陣列，邏輯上看做一顆完全二叉樹，我們通過從根節點開始的向下調整演算法可以把它調整成一個小堆，向下調整演算法有一個前提：左右子樹必須是一個堆，才能調整，

在這里插入圖片描述
1.選出左右孩子中小的那一個
2.小的孩子和父親比
3.如果孩子比父親小，則與父親交換，并把原來孩子的位置當成父親繼續往下調整，
4.如果小的孩子比父親大，則完成調整，

在這里插入圖片描述

3.2.1.2 代碼實作

#include<stdio.h>

void Swap(int *p, int *q)
{
	int temp;
	temp = *p;
	*p = *q;
	*q = temp;
}

void AdjustDown(int *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])
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

int main()
{
	int a[] = { 28, 16, 20, 19, 29, 35, 66, 50, 26, 38 };
	int n = sizeof(a) / sizeof(a[0]);
	AdjustDown(a, n, 0);
	for (int i = 0; i < n; i++)
	{
		printf("%d  ", a[i]);
	}
	printf("\n");
	return 0;
}

在這里插入圖片描述

3.2.2 向上調整排序演算法

3.2.2.1 思路分析

向上排序演算法和向下排序演算法類似，如果我們插入的值比父親大，就交換，依次向上，
在這里插入圖片描述

3.2.2.2 代碼實作

void AdjustUp(int*a,int child)
{
	int parent = (child - 1) / 2;
	while (child>0)
	{
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

3.2.3 堆的創建

下面我們給出一個陣列，這個陣列邏輯上可以看做一顆完全二叉樹，但是還不是一個堆，現在我們通過演算法，把它構建成一個堆，根節點左右子樹不是堆，我們怎么調整呢？這里我們從倒數的第一個非葉子節點的子樹開始調整，一直調整到根節點的樹，就可以調整成堆，

當左右子樹不是小堆時，也就是說，我們需要多次呼叫向下調整演算法，
在這里插入圖片描述
從倒數第一個非葉子節點，從后往前排，按編號，一次作為子樹去向下調整，


#include<stdio.h>

void Swap(int *p, int *q)
{
	int temp;
	temp = *p;
	*p = *q;
	*q = temp;
}

void AdjustDown(int *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])
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

int main()
{
	int a[] = { 20, 16, 38, 29, 50, 35, 66, 19, 26, 28 };
	int n = sizeof(a) / sizeof(a[0]);
	for (int j = (n - 1 - 1) / 2; j >= 0; --j)
	{
		AdjustDown(a, n,j);
	}
	for (int i = 0; i < n; i++)
	{
		printf("%d  ", a[i]);
	}
	printf("\n");
	return 0;
}

在這里插入圖片描述

在這里插入圖片描述
注意，如果是大根堆，只需要將比較時的小于號全部換成大于號就可以，

3.2.4 堆的排序

首先，我們要思考這樣一個問題，當我們想要排升序時，應該建大根堆還是小根堆呢？降序時呢？答案是升序時建大堆，降序時建小堆，
我們以升序為例，升序為什么不能建小堆呢？建堆的時間復雜度為O(N)，如果我們建小堆，堆選出最小的數花了O(N)，緊接著剩下的N-1個數如何選出次小呢？剩下的數父子關系依舊全是亂的需要重新建堆，消耗很大，但如果我們建大堆，我們選出最大的后，將其和最后一個數字互換位置，緊接著選出次大的時，不把最后一個數字看出堆里面的，父子關系未變，向下調整就能選出次大的，
我們以升序排列為例觀察一下排序流程：
在這里插入圖片描述
在這里插入圖片描述
在這里插入圖片描述
從這個流程中我們就可以感受到，如果排升序建小堆的話，會混亂很多，

接下來的代碼展示升序建大堆：

#include<stdio.h>

void Swap(int *p, int *q)
{
	int temp;
	temp = *p;
	*p = *q;
	*q = temp;
}

void AdjustDown(int *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])
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapSort(int *a, int n)
{
	for (int j = (n - 1 - 1) / 2; j >= 0; --j)
	{
		AdjustDown(a, n, j);
	}
	int end = n - 1;
	while (end>0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}
int main()
{
	int a[] = { 20, 16, 38, 29, 50, 35, 66, 19, 26, 28 };
	int n = sizeof(a) / sizeof(a[0]);
	HeapSort(a, n);
	for (int i = 0; i < n; i++)
	{
		printf("%d  ", a[i]);
	}
	printf("\n");
	return 0;
}

接下來的代碼，我們展示了堆的降序排序建小堆：

#include<stdio.h>

void Swap(int *p, int *q)
{
	int temp;
	temp = *p;
	*p = *q;
	*q = temp;
}

void AdjustDown(int *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])
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapSort(int *a, int n)
{
	for (int j = (n - 1 - 1) / 2; j >= 0; --j)
	{
		AdjustDown(a, n, j);
	}
	int end = n - 1;
	while (end>0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}
int main()
{
	int a[] = { 20, 16, 38, 29, 50, 35, 66, 19, 26, 28 };
	int n = sizeof(a) / sizeof(a[0]);
	HeapSort(a, n);
	for (int i = 0; i < n; i++)
	{
		printf("%d  ", a[i]);
	}
	printf("\n");
	return 0;
}

注意：堆排序的時間復雜度是O(N*logN)，

3.2.5 堆的基本功能的實作（以大根堆為例）

3.2.5.1 堆的插入

堆的插入是先增加元素到尾上，然后通過向上調整的排序法，直到滿足堆，
我們要將88插入，流程如下：
在這里插入圖片描述
代碼如下：

void HeapPush(HP*php, HPDataType x)
{
	assert(php);
	if (php->size == php->capacity)
	{
		HPDataType*tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType)*php->capacity * 2);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		php->a = tmp;
		php->capacity *= 2;
	}
	php->a[php->size] = x;
	php->size++;
	AdjustUp(php->a, php->size-1);
}

3.2.5.2 堆的洗掉

堆的洗掉是洗掉堆頂的元素，實作思路是，先將堆頂元素與堆尾元素交換，將size-1，實作洗掉，同時通過向下調整演算法重新將堆調整好，
在這里插入圖片描述
代碼如下：

void HeapPop(HP*php)
{
	assert(php);
	assert(php->size > 0);
	Swap(&php->a[0], &php->a[php->size-1]);
	php->size--;
	AdjustDown(php->a, php->size-1, 0);
}

3.2.5.3 獲取堆頂元素、判空、求大小

這些實作起來很簡單，代碼如下：

HPDataType HeapTop(HP*php)
{
	assert(php);
	assert(php->size > 0);
	return php->a[0];
}
int HeapSize(HP*php)
{
	assert(php);
	return php->size;
}
bool HeapEmpty(HP*php)
{
	if (php->size == 0)
		return true;
	else
		return false;
}

3.2.5.4 完整代碼及運行測驗

Heqp.h檔案

#include<stdio.h>
#include<stdbool.h>
#include<malloc.h>
#include<assert.h>

typedef int HPDataType;

typedef struct Heap
{
	HPDataType *a;
	int size;
	int capacity;

}HP;

void AdjustDown(int *a, int n, int parent);
void AdjustUp(int *a, int child);
HP* HeapInit(HP*php, HPDataType*a, int n);
void HeapDestroy(HP *php);
void HeapPush(HP*php, HPDataType x);
void HeapPop(HP*php);
HPDataType HeapTop(HP*php);
int HeapSize(HP*php);
bool HeapEmpty(HP*php);
void HeapPrint(HP*php);

Heap.c檔案

#include"Heap.h"

void Swap(int *p, int *q)
{
	int temp;
	temp = *p;
	*p = *q;
	*q = temp;
}

void AdjustDown(int *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])
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void AdjustUp(int*a,int child)
{
	int parent = (child - 1) / 2;
	while (child>0)
	{
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

HP* HeapInit(HP*php, HPDataType*a, int n)
{
	assert(php);
	php->a = (HPDataType*)malloc(sizeof(HPDataType)*n);
	if (php->a == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	memcpy(php->a, a, sizeof(HPDataType)*n);
	php->size = n;
	php->capacity = n;

	//建大堆
	for (int j = (n - 1 - 1) / 2; j >= 0; --j)
	{
		AdjustDown(php->a,php->size, j);
	}
}
void HeapDestroy(HP *php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->size = php->capacity = 0;

}
void HeapPush(HP*php, HPDataType x)
{
	assert(php);
	if (php->size == php->capacity)
	{
		HPDataType*tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType)*php->capacity * 2);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		php->a = tmp;
		php->capacity *= 2;
	}
	php->a[php->size] = x;
	php->size++;
	AdjustUp(php->a, php->size-1);
}
void HeapPop(HP*php)
{
	assert(php);
	assert(php->size > 0);
	Swap(&php->a[0], &php->a[php->size-1]);
	php->size--;
	AdjustDown(php->a, php->size-1, 0);
}
HPDataType HeapTop(HP*php)
{
	assert(php);
	assert(php->size > 0);
	return php->a[0];
}
int HeapSize(HP*php)
{
	assert(php);
	return php->size;
}
bool HeapEmpty(HP*php)
{
	if (php->size == 0)
		return true;
	else
		return false;
}
void HeapPrint(HP*php)
{
	for (int i = 0; i <php-> size; i++)
	{
		printf("%d  ", php->a[i]);
	}
	printf("\n");
	printf("\n");
	int num = 0;
	int levelSize = 1;
	for (int i = 0; i < php->size; i++)
	{
		printf("%d  ", php->a[i]);
		++num;
		if (levelSize == num)
		{
			printf("\n");
			levelSize *= 2;
			num = 0;
		}
	}
	printf("\n");
	printf("\n");
	printf("\n");
}

test.c檔案

#include"Heap.h"


int main()
{
	int a[] = { 20, 16, 38, 29, 50, 35, 66, 19, 26, 28 };
	int n = sizeof(a) / sizeof(a[0]);
	HP hp;
	HeapInit(&hp, a, n);
	HeapPrint(&hp);
	HeapPush(&hp, 88);
	HeapPrint(&hp);
	HeapPop(&hp);
	HeapPrint(&hp);
	printf("%d\n", HeapTop(&hp));
	HeapDestroy(&hp);
	
	return 0;
}

運行測驗：
在這里插入圖片描述

4. 二叉樹鏈式結構及實作

4.1 二叉樹鏈式結構的遍歷

所謂遍歷(Traversal)是指沿著某條搜索路線，依次對樹中每個結點均做一次且僅做一次訪問，

二叉樹有四種遍歷順序：
1.前序遍歷（先根遍歷）
2.中序遍歷（中根遍歷）
3.后序遍歷（后根遍歷）
4.層序遍歷

4.1.1 前序遍歷（先根遍歷）

遍歷順序為：根——>左子樹——>右子樹
在這里插入圖片描述

4.1.2 中序遍歷（中根遍歷）

遍歷順序為：左子樹——>根——>右子樹
在這里插入圖片描述

4.1.3 后序遍歷（后根遍歷）

遍歷順序為：左子樹——>右子樹——>根
在這里插入圖片描述

4.1.4 層序遍歷

遍歷順序為：依次遍歷
在這里插入圖片描述

層序遍歷代碼：

void TreeLevelOrder(BTNode*root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		BTNode*front = QueueFront(&q);
		QueuePop(&q);
		printf("%c  ", front->data);
		if (front->left)
		{
			QueuePush(&q, front->left);
		}
		if (front->right)
		{
			QueuePush(&q, front->right);
		}
	}
}

代碼中涉及到的佇列的函式我們已經在之前的文章資料結構：佇列中實作，

4.1.5 前中后序遍歷的代碼實作

#include<stdio.h>
#include<malloc.h>


typedef char BTDataType;

typedef struct BinaryTreeNode
{
	struct BinaryTreeNode*left;
	struct BinaryTreeNode*right;
	BTDataType data;
}BTNode;

BTNode*CreateTreeNode(BTDataType x)
{
	BTNode*node = malloc(sizeof(BTNode));
	node->data = x;
	node->left = NULL;
	node->right = NULL;
	return node;
}
//前序
void PrevOrder(BTNode*root)
{
	if (root == NULL)
	{
		printf("NULL  ");
		return;
	}
	printf("%c  ", root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}
//中序
void InOrder(BTNode*root)
{
	if (root == NULL)
	{
		printf("NULL  ");
		return;
	}
	InOrder(root->left);
	printf("%c  ", root->data);
	InOrder(root->right);
}
//后序
void PostOrder(BTNode*root)
{
	if (root == NULL)
	{
		printf("NULL  ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%c  ", root->data);
}

int main()
{
	BTNode*A = CreateTreeNode('A');
	BTNode*B = CreateTreeNode('B');
	BTNode*C = CreateTreeNode('C');
	BTNode*D = CreateTreeNode('D');
	BTNode*E = CreateTreeNode('E');
	BTNode*F = CreateTreeNode('F');

	A->left = B;
	A->right = C;
	B->left = D;
	C->left = E;
	C->right = F;
	PrevOrder(A);
	printf("\n");
	InOrder(A);
	printf("\n");
	PostOrder(A);
	printf("\n");
	return 0;
}

在這里插入圖片描述

4.2 二叉樹節點計數方法

4.2.1 遍歷計數

實作思路：
在這里插入圖片描述

代碼：

#include<stdio.h>
#include<malloc.h>
typedef char BTDataType;

typedef struct BinaryTreeNode
{
	struct BinaryTreeNode*left;
	struct BinaryTreeNode*right;
	BTDataType data;
}BTNode;

BTNode*CreateTreeNode(BTDataType x)
{
	BTNode*node = malloc(sizeof(BTNode));
	node->data = x;
	node->left = NULL;
	node->right = NULL;
	return node;
}
//求節點個數:思路一  遍歷計數
void TreeSize1(BTNode*root,int *psize)
{
	if (root == NULL)
	{
		return;
	}
	++(*psize);
	TreeSize1(root->left,psize);
	TreeSize1(root->right,psize);
}
int main()
{
	BTNode*A = CreateTreeNode('A');
	BTNode*B = CreateTreeNode('B');
	BTNode*C = CreateTreeNode('C');
	BTNode*D = CreateTreeNode('D');
	BTNode*E = CreateTreeNode('E');
	BTNode*F = CreateTreeNode('F');

	A->left = B;
	A->right = C;
	B->left = D;
	C->left = E;
	C->right = F;
	int size = 0;
	TreeSize1(A,&size);
	printf("TreeSize1:%d\n", size);
	return 0;
}

在這里插入圖片描述

4.2.2 拆解計數

實作思路：
在這里插入圖片描述

代碼：

#include<stdio.h>
#include<malloc.h>

typedef char BTDataType;

typedef struct BinaryTreeNode
{
	struct BinaryTreeNode*left;
	struct BinaryTreeNode*right;
	BTDataType data;
}BTNode;

BTNode*CreateTreeNode(BTDataType x)
{
	BTNode*node = malloc(sizeof(BTNode));
	node->data = x;
	node->left = NULL;
	node->right = NULL;
	return node;
}
//求節點個數:思路二  拆解計數
int TreeSize2(BTNode*root)
{
	return root == NULL ?0: TreeSize2(root->left) + TreeSize2(root->right) + 1;
}
int main()
{
	BTNode*A = CreateTreeNode('A');
	BTNode*B = CreateTreeNode('B');
	BTNode*C = CreateTreeNode('C');
	BTNode*D = CreateTreeNode('D');
	BTNode*E = CreateTreeNode('E');
	BTNode*F = CreateTreeNode('F');

	A->left = B;
	A->right = C;
	B->left = D;
	C->left = E;
	C->right = F;
	printf("TreeSize1:%d\n", size);
	return 0;
}

在這里插入圖片描述

4.3 求葉子的個數

如果是NULL葉子樹為0，如果是指向NULL則代表為葉子，根據這個原理可以得出求葉子樹的函式，

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

4.4 求樹的深度

樹的深度的求法思想是一層層求下去，遇到NULL是0，遇到子樹的根繼續下去，同時深度+1，繼續下去，左右樹同時求深度，取大值為整棵樹的最大深度
在這里插入圖片描述

int TreeMaxDepth(BTNode*root)
{
	if (root == NULL)
	{
		return 0;
	}
	int LeftDepth = TreeMaxDepth(root->left);
	int Rightdepth = TreeMaxDepth(root->right);
	return LeftDepth > Rightdepth ? LeftDepth + 1 : Rightdepth + 1;
}

4.5 求第k層節點個數

這個實作的主要思想是依照上一層的左右指向的節點求本層個數，以此類推，
在這里插入圖片描述

// 二叉樹第k層節點個數
int TreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return TreeLevelKSize(root->left, k - 1) + TreeLevelKSize(root->right, k - 1);
}

4.6 查找值為x的節點

如果root=NULL，return NULL，如果root不是我們要找的，先去左樹找，再去右樹找，如果最后都沒找到，則當前樹無此值，回傳空，
在這里插入圖片描述

// 二叉樹查找值為x的節點
BTNode* TreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	BTNode*lret = TreeFind(root->left, x);
	if (lret)
	{
		return lret;
	}
	BTNode*rret = TreeFind(root->right, x);
	if (rret)
	{
		return rret;
	}
	return NULL;
}

4.7 銷毀二叉樹

void TreeDestroy(BTNode*root)
{
	if (root == NULL)
	{
		return;
	}
	TreeDestroy(root->left);
	TreeDestroy(root->right);
	free(root);
}

這種方法注意銷毀之后置空二叉樹的根，

TreeDestroy(A);
	A = NULL;

如果不想再呼叫之后置空，我們可以采用二級指標的方法，在函式里面置空，

void TreeDestroy(BTNode**pproot)
{
	if (*pproot == NULL)
	{
		return;
	}
	TreeDestroy(&(*pproot)->left);
	TreeDestroy(&(*pproot)->right);
	free(*pproot);
	*pproot = NULL;
}

4.8 單值二叉樹判斷

如果二叉樹每個節點都具有相同的值，那么該二叉樹就是單值二叉樹，只有給定的樹是單值二叉樹時，才回傳 true；否則回傳 false，

//判斷單值樹
bool TreeSingle(BTNode*root)
{
	if (root == NULL)
	{
		return true;
	}
	if (root->left&&root->left->data != root->data)
	{
		return false;
	}
	if (root->right&&root->right->data != root->data)
	{
		return false;
	}
	return TreeSingle(root->left) && TreeSingle(root->right);
}

判斷單值樹的思路就是不斷對比，只要出現不相同的就為false，還是采用了遞回呼叫，

4.9 對稱二叉樹

給定一個二叉樹，檢查它是否是鏡像對稱的，
在這里插入圖片描述

在這里插入圖片描述

bool _TreeSymmertic(BTNode*left, BTNode*right)
{
	if (left == NULL&&right == NULL)
	{
		return true;
	}
	if (left == NULL || right == NULL)
	{
		return false;
	}
	if (left->data != right->data)
	{
		return false;
	}
	return _TreeSymmertic(left->right, right->left);
}

bool TreeSymmertic(BTNode*root)
{
	if (root == NULL)
	{
		return true;
	}
	return _TreeSymmertic(root->left, root->right);
}

4.10 判斷兩棵樹是否相同

如果兩個二叉樹都為空，則兩個二叉樹相同，如果兩個二叉樹中有且只有一個為空，則兩個二叉樹一定不相同，如果兩個二叉樹都不為空，那么首先判斷它們的根節點的值是否相同，若不相同則兩個二叉樹一定不同，若相同，再分別判斷兩個二叉樹的左子樹是否相同以及右子樹是否相同，這是一個遞回的程序，因此可以使用深度優先搜索，遞回地判斷兩個二叉樹是否相同，

//判斷兩棵樹是否相同
bool TreeSame(BTNode*root1,BTNode*root2)
{
	if (root1 == NULL && root2== NULL) 
	{
		return true;
	}
	else if (root1 == NULL || root2== NULL)
	{
		return false;
	}
	else if (root1->data != root2->data) 
	{
		return false;
	}
	else 
	{
		return TreeSame(root1->left, root2->left) &&TreeSame(root1->right, root2->right);
	}
}

4.11 判斷一棵樹為另一棵樹的子樹

這道題可以將要驗證的樹和另一棵樹的每一個子樹比較，若能找到相同的，則是，否則為否，這里我們巧用了之前判斷兩棵樹是否相等的函式，

//判斷一棵樹為另一棵樹的子樹
bool TreeSub(BTNode*root, BTNode*subroot)
{
	if (root == NULL)
	{
		return false;
	}
	if (TreeSame(root, subroot))
	{
		return true;
	}
	return TreeSub(root->left,subroot) || TreeSub(root->right,subroot);
}

4.12 平衡二叉樹

在這里插入圖片描述

//判斷平衡二叉樹
bool _TreeBalance(BTNode*root,int *ph)
{
	if (root == NULL)
	{
		*ph = 0;
		return true;
	}
	int LeftHeight = 0;
	if (_TreeBalance(root->left, &LeftHeight) == false)
		return false;
	int RightHeight = 0;
	if (_TreeBalance(root->right, &RightHeight) == false)
		return false;
	*ph = fmax(LeftHeight, RightHeight) + 1;
	return abs(LeftHeight - RightHeight) < 2;
}

bool TreeBalance(BTNode*root)
{
	if (root == NULL)
	{
		return true;
	}
	int height = 0;
	return _TreeBalance(root, &height);
}

4.13 完整代碼

#include<stdio.h>
#include<malloc.h>
#include<stdbool.h>

typedef char BTDataType;

typedef struct BinaryTreeNode
{
	struct BinaryTreeNode*left;
	struct BinaryTreeNode*right;
	BTDataType data;
}BTNode;

BTNode*CreateTreeNode(BTDataType x)
{
	BTNode*node = malloc(sizeof(BTNode));
	node->data = x;
	node->left = NULL;
	node->right = NULL;
	return node;
}
//前序
void PrevOrder(BTNode*root)
{
	if (root == NULL)
	{
		printf("NULL  ");
		return;
	}
	printf("%c  ", root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}
//中序
void InOrder(BTNode*root)
{
	if (root == NULL)
	{
		printf("NULL  ");
		return;
	}
	InOrder(root->left);
	printf("%c  ", root->data);
	InOrder(root->right);
}
//后序
void PostOrder(BTNode*root)
{
	if (root == NULL)
	{
		printf("NULL  ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%c  ", root->data);
}

層序遍歷，使用時需要引入佇列的頭檔案
//void TreeLevelOrder(BTNode*root)
//{
//	Queue q;
//	QueueInit(&q);
//	if (root)
//	{
//		QueuePush(&q, root);
//	}
//	while (!QueueEmpty(&q))
//	{
//		BTNode*front = QueueFront(&q);
//		QueuePop(&q);
//		printf("%c  ", front->data);
//		if (front->left)
//		{
//			QueuePush(&q, front->left);
//		}
//		if (front->right)
//		{
//			QueuePush(&q, front->right);
//		}
//	}
//}
//求節點個數:思路一  遍歷計數
void TreeSize1(BTNode*root,int *psize)
{
	if (root == NULL)
	{
		return;
	}
	++(*psize);
	TreeSize1(root->left,psize);
	TreeSize1(root->right,psize);
}
//求節點個數:思路二  拆解計數
int TreeSize2(BTNode*root)
{
	return root == NULL ?0: TreeSize2(root->left) + TreeSize2(root->right) + 1;
}
// 二叉樹葉子節點個數
int TreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL&&root->right == NULL)
	{
		return 1;
	}
	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}
// 二叉樹第k層節點個數
int TreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return TreeLevelKSize(root->left, k - 1) + TreeLevelKSize(root->right, k - 1);
}
// 二叉樹查找值為x的節點
BTNode* TreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	BTNode*lret = TreeFind(root->left, x);
	if (lret)
	{
		return lret;
	}
	BTNode*rret = TreeFind(root->right, x);
	if (rret)
	{
		return rret;
	}
	return NULL;
}
int TreeMaxDepth(BTNode*root)
{
	if (root == NULL)
	{
		return 0;
	}
	int LeftDepth = TreeMaxDepth(root->left);
	int Rightdepth = TreeMaxDepth(root->right);
	return LeftDepth > Rightdepth ? LeftDepth + 1 : Rightdepth + 1;
}

//void TreeDestroy(BTNode*root)
//{
//	if (root == NULL)
//	{
//		return;
//	}
//	TreeDestroy(root->left);
//	TreeDestroy(root->right);
//	free(root);
//}

void TreeDestroy(BTNode**pproot)
{
	if (*pproot == NULL)
	{
		return;
	}
	TreeDestroy(&(*pproot)->left);
	TreeDestroy(&(*pproot)->right);
	free(*pproot);
	*pproot = NULL;
}
//判斷單值樹
bool TreeSingle(BTNode*root)
{
	if (root == NULL)
	{
		return true;
	}
	if (root->left&&root->left->data != root->data)
	{
		return false;
	}
	if (root->right&&root->right->data != root->data)
	{
		return false;
	}
	return TreeSingle(root->left) && TreeSingle(root->right);
}
//判斷是否為對稱樹
bool _TreeSymmertic(BTNode*left, BTNode*right)
{
	if (left == NULL&&right == NULL)
	{
		return true;
	}
	if (left == NULL || right == NULL)
	{
		return false;
	}
	if (left->data != right->data)
	{
		return false;
	}
	return _TreeSymmertic(left->right, right->left);
}

bool TreeSymmertic(BTNode*root)
{
	if (root == NULL)
	{
		return true;
	}
	return _TreeSymmertic(root->left, root->right);
}
//判斷兩棵樹是否相同
bool TreeSame(BTNode*root1,BTNode*root2)
{
	if (root1 == NULL && root2== NULL) 
	{
		return true;
	}
	else if (root1 == NULL || root2== NULL)
	{
		return false;
	}
	else if (root1->data != root2->data) 
	{
		return false;
	}
	else 
	{
		return TreeSame(root1->left, root2->left) &&TreeSame(root1->right, root2->right);
	}
}

//判斷一棵樹為另一棵樹的子樹
bool TreeSub(BTNode*root, BTNode*subroot)
{
	if (root == NULL)
	{
		return false;
	}
	if (TreeSame(root, subroot))
	{
		return true;
	}
	return TreeSub(root->left,subroot) || TreeSub(root->right,subroot);
}
//判斷平衡二叉樹
bool _TreeBalance(BTNode*root,int *ph)
{
	if (root == NULL)
	{
		*ph = 0;
		return true;
	}
	int LeftHeight = 0;
	if (_TreeBalance(root->left, &LeftHeight) == false)
		return false;
	int RightHeight = 0;
	if (_TreeBalance(root->right, &RightHeight) == false)
		return false;
	*ph = fmax(LeftHeight, RightHeight) + 1;
	return abs(LeftHeight - RightHeight) < 2;
}

bool TreeBalance(BTNode*root)
{
	if (root == NULL)
	{
		return true;
	}
	int height = 0;
	return _TreeBalance(root, &height);
}
int main()
{
	BTNode*A = CreateTreeNode('A');
	BTNode*B = CreateTreeNode('B');
	BTNode*C = CreateTreeNode('C');
	BTNode*D = CreateTreeNode('D');
	BTNode*E = CreateTreeNode('E');
	BTNode*F = CreateTreeNode('F');

	A->left = B;
	A->right = C;
	B->left = D;
	C->left = E;
	C->right = F;
	PrevOrder(A);
	printf("\n");
	InOrder(A);
	printf("\n");
	PostOrder(A);
	printf("\n");
	int size = 0;
	TreeSize1(A,&size);
	printf("TreeSize1:%d\n", size);
	printf("TreeSize2:%d\n", TreeSize2(A));
	printf("TreeLeafSize:%d\n", TreeLeafSize(A));
	printf("TreeMaxDepth:%d\n", TreeMaxDepth(A));
	printf("TreeLevelKSize:%d\n", TreeLevelKSize(A,2));
	BTNode*ret=TreeFind(A, 'E');
	printf("TreeFind:%c\n", ret->data);
	printf("TreeSingle:%d\n", TreeSingle(A));
	printf("TreeSymmertic:%d\n", TreeSymmertic(A));
	printf("TreeSame:%d\n", TreeSame(A,A));
	printf("TreeSub:%d\n", TreeSub(A, B));
	printf("TreeBalance:%d\n", TreeBalance(A));
	TreeDestroy(A);
	//A = NULL;
	return 0;
}

后記

好的，這期誠意滿滿的博客就分享到這里了，在這期文章中，我們介紹了樹的基本知識，希望對大家有所幫助，
回到我們文章開頭的那張圖片，這張圖片是我在網上看到的，是一位攝影師的作品，圖片中的人是要搬遷的村民，他走時，背走了家里的一棵桃樹，故鄉不再，他帶走了故鄉的一棵樹，這倒是與三毛的那句如果有來生要做一棵樹站成永恒有了奇妙的關聯，當故鄉已經難以留下，就讓樹成為永恒吧，
在這里插入圖片描述

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

標籤：其他

上一篇：KMP演算法詳解——多圖，多例子（c語言）

下一篇：物聯網綜合應用 第二次作業

標籤雲
其他(157675) Python(38076) JavaScript(25376) Java(17977) C(15215) 區塊鏈(8255) C＃(7972) AI(7469) 爪哇(7425) MySQL(7132) html(6777) 基礎類(6313) sql(6102) 熊猫(6058) PHP(5869) 数组(5741) R(5409) Linux(5327) 反应(5209) 腳本語言(PerlPython)(5129) 非技術區(4971) Android(4554) 数据框(4311) css(4259) 节点.js(4032) C語言(3288) json(3245) 列表(3129) 扑(3119) C++語言(3117) 安卓(2998) 打字稿(2995) VBA(2789) Java相關(2746) 疑難問題(2699) 细绳(2522) 單片機工控(2479) iOS(2429) ASP.NET(2402) MongoDB(2323) 麻木的(2285) 正则表达式(2254) 字典(2211) 循环(2198) 迅速(2185) 擅长(2169) 镖(2155) 功能(1967) .NET技术(1958) Web開發(1951) python-3.x(1918) HtmlCss(1915) 弹簧靴(1913) C++(1909) xml(1889) PostgreSQL(1872) .NETCore(1853) 谷歌表格(1846) Unity3D(1843) for循环(1842)

熱門瀏覽
  • 網閘典型架構簡述

    網閘架構一般分為兩種：三主機的三系統架構網閘和雙主機的2+1架構網閘。 三主機架構分別為內端機、外端機和仲裁機。三機無論從軟體和硬體上均各自獨立。首先從硬體上來看，三機都用各自獨立的主板、記憶體及存盤設備。從軟體上來看，三機有各自獨立的作業系統。這樣能達到完全的三機獨立。對于“2+1”系統，“2”分為 ......

    uj5u.com 2020-09-10 02:00:44 more
  • 如何從xshell上傳檔案到centos linux虛擬機里

    如何從xshell上傳檔案到centos linux虛擬機里及：虛擬機CentOs下執行 yum -y install lrzsz命令，出現錯誤：鏡像無法找到軟體包 前言 一、安裝lrzsz步驟 二、上傳檔案 三、遇到的問題及解決方案 總結 前言 提示：其實很簡單，往虛擬機上安裝一個上傳檔案的工具 ......

    uj5u.com 2020-09-10 02:00:47 more
  • 一、SQLMAP入門

    一、SQLMAP入門 1、判斷是否存在注入 sqlmap.py -u 網址/id=1 id=1不可缺少。當注入點后面的引數大于兩個時。需要加雙引號， sqlmap.py -u "網址/id=1&uid=1" 2、判斷文本中的請求是否存在注入 從文本中加載http請求，SQLMAP可以從一個文本檔案中 ......

    uj5u.com 2020-09-10 02:00:50 more
  • Metasploit 簡單使用教程

    metasploit 簡單使用教程 浩先生， 2020-08-28 16:18:25 分類專欄： kail 網路安全 linux 文章標簽： linux資訊安全 編輯 著作權 metasploit 使用教程 前言 一、Metasploit是什么？ 二、準備作業 三、具體步驟 前言 Msfconsole ......

    uj5u.com 2020-09-10 02:00:53 more
  • 游戲逆向之驅動層與用戶層通訊

    驅動層代碼： #pragma once #include <ntifs.h> #define add_code CTL_CODE(FILE_DEVICE_UNKNOWN,0x800,METHOD_BUFFERED,FILE_ANY_ACCESS) /* 更多游戲逆向視頻www.yxfzedu.com ......

    uj5u.com 2020-09-10 02:00:56 more
  • 北斗電力時鐘（北斗授時服務器）讓網路資料更精準

    北斗電力時鐘（北斗授時服務器）讓網路資料更精準 北斗電力時鐘（北斗授時服務器）讓網路資料更精準 京準電子科技官微——ahjzsz 近幾年，資訊技術的得了快速發展，互聯網在逐漸普及，其在人們生活和生產中都得到了廣泛應用，并且取得了不錯的應用效果。計算機網路資訊在電力系統中的應用，一方面使電力系統的運行 ......

    uj5u.com 2020-09-10 02:01:03 more
  • 【CTF】CTFHub 技能樹 彩蛋 writeup

    ?碎碎念 CTFHub：https://www.ctfhub.com/ 筆者入門CTF時時剛開始刷的是bugku的舊平臺，后來才有了CTFHub。 感覺不論是網頁UI設計，還是題目質量，賽事跟蹤，工具軟體都做得很不錯。 而且因為獨到的金幣制度的確讓人有一種想去刷題賺金幣的感覺。 個人還是非常喜歡這個 ......

    uj5u.com 2020-09-10 02:04:05 more
  • 02windows基礎操作

    我學到了一下幾點 Windows系統目錄結構與滲透的作用 常見Windows的服務詳解 Windows埠詳解 常用的Windows注冊表詳解 hacker DOS命令詳解（net user / type /md /rd/ dir /cd /net use copy、批處理 等） 利用dos命令制作 ......

    uj5u.com 2020-09-10 02:04:18 more
  • 03.Linux基礎操作

    我學到了以下幾點 01Linux系統介紹02系統安裝，密碼啊破解03Linux常用命令04LAMP 01LINUX windows： win03 8 12 16 19 配置不繁瑣 Linux：redhat,centos(紅帽社區版)，Ubuntu server,suse unix:金融機構，證券，銀 ......

    uj5u.com 2020-09-10 02:04:30 more
  • 05HTML

    01HTML介紹 02頭部標簽講解03基礎標簽講解04表單標簽講解 HTML前段語言 js1.了解代碼2.根據代碼 懂得挖掘漏洞 （POST注入/XSS漏洞上傳）3.黑帽seo 白帽seo 客戶網站被黑帽植入劫持代碼如何處理4.熟悉html表單 <html><head><title>TDK標題，描述 ......

    uj5u.com 2020-09-10 02:04:36 more
最新发布
  • 2023年最新微信小程式抓包教程

    01 開門見山 隔一個月發一篇文章，不過分。 首先回顧一下《微信系結手機號資料庫被脫庫事件》，我也是第一時間得知了這個訊息，然后跟蹤了整件事情的經過。下面是這起事件的相關截圖以及近日流出的一萬條資料樣本： 個人認為這件事也沒什么，還不如關注一下之前45億快遞資料查詢渠道疑似在近日復活的訊息。 訊息是 ......

    uj5u.com 2023-04-20 08:48:24 more
  • web3 產品介紹：metamask 錢包 使用最多的瀏覽器插件錢包

    Metamask錢包是一種基于區塊鏈技術的數字貨幣錢包，它允許用戶在安全、便捷的環境下管理自己的加密資產。Metamask錢包是以太坊生態系統中最流行的錢包之一，它具有易于使用、安全性高和功能強大等優點。 本文將詳細介紹Metamask錢包的功能和使用方法。 一、 Metamask錢包的功能 數字資 ......

    uj5u.com 2023-04-20 08:47:46 more
  • vulnhub_Earth

    前言 靶機地址->>>vulnhub_Earth 攻擊機ip：192.168.20.121 靶機ip：192.168.20.122 參考文章 https://www.cnblogs.com/Jing-X/archive/2022/04/03/16097695.html https://www.cnb ......

    uj5u.com 2023-04-20 07:46:20 more
  • 從4k到42k，軟體測驗工程師的漲薪史，給我看哭了

    清明節一過，盲猜大家已經無心上班，在數著日子準備過五一，但一想到銀行卡里的余額……瞬間心情就不美麗了。最近，2023年高校畢業生就業調查顯示，本科畢業月平均起薪為5825元。調查一出，便有很多同學表示自己又被平均了。看著這一資料，不免讓人想到前不久中國青年報的一項調查：近六成大學生認為畢業10年內會 ......

    uj5u.com 2023-04-20 07:44:00 more
  • 最新版本 Stable Diffusion 開源 AI 繪畫工具之中文自動提詞篇

    🎈 標簽生成器 由于輸入正向提示詞 prompt 和反向提示詞 negative prompt 都是使用英文，所以對學習母語的我們非常不友好 使用網址：https://tinygeeker.github.io/p/ai-prompt-generator 這個網址是為了讓大家在使用 AI 繪畫的時候 ......

    uj5u.com 2023-04-20 07:43:36 more
  • 漫談前端自動化測驗演進之路及測驗工具分析

    隨著前端技術的不斷發展和應用程式的日益復雜，前端自動化測驗也在不斷演進。隨著 Web 應用程式變得越來越復雜，自動化測驗的需求也越來越高。如今，自動化測驗已經成為 Web 應用程式開發程序中不可或缺的一部分，它們可以幫助開發人員更快地發現和修復錯誤，提高應用程式的性能和可靠性。 ......

    uj5u.com 2023-04-20 07:43:16 more
  • CANN開發實踐：4個DVPP記憶體問題的典型案例解讀

    摘要：由于DVPP媒體資料處理功能對存放輸入、輸出資料的記憶體有更高的要求（例如，記憶體首地址128位元組對齊），因此需呼叫專用的記憶體申請介面，那么本期就分享幾個關于DVPP記憶體問題的典型案例，并給出原因分析及解決方法。 本文分享自華為云社區《FAQ_DVPP記憶體問題案例》，作者：昇騰CANN。 DVPP ......

    uj5u.com 2023-04-20 07:43:03 more
  • msf學習

    msf學習 以kali自帶的msf為例 一、msf核心模塊與功能 msf模塊都放在/usr/share/metasploit-framework/modules目錄下 1、auxiliary 輔助模塊，輔助滲透（埠掃描、登錄密碼爆破、漏洞驗證等） 2、encoders 編碼器模塊，主要包含各種編碼 ......

    uj5u.com 2023-04-20 07:42:59 more
  • Halcon軟體安裝與界面簡介

    1. 下載Halcon17版本到到本地 2. 雙擊安裝包后 3. 步驟如下 1.2 Halcon軟體安裝 界面分為四大塊 1. Halcon的五個助手 1) 影像采集助手：與相機連接，設定相機引數，采集影像 2) 標定助手：九點標定或是其它的標定，生成標定檔案及內參外參，可以將像素單位轉換為長度單位 ......

    uj5u.com 2023-04-20 07:42:17 more
  • 在MacOS下使用Unity3D開發游戲

    第一次發博客，先發一下我的游戲開發環境吧。 去年2月份買了一臺MacBookPro2021 M1pro(以下簡稱mbp)，這一年來一直在用mbp開發游戲。我大致分享一下我的開發工具以及使用體驗。 1、Unity 官網鏈接： https://unity.cn/releases 我一般使用的Apple ......

    uj5u.com 2023-04-20 07:40:19 more

Copyright © 2010-2020 有解無憂