樹

1.樹的概念和模型

樹：是一種非線性的數(shù)據(jù)結(jié)構(gòu)，它是由n(n>=0)個(gè)有限結(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。把它 叫做樹是因?yàn)樗雌饋硐褚豢玫箳斓臉?，也就是說它是根朝上，而葉朝下的。

有一個(gè)特殊的結(jié)點(diǎn)，稱為根結(jié)點(diǎn)，根節(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)

除根節(jié)點(diǎn)外，其余結(jié)點(diǎn)被分成M(M>0)個(gè)互不相交的集合T1、T2、……、Tm，其中每一個(gè)集 合Ti(1<= i <= m)又是一棵結(jié)構(gòu)與樹類似的子樹。每棵子樹的根結(jié)點(diǎn)有且只有一個(gè)前驅(qū)，可以 有0個(gè)或多個(gè)后繼

因此，樹是遞歸定義的。

節(jié)點(diǎn)的度：一個(gè)節(jié)點(diǎn)含有的子樹的個(gè)數(shù)稱為該節(jié)點(diǎn)的度; 如上圖：A的為6

葉節(jié)點(diǎn)或終端節(jié)點(diǎn)：度為0的節(jié)點(diǎn)稱為葉節(jié)點(diǎn); 如上圖：B、C、H、I…等節(jié)點(diǎn)為葉節(jié)點(diǎn)

非終端節(jié)點(diǎn)或分支節(jié)點(diǎn)：度不為0的節(jié)點(diǎn); 如上圖：D、E、F、G…等節(jié)點(diǎn)為分支節(jié)點(diǎn)

雙親節(jié)點(diǎn)或父節(jié)點(diǎn)：若一個(gè)節(jié)點(diǎn)含有子節(jié)點(diǎn)，則這個(gè)節(jié)點(diǎn)稱為其子節(jié)點(diǎn)的父節(jié)點(diǎn); 如上圖：A是B 的父節(jié)點(diǎn)

孩子節(jié)點(diǎn)或子節(jié)點(diǎn)：一個(gè)節(jié)點(diǎn)含有的子樹的根節(jié)點(diǎn)稱為該節(jié)點(diǎn)的子節(jié)點(diǎn); 如上圖：B是A的孩子節(jié)點(diǎn)

兄弟節(jié)點(diǎn)：具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)互稱為兄弟節(jié)點(diǎn); 如上圖：B、C是兄弟節(jié)點(diǎn)

樹的度：一棵樹中，最大的節(jié)點(diǎn)的度稱為樹的度; 如上圖：樹的度為6

節(jié)點(diǎn)的層次：從根開始定義起，根為第1層，根的子節(jié)點(diǎn)為第2層，以此類推;

樹的高度或深度：樹中節(jié)點(diǎn)的最大層次; 如上圖：樹的高度為4

節(jié)點(diǎn)的祖先：從根到該節(jié)點(diǎn)所經(jīng)分支上的所有節(jié)點(diǎn);如上圖：A是所有節(jié)點(diǎn)的祖先

子孫：以某節(jié)點(diǎn)為根的子樹中任一節(jié)點(diǎn)都稱為該節(jié)點(diǎn)的子孫。如上圖：所有節(jié)點(diǎn)都是A的子孫

森林：由m(m>0)棵互不相交的多顆樹的集合稱為森林;(數(shù)據(jù)結(jié)構(gòu)中的學(xué)習(xí)并查集本質(zhì)就是 一個(gè)森林)

2.樹的表示

樹結(jié)構(gòu)相對(duì)線性表就比較復(fù)雜了，要存儲(chǔ)表示起來就比較麻煩了，實(shí)際中樹有很多種表示方式， 如：雙親表示法，孩子表示法、孩子兄弟表示法等等。我們這里就簡(jiǎn)單的了解其中最常用的孩子 兄弟表示法。

typedef int DataType;
struct Node
{
    struct Node* firstChild1;    // 第一個(gè)孩子結(jié)點(diǎn)
    struct Node* pNextBrother;   // 指向其下一個(gè)兄弟結(jié)點(diǎn)
    DataType _data;               // 結(jié)點(diǎn)中的數(shù)據(jù)域
};

二叉樹

二叉樹：一棵二叉樹是結(jié)點(diǎn)的一個(gè)有限集合，該集合或者為空，或者是由一個(gè)根節(jié)點(diǎn)加上兩棵別稱為左子 樹和右子樹的二叉樹組成。 二叉樹的特點(diǎn)：

每個(gè)結(jié)點(diǎn)最多有兩棵子樹，即二叉樹不存在度大于2的結(jié)點(diǎn)。

二叉樹的子樹有左右之分，其子樹的次序不能顛倒。

1.特殊的二叉樹：

