目录

1. 二叉树的遍历

前序遍历

中序遍历

后序遍历

2. 计算二叉树中的节点个数

3. 计算二叉树中叶子节点个数

4. 计算二叉树的深度

5. 计算二叉树第k层节点个数

6. 二叉树基础练习

7. 二叉树的创建

8. 二叉树的销毁

9. 层序遍历

10. 判断二叉树是否为完全二叉树

---

1. 二叉树的遍历

二叉树遍历（traversal）是按照一定的次序访问二叉树中的所有节点，并且每个节点仅被访问一次的过程。它是二叉树最基本的运算，是二叉树中所有其他运算实现的基础。

1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。
3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

前序遍历递归图解：

代码实现

前序遍历

//前序遍历
void PrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("空 ");
		return;
	}
	printf("%d ", root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}

中序遍历

//中序遍历
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("空 ");
		return;
	}	
	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

后序遍历

//后序遍历
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("空 ");
		return;
	}
	PostOrder(root->left);	
	PostOrder(root->right);
	printf("%d ", root->data);
}

以中序遍历为例，递归展开图： 

代码实现： 

#include<stdio.h>
#include<stdlib.h>
typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;//数据元素
	struct BinaryTreeNode* left;//指向左孩子
	struct BinaryTreeNode* right;//指向右孩子
}BTNode;

BTNode* BuyNodee(int x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	node->data = x;
	node->left = NULL;
	node->right = NULL;

	return node;
}

//创建二叉树
BTNode* CreateBinaryTree()
{
	BTNode* node1 = BuyNodee(1);
	BTNode* node2 = BuyNodee(2);
	BTNode* node3 = BuyNodee(3);
	BTNode* node4 = BuyNodee(4);
	BTNode* node5 = BuyNodee(5);
	BTNode* node6 = BuyNodee(6);
	BTNode* node7 = BuyNodee(7);

	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;

	return node1;
}

//前序遍历
void PrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("空 ");
		return;
	}
	printf("%d ", root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}

//中序遍历
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("空 ");
		return;
	}	
	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

//后序遍历
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("空 ");
		return;
	}
	PostOrder(root->left);	
	PostOrder(root->right);
	printf("%d ", root->data);
}

int main()
{
	BTNode* root = CreateBinaryTree();
	//前序遍历
	PrevOrder(root);
	printf("\n");
	//中序遍历
	InOrder(root);
	printf("\n");
	//后序遍历
	PostOrder(root);
	printf("\n");

	return 0;
}

运行结果：

2. 计算二叉树中的节点个数

递归思想：

如果二叉树为空，节点个数为0。

如果二叉树不为空，二叉树节点个数=左子树节点个数 + 右子树节点个数 +1

代码实现：

//节点个数
int TreeSize(BTNode* root)
{
	return root == NULL ? 0 :
		TreeSize(root->left) + TreeSize(root->right) + 1;
}

3. 计算二叉树中叶子节点个数

递归思想：

如果二叉树为空，返回0。

如果二叉树不为空，左右子树为空，返回1。

如果二叉树不为空，且左右子树不为空，返回左子树中叶子节点个数加上右子树中叶子节点个数。

代码实现： 

//叶子节点个数
int TreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	if (root->left ==NULL && root->right == NULL)
		return 1;
	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

4. 计算二叉树的深度

递归思想：

如果二叉树为空，二叉树的深度为0。

如果二叉树不为空，二叉树的深度 = max(左子树深度，右子树深度)+1。 

代码实现： 

//二叉树的深度
int TreeHeight(BTNode* root)
{
	if (root == NULL)
		return 0;
	int height1 = TreeHeight(root->left);
	int height2 = TreeHeight(root->right);
	return height1 > height2 ? height1+1 : height2+1;
}

5. 计算二叉树第k层节点个数

递归思想：

如果二叉树为空，返回0。

如果二叉树不为空且k=1，返回1。

如果二叉树不为空且k>1,返回左子树中k-1层节点个数加右子树中k-1层节点个数。

代码实现：

//计算二叉树第k层节点个数
int TreeLevelKSize(BTNode* root,int k)
{
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	return TreeLevelKSize(root->left, k - 1)
	   + TreeLevelKSize(root->right, k - 1);
}

 在栈中大致过程

6. 二叉树基础练习

题目1 单植二叉树【链接】

题目2 相同的树【链接】

题目3 对称二叉树【链接】

题目4 二叉树的前序遍历【链接】

题目5 二叉树的中序遍历【链接】

题目6 二叉树的后序遍历【链接】

题目7 另一棵树的子树【链接】

7. 二叉树的创建

二叉树的构建及遍历【链接】

代码实现 ：

#include <stdio.h>
typedef struct BinaryTreeNode
{
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
    char val;
}BTNode;

BTNode* CreateTree(char*a,char*pi)
{
    if(a[(*pi)]=='#')
    {
        (*pi)++;
        return NULL;
    }   

    BTNode* root=(BTNode*)malloc(sizeof(BTNode));
    root->val=a[(*pi)++];
    root->left=CreateTree(a,pi);
    root->right=CreateTree(a,pi);
        return root;
}

//中序遍历
void InOrder(BTNode* root)
{
	if (root == NULL)
	{		
		return;
	}	
	InOrder(root->left);
	printf("%c ", root->val);
	InOrder(root->right);
}

int main() 
{
   char a[100];
   scanf("%s",a);
   char i=0;
   BTNode* root=CreateTree(a,&i);
   InOrder(root);

    return 0;
}

8. 二叉树的销毁

代码实现：

//二叉树的销毁(后序遍历)
void TreeDestory(BTNode* root)
{
	if (root == NULL)
		return;
	TreeDestory(root->left);
	TreeDestory(root->right);
	free(root);
}

9. 层序遍历

从上到下，从左到右依次将每个数放入到队列中，然后按顺序依次打印就是想要的结果。
1、首先将二叉树的根节点push到队列中，判断队列不为NULL，就输出队头的元素。
2、判断节点是否有孩子，如果有就将孩子push到队列中。

代码实现：

由于要访问每个节点的左右孩子，所以队列的元素类型为节点的指针。Queue.h【链接】

#include"Queue.h"

//层序遍历
void TreeLevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		printf("%d ", front->data);

		if (front->left)
			QueuePush(&q, front->left);
		if (front->right)
			QueuePush(&q, front->right);
	}
	QueueDesTroy(&q);
}

10. 判断二叉树是否为完全二叉树

基本思想：

按照层序遍历，遇到空也进队列，出队列出到空时，就开始判断，后面是全空就是完全二叉树，后面有非空就不是完全二叉树。例：

//判断二叉树是否是完全二叉树
bool TreeComplete(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;
}