數據結構 —— 二叉樹

1.樹的概念及結構

1.1樹的概念

樹是一種非線性的數據結構，它有著多分支，層次性的特點。

由于其形態類似于自然界中倒過來的數，所以我們將這種數據結構稱為“樹形結構”

注意：樹形結構中，子樹之間不能有交集，否它就不是樹形結構

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; // 結點中的數據域
};

這種數的設計方法，我們可以通過左孩子指針找到 A節點的第一個孩子(B)，在通過孩子的右兄弟指針把 A節點的所有孩子都找到

1.4 樹在實際中的運用

樹在實際中的運用：電腦中的數目錄

2.二叉樹的概念及結構?

2.1二叉樹的概念?

在實際運用中，二叉樹要比樹更加實用

二叉樹其實就是特殊的一種樹，它的每個節點最多有兩個子節點，通常被稱為左子節點和右子節點

?二叉樹不存在度大于2的結點
?二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹

2.2現實中的二叉樹

?2.3特殊的二叉樹

?滿二叉樹：二叉樹的每一層都是滿的（特殊的完全二叉樹）
完全二叉樹：二叉樹的最后一層不一定是滿的，但是它是連續的

像下面這個二叉樹，最后一層并不連續，因此它并非是完全二叉樹：

2.4二叉樹的性質

2.5二叉樹的存儲結構

二叉樹一般可以使用兩種結構存儲，一種順序結構，一種鏈式結構

1. 順序存儲

順序結構存儲就是使用 數組來存儲 ，一般使用數組 只適合表示完全二叉樹 ，因為不是完全二叉樹會有空間的浪費。而現實中使用中只有堆才會使用數組來存儲

二叉樹順序存儲在物理上是一個數組，在邏輯上是一顆二叉樹

2. 鏈式存儲

二叉樹的鏈式存儲結構是指，用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關系。

通常的方法是：鏈表中每個結點由三個域組成，數據域和左右指針域，左右指針分別用來給出該結點左孩子和右孩子所在的鏈結點的存儲地址。鏈式結構又分為二叉鏈和三叉鏈，目前我們使用二叉鏈的新式學習

二叉鏈式實現的二叉樹：

3.二叉樹的順序存儲結構?

順序存儲結構只推薦完全叉樹來進行存儲，一般的二叉樹容使用順序結構進行存儲，容易造成空間的大量浪費，現實中我們通常把堆(一種二叉樹)使用順序結構的數組來存儲，需要注意的是這里的堆和操作系統虛擬進程地址空間中的堆是兩回事，一個是數據結構，一個是操作系統中管理內存的一塊區域分段

堆在這篇文章中有所介紹 ———— 數據結構 - 堆

4.二叉樹的鏈式結構的實現

在進行二叉樹鏈式結構的實現時，我們首先回顧二叉樹是：

1. 空樹

2. 非空：根結點，根結點的左子樹、根結點的右子樹組成的

每一顆二叉樹都可以看做是遞歸形成的因為：

每一顆二叉樹都可以拆分成：根節點左子樹右子樹

它的左子樹可以被拆分成?：根節點左子樹右子樹

它的右子樹右也可以被拆分成?：根節點左子樹右子樹

依次類推直到變成一顆空樹，不能被拆分，所以才會說二叉樹可以看做是遞歸形成，二叉樹可以被拆分成一個一個的小問題（即一個一個的子樹根節點），直到變成空樹不能再被拆分，因此后序基本操作中基本都是按照遞歸概念實現的

4.1二叉樹的前置聲明

typedef int BTDataType;typedef struct BinaryTreeNode    //二叉樹的單個節點
{BTDataType _data;struct BinaryTreeNode* _left;   //左孩子struct BinaryTreeNode* _right;  //右孩子
}BTNode;

4.2二叉樹的遍歷

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

二叉樹的遍歷是指按照某種規則訪問樹中的所有節點，并且每個節點只被訪問一次。訪問結點所做的操作依賴于具體的應用問題。遍歷是二叉樹上最重要的運算之一，也是二叉樹上進行其它運算的基礎。

