之前我们了解了树的性质,并简单介绍了一下二叉树,那么接下来我们就来更多地来学习一下二叉树。
在学习二叉树之前我们先来学习一下二叉树的遍历,但是遍历需要先创建一个二叉树,那么为了方便理解和学习,我们先来暴力创建一个二叉树,介绍完二叉树的遍历之后,我们就可以使用二叉树的遍历来创建二叉树。
当然我们要先一个二叉树结构,如下图:
1.二叉树的遍历
我们先来暴力创建一颗二叉树,就以下图所示创建:
由于这里我们使用数字来创建,所以不要忘记先将char修改为int。
其实简单点就是:
前序:根 左子树 右子树
中序:左子树 根 右子树
后序:左子树 右子树 根
(谁在前就先遍历谁)
1.1前序遍历
遍历顺序为:根 左子树 右子树
下图为递归图解:
所以递归代码为:
这里我们将空也打印出来(N代表NULL)
再来运行测试一下:
1.2中序遍历
遍历顺序为:左子树 根 右子树
和前序相同的逻辑,只不过中序先遍历左子树
运行测试:
1.3后序遍历
遍历顺序:左子树 右子树 根
也是一样的逻辑,我们直接看代码,就不分析了
运行测试:
2.二叉树的构建
了解完二叉树的遍历之后,我们就用前序遍历构建一棵二叉树。(#表示NULL)
注意:数组是不会越界的,因为最后创建右子树时,当读取到的元素为#时,说明为空,再++就变成了\0,后面就不会继续递归了,而是不断返回,不递归的话下标就不会继续++造成越界。
然后我们用前序遍历测试一下看看:
3.二叉树的销毁
销毁要使用后序遍历来销毁,因为使用前序和中序会造成左子树和右子树的地址丢失,从而造成空间泄露,当然解决办法也是有的,你需要先把左右子树的地址先存起来,所以还是后序遍历更好点
注意:我们这里使用二级指针,是为了修改实参,另外递归左子树和右子树时,千万不要忘记left和right是一级指针,要使用&符号。
4.二叉树节点的个数
同样可以用递归的思想,转化为左子树+右子树+根(也就是1)
运行测试:
5.二叉树叶子节点个数
首先要知道叶子节点要怎么判断,左子树和右子树都为空时才是叶子节点。
运行测试:
确实是四个叶子节点,没有问题。
6.二叉树第k层节点个数
我们可以分解成一个子问题,我们每遍历一层,第k层相对我们就是k-1层,于是我们就可以分别遍历左子树和右子树的第k层,然后相加。
运行测试:
7.二叉树查找值为x的节点
我们在递归左子树和右子树时,一定要先把返回值先存在变量里,这样的好处是,如果我们再左子树中找到值为x的节点时,就直接返回,不需要再去递归右子树,还有如果不保存的话,在返回到上一层函数时,因为没有保存,所以又需要再重复递归,这样的话就需要重复多次递归。
运行测试:
8.层序遍历
如图:
那么要如何实现层序遍历呢?其实我们可以用队列来实现,首先队列的特点是先进先出,利用这一特点,可以先把根节点入队列,然后出队列时,把它的左右子树分别也入到队列里面,用上图举例就是:A先入队列,A出队列时,把它的左右子树B和C也入到队列中,B出队列时,左子树D入队列,右子树为空,就不需要入,然后就是C出,EF入,以此类推。这样就能实现层序遍历。
首先,我们要将队列给实现,栈和队列的实现之前讲过,这里就不再赘述。
第一步,要先将Int修改为struct BinaryTreeNode*,因为我们入队列不能只将值给入到队列中,不然我们拿不到左右子树的值,那我们要将节点给入到队列中吗?其实没必要,我们可以将指向节点的指针入到队列中,通过指向节点的指针得到该节点的数据和左右子树的地址,这样每次入队列开辟的空间就会少很多。
只要不为空就入队列。如下图
注意:pop出队列,释放的空间是队列中存放指针(指向二叉树节点的指针)的空间,而不是释放二叉树节点,所以不会出现野指针的问题。
运行测试:
9.判断二叉树是否为完全二叉树
首先我们要知道什么是完全二叉树,之前有介绍过,就是一种特殊的满二叉树,如下图:
左边是完全二叉树,右边并不是,只有连续的才可以。
接下来要如何判断呢?我们也可以通过层序遍历来判断,这次我们将空树也入到队列中,只要出队列出到空时,队列中还有非空的,那么就不是完全二叉树,只有队列中全部为空才是完全二叉树。
举个例子,如图:
这次不管是否为空,都要入队列,出到空时就跳出循环,然后再判断队列中是否还有非空。
运行测试:
代码如下:
BinaryTree.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef char BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int* pi);
// 二叉树销毁
void BinaryTreeDestory(BTNode** root);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉树前序遍历
void PrevOrder(BTNode* root);
// 二叉树中序遍历
void InOrder(BTNode* root);
// 二叉树后序遍历
void PostOrder(BTNode* root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root);
BinaryTree.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "BinaryTree.h"
BTNode* BuyNode(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* Create()
{
BTNode* node1 = BuyNode(1);
BTNode* node2 = BuyNode(2);
BTNode* node3 = BuyNode(3);
BTNode* node4 = BuyNode(4);
BTNode* node5 = BuyNode(5);
BTNode* node6 = BuyNode(6);
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("%c ", root->data);
PrevOrder(root->left);
PrevOrder(root->right);
}
// 二叉树中序遍历
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
InOrder(root->left);
printf("%d ", root->data);
InOrder(root->right);
}
// 二叉树后序遍历
void PostOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->data);
}
// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int* pi)
{
if (a[*pi] == '#')
{
(*pi)++;
return NULL;
}
BTNode* root = (BTNode*)malloc(sizeof(BTNode));
if (root == NULL)
{
perror("malloc fail");
return NULL;
}
root->data = a[(*pi)++];
root->left = BinaryTreeCreate(a, pi);
root->right = BinaryTreeCreate(a, pi);
return root;
}
// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{
if (*root == NULL)
return;
BinaryTreeDestory(&(*root)->left);
BinaryTreeDestory(&(*root)->right);
free(*root);
*root = NULL;
}
// 二叉树节点个数
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* ret1 = BinaryTreeFind(root->left, x);
if (ret1)
return ret1;
BTNode* ret2 = BinaryTreeFind(root->right, x);
if (ret2)
return ret2;
return NULL;
}
#include "Queue.h"
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
Queue q;
QueueInit(&q);
if(root)
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
printf("%c ", front->data);
if (front->left)
QueuePush(&q, front->left);
if (front->right)
QueuePush(&q, front->right);
}
QueueDestroy(&q);
}
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
Queue q;
QueueInit(&q);
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)
{
QueueDestroy(&q);
return false;
}
}
QueueDestroy(&q);
return true;
}
void Test2()
{
char arr[] = { "ABD##E#H##CF##G##" };
int i = 0;
BTNode* root = BinaryTreeCreate(arr, &i);
PrevOrder(root);
printf("\n");
printf("二叉树节点个数:%d\n", BinaryTreeSize(root));
printf("叶子节点个数:%d\n", BinaryTreeLeafSize(root));
printf("第k层节点个数:%d\n", BinaryTreeLevelKSize(root, 3));
BTNode* node = BinaryTreeFind(root, 'E');
if (node != NULL)
printf("找到了\n");
printf("层序遍历:");
BinaryTreeLevelOrder(root);
if (BinaryTreeComplete(root))
printf("完全二叉树\n");
else
printf("非完全二叉树\n");
}
void Test1()
{
BTNode* root = Create();
PrevOrder(root);
printf("\n");
InOrder(root);
printf("\n");
PostOrder(root);
printf("\n");
}
int main()
{
//Test1();
Test2();
return 0;
}