二叉樹概念及結構

二叉樹的性質

二叉樹的存盤結構

二叉樹鏈式結構的實作

二叉樹的前序、中序以及后序遍歷

前序遍歷

中序遍歷

后序遍歷

二叉樹的創建

二叉樹的銷毀

二叉樹的其他介面

二叉樹的深度

二叉樹的節點個數

二叉樹的葉子個數

第K層節點個數

查找二叉樹中的元素

二叉樹的層序遍歷

判斷是否為完全二叉樹

測驗用例

二叉樹概念及結構

二叉樹：樹中節點的度不大于2的有序樹，它是一種最簡單且最重要的樹，. 二叉樹的遞回定義為：二叉樹是一棵空樹，或者是一棵由一個根節點和兩棵互不相交的，分別稱作根的左子樹和右子樹組成的非空樹；左子樹和右子樹又同樣都是二叉樹，

二叉樹的性質

1. 若規定根節點的層數為1，則一棵非空二叉樹的第 i 層上最多有 $2^{(i-1)}$ 個結點

2. 若規定根節點的層數為1，則深度為 h 的二叉樹的最大結點數是 $2^{h}-1$

3. 對任何一棵二叉樹, 如果度為0其葉結點個數為 $n_{0}$ , 度為2的分支結點個數為 $n_{2}$ ,則有 $n_{0}$ = $n_{2}$ ＋1

4. 若規定根節點的層數為1，具有n個結點的滿二叉樹的深度，h = $log{_{2}}^{(n+1)}$

5. 對于具有 n 個結點的完全二叉樹，如果按照從上至下從左至右的陣列順序對所有節點從0開始編號，則對于序號為 i 的結點有：

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

(2). 若 2i+1< n,左孩子序號: 2i+1;否則無左孩子

(3). 若 2i+2< n,右孩子序號: 2i+2;否則無右孩子

二叉樹的存盤結構

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

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

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

二叉樹鏈式結構的實作

先給出構成二叉樹節點的結構體：

typedef char BTDataType;

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

由于鏈式二叉樹結構的多變性，我們往往需要根據一棵二叉樹的遍歷序列來創建二叉樹，這里先說明二叉樹的遍歷，

二叉樹的前序、中序以及后序遍歷

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

1. 前序遍歷(Preorder Traversal 亦稱先序遍歷)——訪問根結點的操作發生在遍歷其左右子樹之前，

2. 中序遍歷(Inorder Traversal)——訪問根結點的操作發生在遍歷其左右子樹之中（間），

3. 后序遍歷(Postorder Traversal)——訪問根結點的操作發生在遍歷其左右子樹之后，

前序遍歷

以列印該節點資料為例，若為空節點，則列印NULL，對于不同的操作，可以將其替換，

前序遍歷的順序為：根——>左子樹——>右子樹，先列印根的值，再遞回遍歷左子樹與右子樹，

void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	printf("%c ", root->data);
	PreOrder(root->left);
	PreOrder(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);
}

二叉樹的創建

這里給定一個二叉樹的前序遍歷陣列，根據這個前序遍歷陣列來創建二叉樹，

char str[] = "abc##de#g##f###";//"#"表示空格
int i = 0;
BTNode* root = BinaryTreeCreat(str,&i);

由于需要在遞回時正確的遍歷陣列，對下標 i 傳參時應傳地址，

BTNode* BinaryTreeCreat(char* str, int* pi)
{
    if(str[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }
    
    BTNode* root = (BTNode*)malloc(sizeof(BTNode));
    root->data = str[*pi];
    (*pi)++;
    
    root->left = BinaryTreeCreat(str,pi);
    root->right = BinaryTreeCreat(str,pi);
    
    return root;
}

二叉樹的銷毀

由于二叉樹中的每一個節點都是用我們開辟的空間，故銷毀二叉樹時需要將每個節點都釋放，

先遞回到最后一層，然后不斷向上釋放，

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

	free(root);
	root = NULL;
}

二叉樹的其他介面

二叉樹的深度

二叉樹的深度為其左右子樹中的最大深度加1，

int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
		return 0;
	int leftDepth = BinaryTreeDepth(root->left);
	int rightDepth = BinaryTreeDepth(root->right);
	return (leftDepth > rightDepth) ? (leftDepth + 1) : (rightDepth + 1);
}

