久久亚洲国产精品五月天婷 ,免费xxxx性欧美18vr,麻豆国产成人av在线

二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是指，用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關(guān)系。通常的方法是鏈表中每個(gè)結(jié)點(diǎn)由三個(gè)域組成，數(shù)據(jù)域和左右指針域，左右指針分別用來給出該結(jié)點(diǎn)左孩子和右孩子所在的鏈結(jié)點(diǎn)的存儲(chǔ)地址

之前我們的重點(diǎn)學(xué)習(xí)二叉樹都是完全二叉樹，接下來我們來說下普通二叉樹，普通的二叉樹如果我們使用數(shù)組存儲(chǔ)，那么會(huì)浪費(fèi)相當(dāng)多的空間的，所以我們選擇鏈表存儲(chǔ)，我們先再來復(fù)習(xí)下二叉樹的結(jié)構(gòu)吧。

二叉樹的結(jié)構(gòu)和概念

二叉樹概念是：

1. 空樹

2. 非空：根節(jié)點(diǎn)，根節(jié)點(diǎn)的左子樹、根節(jié)點(diǎn)的右子樹組成的。

從概念中可以看出，二叉樹定義是遞歸式的。

我們就手動(dòng)創(chuàng)建一個(gè)二叉樹，用于學(xué)習(xí)二叉樹的訪問吧，結(jié)構(gòu)如下：

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;
BTNode* BuyNode(BTDataType* x)
{
	BTNode* NewNode = (BTNode*)malloc(sizeof(BTNode));
	assert(NewNode);
	NewNode->data = x;
	NewNode->left = NULL;
	NewNode->right = NULL;
	return NewNode;
}
BTNode* CreatBinaryTree()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);
	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;
	return node1;
}

我們可以根據(jù)上述的結(jié)構(gòu)進(jìn)行二叉樹的后續(xù)操作啦。

二叉樹的操作

學(xué)習(xí)二叉樹結(jié)構(gòu)，最簡單的方式就是遍歷。

所謂二叉樹遍歷(Traversal)是按照某種特定的規(guī)則，依次對(duì)二叉樹中的節(jié)點(diǎn)進(jìn)行相應(yīng)的操作，并且每個(gè)節(jié)點(diǎn)只操作一次。訪問結(jié)點(diǎn)所做的操作依賴于具體的應(yīng)用問題。遍歷是二叉樹上最重要的運(yùn)算之一，也是二叉樹上進(jìn)行其它運(yùn)算的基礎(chǔ)。

按照規(guī)則，二叉樹的遍歷有：前序/中序/后序的遞歸結(jié)構(gòu)遍歷：

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

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

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

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

前序遍歷

我們都知道二叉樹我們可以分為根左子樹右子樹，這三個(gè)部分，我們先序遍歷，就是先訪問二叉樹的根，在訪問左子樹，最后訪問右子樹，如果訪問到空樹我們使用 ‘*’ 代替，我們用代碼控制下：

我們自己創(chuàng)建的二叉樹的圖如下：

void Preorder(BTNode* root)
{
	if (root == NULL)
	{
		printf("* ");//空樹打印 * 
		return ;
	}
	printf("%d ", root->data);//先訪問 根
	Preorder(root->left);//再訪問左子樹
	Preorder(root->right);//最后訪問右子樹
}

中序遍歷和后序遍歷

這兩個(gè)遍歷和上面對(duì)比就是把訪問根的順序變了，不在詳細(xì)說了。

void Inorder(BTNode* root)//中序遍歷
{
	if (root == NULL)
	{
		printf("* ");//空樹打印 * 
		return;
	}
	Preorder(root->left);//先訪問左子樹
	printf("%d ", root->data);//再訪問 根
	Preorder(root->right);//最后訪問右子樹
}
void Postorder(BTNode* root)//后序遍歷
{
	if (root == NULL)
	{
		printf("* ");//空樹打印 * 
		return;
	}
	Preorder(root->left);//先訪問左子樹
	Preorder(root->right);//再訪問右子樹
	printf("%d ", root->data);//最后訪問 根
}

