【數據結構】09.樹與二叉樹

一、樹的概念與結構

1.1 樹的概念

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

根結點：根節點沒有前驅結點。
除根節點外，其余結點被分成是一棵結構與樹類似的子樹。每棵子樹的根結點有且只有一個前驅，可以有0個或多個后繼。
因此，樹是遞歸定義的。

在這里插入圖片描述

1.2 樹的相關概念

在這里插入圖片描述

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

1.3 樹的表示法

樹結構相對線性表就比較復雜了，要存儲表示起來就比較麻煩了，既要保存值域，也要保存結點和結點之間的關系，實際中樹有很多種表示方式如：雙親表示法，孩子表示法、孩子雙親表示法以及孩子兄弟表示法等。

在介紹以下存儲結構的過程中，我們都以下面這個樹為例子。在這里插入圖片描述

1.3.1 雙親表示法

我們假設以一組連續空間存儲樹的結點，同時在每個結點中，附設一個指示器指示其雙親結點到鏈表中的位置。也就是說，每個結點除了知道自已是誰以外，還知道它的雙親在哪里。
在這里插入圖片描述
其中data是數據域，存儲結點的數據信息。而parent是指針域，存儲該結點的雙親在數組中的下標。
以下是我們的雙親表示法的結點結構定義代碼。

/*樹的雙親表示法結點結構定義*/
#define MAX_TREE_SIZE 100
typedef int TElemType;	//樹結點的數據類型，目前暫定為整型
/*結點結構*/
typedef struct TreeNode
{TElemType data;	//結點數據int parent;	//雙親位置
}TreeNode;
/*樹結構*/
typedef struct
{TreeNode nodes[MAX_TREE_SIZE];	//結點數組int r, n;	//根的位置和結點數
}PTree;

這樣的存儲結構，我們可以根據結點的parent 指針很容易找到它的雙親結點，所用的時間復雜度為0(1)，直到parent為-1時，表示找到了樹結點的根。可如果我們要知道結點的孩子是什么，對不起，請遍歷整個結構才行。

1.3.2 孩子兄弟表示法

剛才我們分別從雙親的角度和從孩子的角度研究樹的存儲結構，如果我們從樹結點的兄弟的角度又會如何呢?當然，對于樹這樣的層級結構來說，只研究結點的兄弟是不行的，我們觀察后發現，任意一棵樹，它的結點的第一個孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。 因此，我們設置兩個指針，分別指向該結點的第一個孩子和此結點的右兄弟。

在這里插入圖片描述

/*樹的孩子兄弟表示法結構定義*/
typedef struct TreeNode
{TElemtype data;struct TreeNode *firstchild, *rightsib;
} TreeNode,* pTreeNode;

1.4 樹在實際中的應用

在這里插入圖片描述

二、二叉樹的概念及結構

2.1概念

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

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

在這里插入圖片描述

從上圖可以看出：

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

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

2.2 特殊的二叉樹

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

2.3 二叉樹的性質

若規定根節點的層數為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.4 二叉樹的存儲結構

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

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

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

普通的二叉樹是不適合用數組來存儲的，因為可能會存在大量的空間浪費。而完全二叉樹更適合使用順序結構存儲。現實中我們通常把堆(一種二叉樹)使用順序結構的數組來存儲，需要注意的是這里的堆和操作系統虛擬進程地址空間中的堆是兩回事，一個是數據結構，一個是操作系統中管理內存的一塊區域分段。
具體的實現及應用請查看：【數據結構】08.堆及堆的應用

四、二叉樹的鏈式結構及其實現

4.1 二叉樹的遍歷

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

4.1.1 前序遍歷

//根 左子樹 右子樹
void PrevOrder(pTreeNode root)
{if (root == NULL){printf("NULL ");return;}printf("%d ", root->val);PrevOrder(root->left);PrevOrder(root->right);
}

下圖為遞歸過程：
在這里插入圖片描述

4.1.2 中序遍歷

//左子樹 根 右子樹
void InOrder(pTreeNode root)
{if (root == NULL){printf("NULL ");return;}InOrder(root->left);printf("%d ", root->val);InOrder(root->right);
}

下面為遞歸過程：
在這里插入圖片描述

4.1.3 后序遍歷

//左子樹 右子樹 根
void PostOrder(pTreeNode root)
{if (root == NULL){printf("NULL ");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->val);
}

下面為遞歸過程：
在這里插入圖片描述

4.2.4 層序遍歷

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

我們這里介入隊列來進行二叉樹的前序遍歷。

// 層序遍歷
void LevelOrder(pTreeNode root)
{Queue q;QueueInit(&q);if (root){QueuePush(&q, root);}while (!QueueEmpty(&q)){pTreeNode front = QueueFront(&q);QueuePop(&q);if (front == NULL){printf("NULL ");}else{printf("%d ", front->val);QueuePush(&q, front->left);QueuePush(&q, front->right);}}QueueDestory(&q);
}

4.1 二叉樹的創建與銷毀

二叉樹的創建與銷毀，我們以二叉樹遍歷為例題。

//二叉樹的創建
struct TreeNode* Creat(char* arr,int n,int* i)
{ if(*i<n&&arr[*i]=='#'){(*i)++;return NULL;}TreeNode* newnode=(TreeNode*)malloc(sizeof(TreeNode));newnode->left=NULL;newnode->right=NULL;newnode->val=arr[(*i)++];newnode->left=Creat(arr,n,i);newnode->right=Creat(arr,n,i);return newnode;
}

//二叉樹的銷毀
void TreeDestroy(struct TreeNode* root)
{if(root==NULL){return;}TreeDestroy(root->left);TreeDestroy(root->right);free(root);
}

4.3 二叉樹的其他操作

以下的操作均是沿著遍歷的思想展開的。

// 二叉樹節點個數
int TreeSize(pTreeNode root)
{if (root == NULL){return 0;}return TreeSize(root->left) + TreeSize(root->right) + 1;
}

// 二叉樹葉子節點個數
int TreeLeafSize(pTreeNode 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(pTreeNode 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的節點
pTreeNode TreeFind(pTreeNode root, TreeDataType x)
{if (root == NULL){return NULL;}//相等就返回if (root->val == x)return root;//找左子樹pTreeNode left=TreeFind(root->left, x);if (left){return left;}//找右子樹pTreeNode right = TreeFind(root->right, x);if (right){return right;}//都沒找到return NULL;
}

//二叉樹的高度
int TreeHeight(pTreeNode root)
{if (root == NULL){return 0;}int max_left = TreeHeight(root->left) ;int max_right = TreeHeight(root->right);return max_left > max_right ? max_left + 1 : max_right + 1;
}

//判斷是否是完全二叉樹
bool TreeComplete(pTreeNode root)
{Queue q;QueueInit(&q);if (root){QueuePush(&q, root);}while (!QueueEmpty(&q)){pTreeNode front = QueueFront(&q);QueuePop(&q);if (front == NULL){break;}else{QueuePush(&q, front->left);QueuePush(&q, front->right);}}while (!QueueEmpty(&q)){pTreeNode front = QueueFront(&q);QueuePop(&q);if (front){QueueDestory(&q);return false;}}QueueDestory(&q);return true;
}