前言

二叉樹(shù)不同于順序表，一顆普通的二叉樹(shù)是沒(méi)有增刪改查的意義。普通的二叉樹(shù)用來(lái)存儲(chǔ)數(shù)據(jù)是不方便的。但是二叉樹(shù)的一些基本實(shí)現(xiàn)結(jié)構(gòu)，例如前序遍歷，中序遍歷。。。等等都是對(duì)我們學(xué)習(xí)更深層次的二叉樹(shù)打下夯實(shí)的基礎(chǔ)。

?二叉樹(shù)節(jié)點(diǎn)聲明

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

二叉樹(shù)的遍歷

二叉樹(shù)的遍歷，是學(xué)習(xí)二叉樹(shù)結(jié)構(gòu)的重要部分。二叉樹(shù)的遍歷主要分為三種：1.前序遍歷? ?2.中序遍歷 3.后序遍歷。首先我們要知道一顆二叉樹(shù)分為根，左子樹(shù)，右子樹(shù)。而三種遍歷方式也是圍繞著根來(lái)實(shí)現(xiàn)的。?

?

構(gòu)建二叉樹(shù)

我們按上圖來(lái)構(gòu)建一顆二叉樹(shù)

BTNode* CreatTreeNode(BTDataType x){	BTNode* node = (BTNode*)malloc(sizeof(BTDataType));	node->data = x;	node->right = NULL;	node->left = NULL;	return node;}int main(){   	BTNode* A = CreatTreeNode("A");	BTNode* B = CreatTreeNode("B");	BTNode* C = CreatTreeNode("C");	BTNode* D = CreatTreeNode("D");	BTNode* E = CreatTreeNode("E");	BTNode* F = CreatTreeNode("F");	A->left = B;	A->right = C;	B->left = D;	C->left = E;	C->right = F;}

?

1.前序遍歷

前序遍歷的順序?yàn)?根 左子樹(shù) 右子樹(shù) 顧名思義就是先訪問(wèn)根節(jié)點(diǎn)再訪問(wèn)左節(jié)點(diǎn)最后訪問(wèn)右節(jié)點(diǎn)。

按照前序遍歷，則上圖的遍歷順序?yàn)椋?/span>A B D NULL NULL NULL C E NULL NULL F NULL NULL

// 二叉樹(shù)前序遍歷 void BinaryTreePrevOrder(BTNode* root){	if (root == NULL) //等于NULL就直接返回	{		printf("NULL ");		return;	}	printf("%c ", root->data);// 打印節(jié)點(diǎn)	BinaryTreePrevOrder(root->left);//遞歸到左子樹(shù)	BinaryTreePrevOrder(root->right);//遞歸到右子樹(shù)}

?2.中序遍歷

中序遍歷的順序?yàn)?左子樹(shù)??根? ?右? ? 顧名思義就是先訪問(wèn)左節(jié)點(diǎn)再訪問(wèn)根節(jié)點(diǎn)最后訪問(wèn)右節(jié)點(diǎn)。

按照中序遍歷，則上圖的遍歷順序?yàn)椋?/span>NULL D NULL B NULL A? NULL E NULL C NULL F NULL

// 二叉樹(shù)中序遍歷void BinaryTreeInOrder(BTNode* root){	if (root == NULL) //等于NULL就直接返回	{		printf("NULL ");		return;	}	BinaryTreePrevOrder(root->left);//遞歸到左子樹(shù)	printf("%c ", root->data);//打印節(jié)點(diǎn)	BinaryTreePrevOrder(root->right);//遞歸到右子樹(shù)}

?3.后序遍歷

后序遍歷的順序?yàn)?左子樹(shù)? ?右子樹(shù)? ?根? 顧名思義就是先訪問(wèn)左節(jié)點(diǎn)，再訪問(wèn)右節(jié)點(diǎn)，最后訪問(wèn)根。

按照后序遍歷，則上圖的遍歷順序?yàn)椋?/span>NULL NULL D NULL B NULL NULL E NULL NULL F C A

// 二叉樹(shù)后序遍歷void BinaryTreePostOrder(BTNode* root){	if (root == NULL)//等于NULL直接返回	{		printf("NULL ");		return;	}	BinaryTreePostOrder(root->left);//遞歸到左子樹(shù)	BinaryTreePostOrder(root->right);//遞歸到右子樹(shù)	printf("%c ", root->data);//打印節(jié)點(diǎn)	}

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

求二叉樹(shù)節(jié)點(diǎn)的個(gè)數(shù)與上述遍歷類(lèi)似，都是通過(guò)遞歸函數(shù)來(lái)實(shí)現(xiàn)。一顆二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)主要以三個(gè)部分構(gòu)成：根節(jié)點(diǎn)+左子樹(shù)的節(jié)點(diǎn)個(gè)數(shù)+右子樹(shù)的節(jié)點(diǎn)個(gè)數(shù)。知道這個(gè)公式我們就可以實(shí)現(xiàn)代碼

// 二叉樹(shù)節(jié)點(diǎn)個(gè)數(shù)int BinaryTreeSize(BTNode* root){	if (root == NULL)//如果為空返回零	{		return 0;	}	return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;}

?

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

葉子節(jié)點(diǎn)的左右子樹(shù)都為空，知道這個(gè)，我們只需稍微改動(dòng)上述代碼即可

// 二叉樹(shù)葉子節(jié)點(diǎn)個(gè)數(shù)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);}

