【数据结构】二叉树（2）
目录
1. 二叉树的遍历
前序遍历
中序遍历
后序遍历
2. 计算二叉树中的节点个数
3. 计算二叉树中叶子节点个数
4. 计算二叉树的深度
5. 计算二叉树第k层节点个数
6. 二叉树基础练习
7. 二叉树的创建
8. 二叉树的销毁
9. 层序遍历
10. 判断二叉树是否为完全二叉树
1. 二叉树的遍历
二叉树遍历（traversal）是按照一定的次序访问二叉树中的所有节点，并且每个节点仅被访问一次的过程。它是二叉树最基本的运算，是二叉树中所有其他运算实现的基础。
- 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
- 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。
- 后序遍历(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;
}