二叉樹的節點個數

只要該節點不為空，就回傳左子樹節點個數加右子樹節點個數加1，

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

二叉樹的葉子個數

當節點左右均為空時回傳1，否則繼續遞回其左右子樹，

int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	if (root->left == NULL && root->right == NULL)
		return 1;
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

第K層節點個數

求第k層的節點個數就是求其左右子樹的k-1層節點的個數之和，當k = 1時，說明已經來到二叉樹的第k層，存在結點時回傳1即可，

int BinaryTreeLevelKSize(BTNode* root, int k)
{
	assert(k >= 1);
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

查找二叉樹中的元素

當節點的值與查找值相等時，回傳該節點，否則去其左右子樹中尋找，若未找到，則回傳空，

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->data == x)
		return root;

	BTNode* leftRet = BinaryTreeFind(root->left, x);
	if (leftRet)
		return leftRet;

	BTNode* rightRet = BinaryTreeFind(root->right, x);
	if (rightRet)
		return rightRet;

	return NULL;
}

二叉樹的層序遍歷

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

實作二叉樹的層序遍歷我們需要用到佇列這一資料結構，佇列在之前文章已經給出，這里直接使用它的各類介面，

思路：

以列印資料為例，先把根節點入佇列，然后保存隊頭節點，出隊頭節點并將其列印，將其左右不為空的節點入隊，當佇列不為空時，回圈上述操作，

代碼：

void LevelOrder(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);
	}

	QueueDestroy(&q);
}

判斷是否為完全二叉樹

我們先來看一下完全二叉樹與非完全二叉樹有什么不同：

完全二叉樹僅在最后一層有空缺節點，且最后一層的節點從左到右按順序鏈接，

我們將層序遍歷稍作更改，以相同的方式將二叉樹的節點入隊和出隊，不同的是，若根節點的子節點為空，也將其放入佇列中，這里把空節點放入佇列中是指這個佇列元素所存盤的資料為BTNode*型的空指標，其佇列節點中的next指標依舊指向下一個節點，

對于完全二叉樹而言，出現第一個”空“時，后面全為”空“；

而非完全二叉樹出現第一個”空“時，后面仍有存盤不為空的節點，

我們只需在遇到第一個“空”時停下，檢查佇列剩余節點中是否有不為“空”的節點，若無，則為完全二叉樹，否則為非完全二叉樹，

bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
		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)
			return false;
	}

	QueueDestroy(&q);
	return true;
}

測驗用例

void Test()
{
	char str[] = "abc##de#g##f###";
	int i = 0;
	BTNode* root = BinaryTreeCreat(str, &i);

	PreOrder(root);
	printf("\n");

	InOrder(root);
	printf("\n");

	PostOrder(root);
	printf("\n");

	printf("BinaryTreeDepth: %d\n", BinaryTreeDepth(root));
	printf("BinaryTreeNodeSize: %d\n", BinaryTreeNodeSize(root));
	printf("BinaryTreeLeafSize: %d\n", BinaryTreeLeafSize(root));
	printf("BinaryTreeLevelKSize: %d\n", BinaryTreeLevelKSize(root, 3));

	BTNode* ret = BinaryTreeFind(root, 'c');
	printf("%c\n", ret->data);

	LevelOrder(root);
	printf("\n");

	printf("BinaryTreeComplete:%d\n", BinaryTreeComplete(root));

	DestroyBinaryTree(root);
}

int main()
{
	Test();
	return 0;
}

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

標籤：其他

上一篇：《手撕資料結構經典題系列》用佇列實作堆疊

下一篇：應屆生校招套路總結——看完同學們都能進大廠

【資料結構】二叉樹0.6萬字詳解

二叉樹概念及結構

二叉樹的性質

二叉樹的存盤結構

二叉樹鏈式結構的實作

二叉樹的前序、中序以及后序遍歷

前序遍歷

中序遍歷

后序遍歷

二叉樹的創建

二叉樹的銷毀

二叉樹的其他介面

二叉樹的深度

二叉樹的節點個數

二叉樹的葉子個數

第K層節點個數

查找二叉樹中的元素

二叉樹的層序遍歷

判斷是否為完全二叉樹

測驗用例