前言

二叉樹不同于順序表，一顆普通的二叉樹是沒有增刪改查的意義。普通的二叉樹用來存儲數據是不方便的。但是二叉樹的一些基本實現結構，例如前序遍歷，中序遍歷。。。等等都是對我們學習更深層次的二叉樹打下夯實的基礎。

?二叉樹節點聲明

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

二叉樹的遍歷

二叉樹的遍歷，是學習二叉樹結構的重要部分。二叉樹的遍歷主要分為三種：1.前序遍歷? ?2.中序遍歷 3.后序遍歷。首先我們要知道一顆二叉樹分為根，左子樹，右子樹。而三種遍歷方式也是圍繞著根來實現的。?

?

構建二叉樹

我們按上圖來構建一顆二叉樹

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.前序遍歷

前序遍歷的順序為 根 左子樹 右子樹 顧名思義就是先訪問根節點再訪問左節點最后訪問右節點。

按照前序遍歷，則上圖的遍歷順序為：A B D NULL NULL NULL C E NULL NULL F NULL NULL

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

?2.中序遍歷

中序遍歷的順序為 左子樹??根? ?右? ? 顧名思義就是先訪問左節點再訪問根節點最后訪問右節點。

按照中序遍歷，則上圖的遍歷順序為：NULL D NULL B NULL A? NULL E NULL C NULL F NULL

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

?3.后序遍歷

后序遍歷的順序為 左子樹? ?右子樹? ?根? 顧名思義就是先訪問左節點，再訪問右節點，最后訪問根。

按照后序遍歷，則上圖的遍歷順序為：NULL NULL D NULL B NULL NULL E NULL NULL F C A

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

二叉樹節點的個數

求二叉樹節點的個數與上述遍歷類似，都是通過遞歸函數來實現。一顆二叉樹的節點個數主要以三個部分構成：根節點+左子樹的節點個數+右子樹的節點個數。知道這個公式我們就可以實現代碼

// 二叉樹節點個數int BinaryTreeSize(BTNode* root){	if (root == NULL)//如果為空返回零	{		return 0;	}	return BinaryTreeSize(root->left) + BinaryTreeSize(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不為零時，我們可以求root左右子樹K-1層的節點數之和。

// 二叉樹第k層節點個數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);}

?二叉樹的高度/深度

二叉樹的高度就是指二叉樹節點層次的最大值，也就是左右子樹最大高度+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;}

?二叉樹查找值為x的節點

// 二叉樹查找值為x的節點BTNode* BinaryTreeFind(BTNode* root, BTDataType x){	if (root == NULL)  //根為空，直接返回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;  //如果都沒找到，就直接返回NULL}

整體代碼

#pragma once#include#include#includetypedef char BTDataType;typedef struct BinaryTreeNode{	BTDataType data;	struct BinaryTreeNode* left;	struct BinaryTreeNode* right;}BTNode;BTNode* CreatTreeNode(BTDataType x);// 二叉樹節點個數int BinaryTreeSize(BTNode* root);// 二叉樹葉子節點個數int BinaryTreeLeafSize(BTNode* root);// 二叉樹第k層節點個數int BinaryTreeLevelKSize(BTNode* root, int k);// 二叉樹查找值為x的節點BTNode* BinaryTreeFind(BTNode* root, BTDataType x);// 二叉樹前序遍歷 void BinaryTreePrevOrder(BTNode* root);// 二叉樹中序遍歷void BinaryTreeInOrder(BTNode* root);// 二叉樹后序遍歷void BinaryTreePostOrder(BTNode* root);//二叉樹深度/高度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;}// 二叉樹前序遍歷 void BinaryTreePrevOrder(BTNode* root){	if (root == NULL)	{		printf("NULL ");		return ;	}	printf("%c ", root->data);	BinaryTreePrevOrder(root->left);	BinaryTreePrevOrder(root->right);}// 二叉樹中序遍歷void BinaryTreeInOrder(BTNode* root){	if (root == NULL)	{		printf("NULL ");		return ;	}	BinaryTreePrevOrder(root->left);	printf("%c ", root->data);	BinaryTreePrevOrder(root->right);}// 二叉樹后序遍歷void BinaryTreePostOrder(BTNode* root){	if (root == NULL)	{		printf("NULL ");		return ;	}	BinaryTreePostOrder(root->left);	BinaryTreePostOrder(root->right);	printf("%c ", root->data);}// 二叉樹節點個數int BinaryTreeSize(BTNode* root){	if (root == NULL)	{		return 0;	}	return BinaryTreeSize(root->left) + BinaryTreeSize(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層節點個數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);}// 二叉樹查找值為x的節點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;}// 二叉樹銷毀void BinaryTreeDestory(BTNode** root){	if (*root)	{		BinaryTreeDestory(&(*root)->left);		BinaryTreeDestory(&(*root)->right);		free(*root);		*root = NULL;	}}//二叉樹深度/高度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;}