按照規則，二叉樹的遍歷有：前序/中序/后序的遞歸結構遍歷：?

1. 前序遍歷 (Preorder Traversal )—— 訪問順序：根節點 —>左子樹 —>右子樹

2. 中序遍歷(Inorder Traversal)——訪問順序：左子樹 —>根節點 —>右子樹

3. 后序遍歷(Postorder Traversal)——訪問順序：左子樹 —>右子樹—>根節

前序遍歷遞歸圖解 ：

前序遍歷結果： 1 2 3 4 5 6

中序遍歷結果： 3 2 1 5 4 6

后序遍歷結果： 3 2 5 6 4 1

前中后序遍歷的方式大抵相同，這里不做過多贅述

代碼實現：

// 二叉樹前序遍歷 
void BinaryTreePrevOrder(BTNode* root) {if (root == NULL)  //當訪問的數為NULL樹時停止訪問{printf("N ");return;}printf("%d ",root->_data);//先便利根節點,整形的數據類型BinaryTreePrevOrder(root->_left);//左子樹BinaryTreePrevOrder(root->_right);//右子樹}
// 二叉樹中序遍歷
void BinaryTreeInOrder(BTNode* root) {if (root == NULL){printf("N ");return;}BinaryTreeInOrder(root->_left);//左子樹printf("%d ", root->_data);//根節點BinaryTreeInOrder(root->_right);//右子樹
}// 二叉樹后序遍歷
void BinaryTreePostOrder(BTNode* root) {if (root == NULL){printf("N ");return;}BinaryTreePostOrder(root->_left);//左子樹BinaryTreePostOrder(root->_right);//右子樹printf("%d ", root->_data);//根節點
}

4.2.2層序遍歷?

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

?代碼實現：

二叉樹的層序遍歷并不是通過遞歸來完成的，而是通過 —— 數據結構中的隊列來實現的

遍歷的原理是從根節點開始，首先訪問根節點，然后將根節點的左右子節點依次入隊。接下來，從隊列中取出一個節點（隊首節點），訪問該節點，再將其未被訪問的左右子節點入隊。重復此過程，直到隊列為空，即所有節點都被訪問過。

動圖理解：

// 層序遍歷
void BinaryTreeLevelOrder(BTNode* root) {//創建隊列Queue qu;QueueInit(&qu);QueuePush(&qu, root);//開始拖家帶口，當隊列為NULL時，說明已經遍歷完成,循環結束while (!QueueEmpty(&qu)){//先訪問隊頭的元素BTNode* bt = QueueFront(&qu);//獲取隊頭元素printf("%d ", bt->_data);//將樹的左右孩子都帶入隊列中，NULL孩子除外if (bt->_left)QueuePush(&qu, bt->_left);if (bt->_right)QueuePush(&qu, bt->_right);//隊頭數據處隊列QueuePop(&qu);}//銷毀隊列QueueDestroy(&qu);}

5.二叉樹總代碼

隊列的相關功能：

Queue.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef struct BinaryTreeNode* QDataType;   //隊列中的元素是樹的節點
// 鏈式結構：表示隊列 
typedef struct QListNode
{struct QListNode* _next;QDataType _data;
}QNode;// 隊列的結構 
typedef struct Queue
{QNode* _front;QNode* _rear;int size;
}Queue;// 初始化隊列 
void QueueInit(Queue* q);
// 隊尾入隊列 
void QueuePush(Queue* q, QDataType data);
// 隊頭出隊列 
void QueuePop(Queue* q);
// 獲取隊列頭部元素 
QDataType QueueFront(Queue* q);
// 獲取隊列隊尾元素 
QDataType QueueBack(Queue* q);
// 獲取隊列中有效元素個數 
int QueueSize(Queue* q);
// 檢測隊列是否為空，如果為空返回非零結果，如果非空返回0 
int QueueEmpty(Queue* q);
// 銷毀隊列 
void QueueDestroy(Queue* q);

Queue.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"// 初始化隊列 
void QueueInit(Queue* q) {assert(q);q->size = 0;q->_front = NULL;q->_rear = NULL;
}
// 隊尾入隊列 
void QueuePush(Queue* q, QDataType data) {assert(q);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("QueuePush()::malloc()");return;}newnode->_data = data;newnode->_next = NULL;//隊列為NULLif (q->_front == NULL){q->_front = q->_rear = newnode;}else{q->_rear->_next = newnode;q->_rear = q->_rear->_next;}q->size++;
}
// 隊頭出隊列 
void QueuePop(Queue* q) {assert(q);assert(q->size != 0);//單個節點if (q->_front == q->_rear){free(q->_front);q->_front = q->_rear = NULL;}//多個節點else{QNode* next = q->_front->_next;free(q->_front);q->_front = next;}q->size--;
}
// 獲取隊列頭部元素 
QDataType QueueFront(Queue* q) {assert(q);assert(q->_front);//隊頭不能為NULLreturn q->_front->_data;
}
// 獲取隊列隊尾元素 
QDataType QueueBack(Queue* q) {assert(q);assert(q->_rear);//隊尾不能為NULLreturn q->_rear->_data;
}
// 獲取隊列中有效元素個數 
int QueueSize(Queue* q) {return q->size;
}
// 檢測隊列是否為空，如果為空返回非零結果，如果非空返回0 
int QueueEmpty(Queue* q) {assert(q);return q->size == 0;
}
// 銷毀隊列 
void QueueDestroy(Queue* q) {assert(q);QNode* cur = q->_front;while (cur){QNode* next = cur->_next;free(cur);cur = next;}q->_front = q->_rear = NULL;q->size = 0;//這個應該留給用戶去釋放/*free(q);q = NULL;*/
}

二叉樹相關功能：

BinaryTree.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include"Queue.h"
typedef char BTDataType;typedef struct BinaryTreeNode
{BTDataType _data;struct BinaryTreeNode* _left;struct BinaryTreeNode* _right;
}BTNode;// 二叉樹銷毀
void BinaryTreeDestory(BTNode** root);// 二叉樹節點個數
int BinaryTreeSize(BTNode* root);// 二叉樹葉子節點個數
int BinaryTreeLeafSize(BTNode* root);// 二叉樹第k層節點個數
int BinaryTreeLevelKSize(BTNode* root, int k);// 二叉樹查找值為x的節點
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);// 二叉樹前序遍歷 
void BinaryTreePrevOrder(BTNode* root);// 二叉樹中序遍歷
void BinaryTreeInOrder(BTNode* root);// 二叉樹后序遍歷
void BinaryTreePostOrder(BTNode* root);// 層序遍歷
void BinaryTreeLevelOrder(BTNode* root);// 判斷二叉樹是否是完全二叉樹
int BinaryTreeComplete(BTNode* root);BTNode* CreatBinaryTree();