二叉樹的節(jié)點(diǎn)個(gè)數(shù)

我們接下來要求出二叉樹的節(jié)點(diǎn)個(gè)數(shù)。

1. 我們使用計(jì)數(shù)器進(jìn)行操作。缺點(diǎn)：每次使用前全局變量要置為0，比較麻煩。

2. 我們使用分治的思路，轉(zhuǎn)化為這個(gè)根+左子樹的節(jié)點(diǎn)+右子樹的節(jié)點(diǎn)

我們來一個(gè)個(gè)實(shí)現(xiàn)吧。

思路一：(不常用)

我們定義一個(gè)全局變量size，使用前序遍歷，然后把其中打印部分去掉換成 ++size即可，我們要在每次使用該函數(shù)時(shí)，手動(dòng)把我們定義的全局變量置為0。

int size；
void TreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	size++;//計(jì)數(shù)器
	TreeSize(root->left);//訪問左子樹
	TreeSize(root->right);//訪問右子樹
}
int main()
{
	BTNode* root = CreatBinaryTree();
	size = 0;
	TreeSize(root);
	printf("TreeSize = %d\n", size);
	return 0;
}

思路二：

我們可以使用分治的思想轉(zhuǎn)化為求該節(jié)點(diǎn)的左子樹+右子數(shù)+根，如果為NULL，就返回0.

int TreeSize2(BTNode* root)
{
	if (root == NULL)//為NULL返回0
	{
		return 0;
	}
	return TreeSize2(root->left) + TreeSize2(root->right) + 1;
}

求二叉樹葉子結(jié)點(diǎn)個(gè)數(shù)

要求葉子結(jié)點(diǎn)，就是左右的子樹都是空樹，才是一個(gè)葉子節(jié)點(diǎn)，我們可以轉(zhuǎn)化為求左子樹的葉子+右子樹的葉子。

int TreeLeafSize(BTNode* root)//求葉子節(jié)點(diǎn)
{
	if (root == NULL)//空樹返回0
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)//左子樹為空并且右子樹為空返回1
	{
		return 1;
	}
	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

求二叉樹的深度

我們還是采用分治的思想，我們先求出左子樹的高度，再求出右子樹的高度，進(jìn)行對(duì)比，比較時(shí)不要忘了自身也是有高度的，最后把二叉樹拆到最小的空樹時(shí)返回0就好啦。

int TreeDepth(BTNode* root)
{
	if (root == NULL)//空樹返回0
	{
		return 0;
	}
	int Leftdepth = TreeDepth(root->left);//求出左邊高度
	int Rightdepth = TreeDepth(root->right);//求出右邊高度
	return Leftdepth > Rightdepth ? Leftdepth + 1 : Rightdepth + 1;//返回時(shí)加上自身返回
}

在二叉樹查找為X的結(jié)點(diǎn)

我們?cè)诙鏄渲胁檎医Y(jié)點(diǎn)，可以使用前序遍歷，找到該節(jié)點(diǎn)時(shí)我們直接返回不用在查找。整體上采用前序遍歷，我們需要注意，在遍歷左右子樹時(shí)，我們應(yīng)該保存節(jié)點(diǎn)的值方便返回。

BTNode* TreeFind(BTNode* root, BTDataType x)//查找二叉樹中值為x的節(jié)點(diǎn)
{
	if (root == NULL)//為空返回空
	{
		return NULL;
	}
	if (root->data == x)//相等就返回節(jié)點(diǎn)
	{
		return root;
	}
	BTNode* RetLeft = TreeFind(root->left, x);//保存左節(jié)點(diǎn)值，方便直接返回
	if (RetLeft)
	{
		return RetLeft;
	}
	BTNode* RetRight = TreeFind(root->right, x);//保存右節(jié)點(diǎn)值，方便直接返回
	if (RetRight)
	{
		return RetRight;
	}
	return NULL;//都找不到返回NULL
}