滿二叉樹：一個(gè)二叉樹，如果每一個(gè)層的結(jié)點(diǎn)數(shù)都達(dá)到最大值，則這個(gè)二叉樹就是滿二叉 樹。也就是說，如果一個(gè)二叉樹的層數(shù)為K，且結(jié)點(diǎn)總數(shù)是(2^k) -1 ，則它就是滿二叉樹。

完全二叉樹：完全二叉樹是效率很高的數(shù)據(jù)結(jié)構(gòu)，完全二叉樹是由滿二叉樹而引出來的。對(duì) 于深度為K的，有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為K的滿二叉樹中編號(hào) 從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)稱之為完全二叉樹。 要注意的是滿二叉樹是一種特殊的完全二叉樹。(假設(shè)樹的高度是h，前h-1層都是滿的，最后一層不滿，但最后一層從左往右都是滿的)

2.二叉樹的存儲(chǔ)結(jié)構(gòu)

? 二叉樹一般可以使用兩種結(jié)構(gòu)存儲(chǔ)，一種順序結(jié)構(gòu)，一種鏈?zhǔn)浇Y(jié)構(gòu)。

(1)二叉樹的性質(zhì)

若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，則一棵非空二叉樹的第i層上最多有2(i-1) 個(gè)結(jié)點(diǎn).

若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，則深度為h的二叉樹的最大結(jié)點(diǎn)數(shù)是2h- 1.

對(duì)任何一棵二叉樹, 如果度為0其葉結(jié)點(diǎn)個(gè)數(shù)為 n0, 度為2的分支結(jié)點(diǎn)個(gè)數(shù)為 n2,則有n0=n2 +1

若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，具有n個(gè)結(jié)點(diǎn)的滿二叉樹的深度，h=LogN

(2)順序存儲(chǔ)：

? 順序結(jié)構(gòu)存儲(chǔ)就是使用數(shù)組來存儲(chǔ)，一般使用數(shù)組只適合表示完全二叉樹，因?yàn)椴皇峭耆鏄?會(huì)有空間的浪費(fèi)。而現(xiàn)實(shí)中使用中只有堆才會(huì)使用數(shù)組來存儲(chǔ)，二叉樹順序存儲(chǔ)在物理上是一個(gè)數(shù)組，在邏輯上是一顆二叉樹。

(3)鏈?zhǔn)酱鎯?chǔ)：

? 二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關(guān)系。 通常的 方法是鏈表中每個(gè)結(jié)點(diǎn)由三個(gè)域組成，數(shù)據(jù)域和左右指針域，左右指針分別用來給出該結(jié)點(diǎn)左孩 子和右孩子所在的鏈結(jié)點(diǎn)的存儲(chǔ)地址 。鏈?zhǔn)浇Y(jié)構(gòu)又分為二叉鏈和三叉鏈，當(dāng)前我們學(xué)習(xí)中一般都 是二叉鏈，后面課程學(xué)到高階數(shù)據(jù)結(jié)構(gòu)如紅黑樹等會(huì)用到三叉鏈。

// 二叉鏈
struct BinaryTreeNode
{
   struct BinTreeNode* pLeft;   // 指向當(dāng)前節(jié)點(diǎn)左孩子
   struct BinTreeNode* pRight; // 指向當(dāng)前節(jié)點(diǎn)右孩子
   BTDataType _data; // 當(dāng)前節(jié)點(diǎn)值域
}
// 三叉鏈
struct BinaryTreeNode
{
   struct BinTreeNode* pParent; // 指向當(dāng)前節(jié)點(diǎn)的雙親
   struct BinTreeNode* pLeft;   // 指向當(dāng)前節(jié)點(diǎn)左孩子
   struct BinTreeNode* pRight; // 指向當(dāng)前節(jié)點(diǎn)右孩子
   BTDataType _data; // 當(dāng)前節(jié)點(diǎn)值域
}；

3.二叉樹鏈?zhǔn)浇Y(jié)構(gòu)的遍歷

? 所謂遍歷(Traversal)是指沿著某條搜索路線，依次對(duì)樹中每個(gè)結(jié)點(diǎn)均做一次且僅做一次訪問。訪 問結(jié)點(diǎn)所做的操作依賴于具體的應(yīng)用問 題。 遍歷是二叉樹上最重要的運(yùn)算之一，是二叉樹上進(jìn)行 其它運(yùn)算之基礎(chǔ)。

前序/中序/后序的遞歸結(jié)構(gòu)遍歷：是根據(jù)訪問結(jié)點(diǎn)操作發(fā)生位置命名 5

NLR：前序遍歷(Preorder Traversal 亦稱先序遍歷)——訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之前。

LNR：中序遍歷(Inorder Traversal)——訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之中 (間)。

LRN：后序遍歷(Postorder Traversal)——訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之后。

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