BinaryTree.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"BinaryTree.h"
BTNode* BuyNode(BTDataType x) {BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL){perror("Buynode()::malloc()");return newnode;}newnode->_data = x;newnode->_left = NULL;newnode->_right = NULL;return newnode;
}// 二叉樹前序遍歷 
void BinaryTreePrevOrder(BTNode* root) {if (root == NULL)  //當訪問的數為NULL樹時停止訪問{printf("N ");return;}printf("%d ",root->_data);//先便利根節點,整形的數據類型BinaryTreePrevOrder(root->_left);//左子樹BinaryTreePrevOrder(root->_right);//右子樹}
// 二叉樹中序遍歷
void BinaryTreeInOrder(BTNode* root) {if (root == NULL){printf("N ");return;}BinaryTreeInOrder(root->_left);//左子樹printf("%d ", root->_data);//根節點BinaryTreeInOrder(root->_right);//右子樹
}// 二叉樹后序遍歷
void BinaryTreePostOrder(BTNode* root) {if (root == NULL){printf("N ");return;}BinaryTreePostOrder(root->_left);//左子樹BinaryTreePostOrder(root->_right);//右子樹printf("%d ", root->_data);//根節點
}//求二叉樹的高度
int maxDepth(BTNode* root) {if (root == NULL)   //如果為空樹則返回 0 {return 0;}int lefthigh = maxDepth(root->_left);    //記錄樹的左子樹高度int righthigh = maxDepth(root->_right); //記錄樹的右子樹高度//左子樹高則返回左子樹的高度    右子樹高則返回右子樹高度return lefthigh > righthigh ? lefthigh + 1 : righthigh + 1; }// 二叉樹葉子節點個數
int BinaryTreeLeafSize(BTNode* root) {if (root == NULL)  //如果為空樹則返回 0 return 0;if (root->_left == NULL && root->_right == NULL)  //如果是葉子節點就返回 1 return 1;//返回左子樹 與 右子樹總共的葉子節點return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}// 二叉樹第k層節點個數
int BinaryTreeLevelKSize(BTNode* root, int k) {//將找第k層問題轉化成：層序遍歷按照樹的層次進行遍歷，每次遍歷一層，直到遍歷到第k層或者遍歷完整個樹。   if (root == NULL)    //如果為空樹則返回 0 return 0;if (root != NULL && k == 1) //當不為空且k為1時，到達所找層，返回1return 1;//一層一層的往下找if (root != NULL && k > 1)return BinaryTreeLevelKSize(root->_left,k - 1) + BinaryTreeLevelKSize(root->_right,k - 1);
}// 二叉樹查找值為x的節點
//向這種找值的，一定要記錄，把記錄的遞歸返回
BTNode* BinaryTreeFind(BTNode* root, BTDataType x) {if (root == NULL)return NULL;if (root->_data == x)return root;BTNode* find1 = NULL;BTNode* find2 = NULL;find1 = BinaryTreeFind(root->_left, x);  //記錄所找的節點if (find1)//如果左邊找到了就不用去右邊找了return find1;find2 = BinaryTreeFind(root->_right, x);return find2;
}// 二叉樹銷毀
void BinaryTreeDestory(BTNode** root) {if (*root == NULL)return;BinaryTreeDestory(&((*root)->_left));//先銷毀左子樹BinaryTreeDestory(&((*root)->_right));//在銷毀右子樹free(*root);*root = NULL;
}// 二叉樹節點個數
int BinaryTreeSize(BTNode* root) {if (root == NULL)return 0;return BinaryTreeSize(root->_left)+ BinaryTreeSize(root->_right) + 1;
}// 層序遍歷
void BinaryTreeLevelOrder(BTNode* root) {//創建隊列Queue qu;QueueInit(&qu);QueuePush(&qu, root);//開始拖家帶口，當隊列為NULL時，說明已經遍歷完成,循環結束while (!QueueEmpty(&qu)){//先訪問隊頭的元素BTNode* bt = QueueFront(&qu);//獲取隊頭元素printf("%d ", bt->_data);//將樹的左右孩子都帶入隊列中if (bt->_left)QueuePush(&qu, bt->_left);if (bt->_right)QueuePush(&qu, bt->_right);QueuePop(&qu);}QueueDestroy(&qu);}// 判斷二叉樹是否是完全二叉樹
int BinaryTreeComplete(BTNode* root) {//創建隊列Queue qu;QueueInit(&qu);QueuePush(&qu, root);//開始拖家帶口，當隊列為NULL時，說明已經遍歷完成,循環結束while (!QueueEmpty(&qu)){//隊列中存的數據是，樹節點的指針，我們先訪問隊頭的元素BTNode* bt = QueueFront(&qu);//獲取隊頭元素if (bt == NULL){break;}//將樹的左右孩子都帶入隊列中,NULL也不例外QueuePush(&qu, bt->_left);QueuePush(&qu, bt->_right);QueuePop(&qu);}while (!QueueEmpty(&qu)){BTNode* bt = QueueFront(&qu);//獲取隊頭元素//如果在遇到非空的節點，說明它不是一個完全二叉樹返回falseif (bt){return false;}QueuePop(&qu);}QueueDestroy(&qu);return true;
}