?二叉樹(shù)第K層節(jié)點(diǎn)個(gè)數(shù)

如果指定一顆二叉樹(shù)，求它第K層節(jié)點(diǎn)個(gè)數(shù)，也可以采用遞歸的思想，當(dāng)給定的K為零的時(shí)候此時(shí)就是求根節(jié)點(diǎn)的個(gè)數(shù)，顯而易見(jiàn)就是返回1；而K不為零時(shí)，我們可以求root左右子樹(shù)K-1層的節(jié)點(diǎn)數(shù)之和。

// 二叉樹(shù)第k層節(jié)點(diǎn)個(gè)數(shù)int BinaryTreeLevelKSize(BTNode* root, int k){	if (root == NULL)	{		return 0;	}	if (k == 1)	{		return 1;	}	return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);}

?二叉樹(shù)的高度/深度

二叉樹(shù)的高度就是指二叉樹(shù)節(jié)點(diǎn)層次的最大值，也就是左右子樹(shù)最大高度+1.

//二叉樹(shù)深度/高度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;}

?二叉樹(shù)查找值為x的節(jié)點(diǎn)

// 二叉樹(shù)查找值為x的節(jié)點(diǎn)BTNode* BinaryTreeFind(BTNode* root, BTDataType x){	if (root == NULL)  //根為空，直接返回NULL	{		return NULL;	}	if (root->data == x)//找到了 直接返回節(jié)點(diǎn)	{		return root;	}	BTNode* leftRet = BinaryTreeFind(root->left, x); 	if (leftRet)	{		return leftRet; //如果再左子樹(shù)找到，直接返回，無(wú)需遞歸到右子樹(shù)	}	BTNode* rightRet = BinaryTreeFind(root->right, x);	if (rightRet)	{		return rightRet; 	}	return NULL;  //如果都沒(méi)找到，就直接返回NULL}

整體代碼

#pragma once#include#include#includetypedef char BTDataType;typedef struct BinaryTreeNode{	BTDataType data;	struct BinaryTreeNode* left;	struct BinaryTreeNode* right;}BTNode;BTNode* CreatTreeNode(BTDataType x);// 二叉樹(shù)節(jié)點(diǎn)個(gè)數(shù)int BinaryTreeSize(BTNode* root);// 二叉樹(shù)葉子節(jié)點(diǎn)個(gè)數(shù)int BinaryTreeLeafSize(BTNode* root);// 二叉樹(shù)第k層節(jié)點(diǎn)個(gè)數(shù)int BinaryTreeLevelKSize(BTNode* root, int k);// 二叉樹(shù)查找值為x的節(jié)點(diǎn)BTNode* BinaryTreeFind(BTNode* root, BTDataType x);// 二叉樹(shù)前序遍歷 void BinaryTreePrevOrder(BTNode* root);// 二叉樹(shù)中序遍歷void BinaryTreeInOrder(BTNode* root);// 二叉樹(shù)后序遍歷void BinaryTreePostOrder(BTNode* root);//二叉樹(shù)深度/高度int BinaryTreeDepth(BTNode* root);#include"BinarryTree.h"BTNode* CreatTreeNode(BTDataType x){	BTNode* node = (BTNode*)malloc(sizeof(BTDataType));	assert(node);	node->data = x;	node->right = NULL;	node->left = NULL;	return node;}// 二叉樹(shù)前序遍歷 void BinaryTreePrevOrder(BTNode* root){	if (root == NULL)	{		printf("NULL ");		return ;	}	printf("%c ", root->data);	BinaryTreePrevOrder(root->left);	BinaryTreePrevOrder(root->right);}// 二叉樹(shù)中序遍歷void BinaryTreeInOrder(BTNode* root){	if (root == NULL)	{		printf("NULL ");		return ;	}	BinaryTreePrevOrder(root->left);	printf("%c ", root->data);	BinaryTreePrevOrder(root->right);}// 二叉樹(shù)后序遍歷void BinaryTreePostOrder(BTNode* root){	if (root == NULL)	{		printf("NULL ");		return ;	}	BinaryTreePostOrder(root->left);	BinaryTreePostOrder(root->right);	printf("%c ", root->data);}// 二叉樹(shù)節(jié)點(diǎn)個(gè)數(shù)int BinaryTreeSize(BTNode* root){	if (root == NULL)	{		return 0;	}	return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;}// 二叉樹(shù)葉子節(jié)點(diǎn)個(gè)數(shù)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);}// 二叉樹(shù)第k層節(jié)點(diǎn)個(gè)數(shù)int BinaryTreeLevelKSize(BTNode* root, int k){	if (root == NULL)	{		return 0;	}	if (k == 1)	{		return 1;	}	return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);}// 二叉樹(shù)查找值為x的節(jié)點(diǎn)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;}// 二叉樹(shù)銷(xiāo)毀void BinaryTreeDestory(BTNode** root){	if (*root)	{		BinaryTreeDestory(&(*root)->left);		BinaryTreeDestory(&(*root)->right);		free(*root);		*root = NULL;	}}//二叉樹(shù)深度/高度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;}#include"BinarryTree.h"int main(){	BTNode* A = CreatTreeNode("A");	BTNode* B = CreatTreeNode("B");	BTNode* C = CreatTreeNode("C");	BTNode* D = CreatTreeNode("D");	BTNode* E = CreatTreeNode("E");	BTNode* F = CreatTreeNode("F");	A->left = B;	A->right = C;	B->left = D;	C->left = E;	C->right = F;	return 0;}