層序遍歷：除了先序遍歷、中序遍歷、后序遍歷外，還可以對(duì)二叉樹進(jìn)行層序遍歷。設(shè)二叉樹的 根節(jié)點(diǎn)所在層數(shù)為1，層序遍歷就是從所在二叉樹的根節(jié)點(diǎn)出發(fā)，首先訪問第一層的樹根節(jié)點(diǎn)，然 后從左到右訪問第2層上的節(jié)點(diǎn)，接著是第三層的節(jié)點(diǎn)，以此類推，自上而下，自左至右逐層訪問樹的結(jié)點(diǎn)的過程就是層序遍歷。(廣度優(yōu)先)

4.二叉樹實(shí)現(xiàn)的代碼

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

typedef char BTDataType;
typedef struct BinaryTreeNode
{
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
	BTDataType data;
}BTNode;
//樹一般不直接遍歷沒有意義，就前中后序遍歷
//分治遞歸算法
void PrevOrder(BTNode* root)//前序
{
	if (NULL == root)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}
void InOrder(BTNode* root)//中序
{
	if (NULL == root)
	{
		printf("NULL ");
		return;
	}
	InOrder(root->left);
	printf("%c ", root->data);
	InOrder(root->right);
}
void PostOrder(BTNode* root)//后序
{
	if (NULL == root)
	{
		printf("NULL ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%c ", root->data);
}
//int size = 0;//方式一：定義全局變量（一般不用）
int TreeSize(BTNode* root)//求樹節(jié)點(diǎn)的個(gè)數(shù)
{
	//if (NULL == root)
	//{
	//	return;
	//}
	//++size;
	//TreeSize(root->left);
	//TreeSize(root->right);
	//return size;
	//方式二
	return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}
int TreeLeafSize(BTNode* root)//求葉子節(jié)點(diǎn)的個(gè)數(shù)
{
	if (NULL == root)
		return 0;
	if (NULL == root->left && NULL == root->right)
		return 1;
	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}
int main()
{
	BTNode* A = (BTNode*)malloc(sizeof(BTNode));
	A->data = 'A';
	A->left = NULL;
	A->right = NULL;
	BTNode* B = (BTNode*)malloc(sizeof(BTNode));
	B->data = 'B';
	B->left = NULL;
	B->right = NULL;
	BTNode* C = (BTNode*)malloc(sizeof(BTNode));
	C->data = 'C';
	C->left = NULL;
	C->right = NULL;
	BTNode* D = (BTNode*)malloc(sizeof(BTNode));
	D->data = 'D';
	D->left = NULL;
	D->right = NULL;
	BTNode* E = (BTNode*)malloc(sizeof(BTNode));
	E->data = 'E';
	E->left = NULL;
	E->right = NULL;
	A->left = B;
	A->right = C;
	B->left = D;
	B->right = E;
	PrevOrder(A);
	printf("\n");
	InOrder(A);
	printf("\n");
	PostOrder(A);
	printf("\n");
	printf("%d\n", TreeSize(A));
	printf("%d\n", TreeLeafSize(A));
	return 0;
}
//判斷樹是否是高度平衡的二叉樹。（一個(gè)二叉樹每個(gè)節(jié)點(diǎn) 的左右兩個(gè)子樹的高度差的絕對(duì)值不超過 1 。）
struct TreeNode {
	int val;
	struct TreeNode* left;
	struct TreeNode* right;
};
//求樹的最大深度
int maxDepth(struct TreeNode* root) {
	if (NULL == root)
		return 0;
	int leftDepth = maxDepth(root->left);
	int rightDepth = maxDepth(root->right);
	return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;}
bool isBalanced(struct TreeNode* root)
{
	if (NULL == root)
		return true;
	int leftDepth = maxDepth(root->left);
	int rightDepth = maxDepth(root->right);
	return abs(leftDepth - rightDepth) < 2
		&& isBalanced(root->left)
		&& isBalanced(root->right);
}
//給你二叉樹的根節(jié)點(diǎn) root ，返回它節(jié)點(diǎn)值的 前序 遍歷。
int Treesize(struct TreeNode* root)
{
	return root == NULL ? 0 : Treesize(root->left) + Treesize(root->right) + 1;
}
void PrevOrder(struct TreeNode* root, int* a, int* pi)
{
	if (NULL == root)
		return;
	a[*pi] = root->val;
	++(*pi);
	PrevOrder(root->left, a, pi);
	PrevOrder(root->right, a, pi);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
	int size = Treesize(root);//計(jì)算樹的節(jié)點(diǎn)的個(gè)數(shù)
	int* a = malloc(sizeof(int) * size);
	int i = 0;
	PrevOrder(root, a, &i);
	*returnSize = size;
	return a;
}