【数据结构】二叉树（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;
}