之前也是把堆部分的知识点梳理完毕(即二叉树链式顺序的实现):堆的应用:堆排序和TOP-K问题
那么讲完了二叉树链式结构的实现。今天就进入二叉树链式结构的实现:
我们先手动快速创建一棵简单的二叉树来先进入二叉树操作,等对二叉树递归和结构有了一定的熟练后我们反过头再来看二叉树真正的创建方式
这不是真正的创建方法,是自己手动构建
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<math.h>
typedef int BTDataType;
typedef struct BinaryTreeNode//节点
{
BTDataType data;//数据
struct BinaryTreeNode* left;//左孩子
struct BinaryTreeNode* right;//右孩子
}TreeNode;
TreeNode* BuyTreeNode(int x)//创建数据为x的节点
{
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
assert(node);
node->data = x;
node->left = NULL;
node->right = NULL;
return node;
}
TreeNode* CreateTree()//形成树(手动连接)
{
TreeNode* node1 = BuyTreeNode(1);
TreeNode* node2 = BuyTreeNode(2);
TreeNode* node3 = BuyTreeNode(3);
TreeNode* node4 = BuyTreeNode(4);
TreeNode* node5 = BuyTreeNode(5);
TreeNode* node6 = BuyTreeNode(6);//创建六个节点
node1->left = node2;
node1->right = node4;
node2->left = node3;
node4->left = node5;
node4->right = node6;//进行连接
return node1;
}
构建的二叉树如图:
递归实现的关键在于将问题分解为规模更小的子问题,然后通过函数的递归调用来解决子问题。在二叉树遍历中,递归的思想可以很自然地应用,因为遍历左子树和右子树本质上就是对规模更小的子树进行遍历
二叉树遍历(Traversal)是指按照一定规则,依次访问二叉树中的所有节点,每个节点只被访问一次 二叉树的遍历有:前序/中序/后序的递归结构遍历和层序遍历
先访问根节点,再访问左子树,最后访问右子树(根>左>右);每进入一个新节点(先访问自身) 按照此规则之前构建的二叉树访问结果:1 2 3 NULL NULL NULL 4 5 NULL NULL 6 NULL NULL
方便大家理解,我就把NULL也写上:
void PreTraversal(TreeNode* root)
{
if (root == NULL)
{
printf("NULL ");//正常是不需要的,这里是为了让大家看到NULL(看的全过程)
return;
}
// 访问根节点
printf("%d ", root->data);
// 遍历左子树
PreTraversal(root->left);
// 遍历右子树
PreTraversal(root->right);
}
int main()
{
TreeNode* root = CreateTree();//创建好树
PreTraversal(root);
return 0;
}
结果:
先访问左子树,再访问根节点,最后访问右子树(左>根>右);每进入一个新节点(先访问左子树) 按照此规则之前构建的二叉树访问结果:NULL 3 NULL 2 NULL 1 NULL 5 NULL 4 NULL 6 NULL
void InTraversal(TreeNode* root)
{
if (root == NULL)
{
printf("NULL ");//正常是不需要的,这里是为了让大家看到NULL(看的全过程)
return;
}
// 遍历左子树
InTraversal(root->left);
// 访问根节点
printf("%d ", root->data);
// 遍历右子树
InTraversal(root->right);
}
int main()
{
TreeNode* root = CreateTree();//创建好树
InTraversal(root);
return 0;
}
结果:
先访问左子树,再访问右子树,最后访问根节点(左>右>根);每进入一个新节点(先访问右子树) 按照此规则之前构建的二叉树访问结果:NULL NULL 3 NULL 2 NULL NULL 5 NULL NULL6 4 1
void PostTraversal(TreeNode* root)
{
if (root == NULL)
{
printf("NULL ");//正常是不需要的,这里是为了让大家看到NULL(看的全过程)
return;
}
// 遍历左子树
PostTraversal(root->left);
// 遍历右子树
PostTraversal(root->right);
// 访问根节点
printf("%d ", root->data);
}
int main()
{
TreeNode* root = CreateTree();//创建好树
PostTraversal(root);
return 0;
}
结果:
它从树的根节点开始,逐层向下遍历,按照从左到右的顺序访问每一层的节点 在 C 语言中,一般使用队列来实现层序遍历:
- **弹出队列的首节点,并访问该节点**
- **将该节点的左右子节点(如果存在)依次入队列;即弹出节点后把子节点入队列**
队列为空时,循环结束
void LevelOrder(TreeNode* root)
{
Queue q;//创建队列,队列节点里的data储存root的地址
QInit(&q);//初始化
QPush(&q, root);//根进去了
int LevelSize = 1;//要一层一层输出,来辅助
while (!QEmpty(&q))
{
while (LevelSize--)//LevelSize是几就循环几次,一开始是1,输出一个就换行了,再Push后再次更新,来输出下一行
{
TreeNode* first = QFront(&q);//先存下来
QPop(&q);//再pop掉第一个
printf("%c ", first->data);
if (first->left)//有左节点就push进来
{
QPush(&q, first->left);
}
if (first->right)//有右节点就push进来
{
QPush(&q, first->right);
}
}
printf("\n");
LevelSize = QSize(&q);
}
QDestroy(&q);
}
同样是递归
TreeSize(root->left) + TreeSize(root->right) + 1
int TreeSize(TreeNode* root)
{
if (root == NULL)
{
return 0;
}
return TreeSize(root->left) + TreeSize(root->right) + 1;
}
int main()
{
TreeNode* root = CreateTree();//创建好树
printf("%d\n", TreeSize(root));
return 0;
}
结果:
代码也可以这样写:
int TreeSize(TreeNode* root)
{
return root == NULL ? 0 :
TreeSize(root->left) + TreeSize(root->right) + 1;//利用三目运算符
}
root->left == NULL && root->right == NULL
**,则表示当前节点为叶子节点,返回 1**TreeLeafSize(root->left) + TreeLeafSize(root->right)
int TreeLeafSize(TreeNode* root)
{
if (root == NULL)//是NULL就返回0
{
return 0;
}
if (root->left == NULL && root->right == NULL)//是叶子就返回1
{
return 1;
}
return TreeLeafSize(root->left) + TreeLeafSize(root->right);
//不是叶子就返回左子树叶子与右子树叶子之和
}
int main()
{
TreeNode* root = CreateTree();//创建好树
//printf("%d\n", TreeSize(root));
printf("%d\n", TreeLeafSize(root));
return 0;
}
fmax(TreeHeight(root->left), TreeHeight(root->right)) + 1
int TreeHeight(TreeNode* root)
{
if (root == NULL)
return 0;
return fmax(TreeHeight(root->left), TreeHeight(root->right)) + 1;
}
int main()
{
TreeNode* root = CreateTree();//创建好树
//printf("%d\n", TreeSize(root));
//printf("%d\n", TreeLeafSize(root));
printf("%d\n", TreeHeight(root));
return 0;
}
TreeLevelNodes(root->left, k-1) + TreeLevelNodes(root->right, k-1)
int TreeLevelKSize(TreeNode* root, int k)
{
if (root == NULL)
return 0;
if (k == 1)
return 1;
return TreeLevelKSize(root->left, k - 1) + TreeLevelKSize(root->right, k - 1);
}
int main()
{
TreeNode* root = CreateTree();//创建好树
printf("%d\n", TreeLevelKSize(root,2));//求个第二层的
return 0;
}
root->data == x
**,就返回该节点地址(同时也作为递归终止的情况之一)递归停止的两种情况:要么找到了返回地址, 要么没找到返回NULL
TreeNode* TreeFind(TreeNode* root, BTDataType x)
{
if (root == NULL)
{
return NULL;
}
// 先看根节点
if (root->data == x)
{
return root;
}
// 看左子树
TreeNode* ret1= TreeFind(root->left, x);//递归停止的两种情况:要么找到了返回地址
// 要么没找到返回NULL
//当不是NULL时,说明找到了,就一路返回上去,得到结果
if (ret1 != NULL)
{
return ret1;
}
// 看右子树
TreeNode* ret2 = TreeFind(root->right, x);//如上
if (ret2 != NULL)
{
return ret2;
}
return NULL;
}
int main()
{
TreeNode* root = CreateTree();//创建好树
//printf("%d\n", TreeSize(root));
//printf("%d\n", TreeLeafSize(root));
//printf("%d\n", TreeHeight(root));
//printf("%d\n", TreeLevelKSize(root,2));//求个第二层的
printf("%p\n", TreeFind(root, 5));
return 0;
}
返回地址,说明找到了
通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树 先根据这个画出来(#为NULL就不画了):
TreeNode* CreateTreeTrue(char* arr, int* pi)
{
if (arr[*pi] == '#')
{
(*pi)++;//调到下一个字符
return NULL;
}
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
assert(root);
root->data = arr[*pi];//根创建且赋值好了
(*pi)++;
root->left=CreateTreeTrue(arr, pi);//创建左树
root->right=CreateTreeTrue(arr, pi);//创建右树
return root;
}
严格按照**
根
**>左子树
**>**右子树
**的顺序,每一个左子树又是作为一个根,有自己的左子树及右子树。所以以创建根的方法来创建左子树和右子树,直到遇到#来返回NULL进行终止**
销毁我们都使用后序销毁
void TreeDestory(TreeNode** root)
{
if (*root == NULL)
{
return;
}
TreeDestory((*root)->left);
TreeDestory((*root)->right);
free(*root);
*root = NULL;
}
因为最后要把root置空,传一级指针不行(没用,形参是临时拷贝),想要改变root本身就传入root的地址(即二级指针)
也是利用队列,pop出一个后把他的左右节点push进去,遇到NULL就出循环,再看此时队列里是否全是NULL,如果全是NULL那就是完全二叉树,只要还有节点,那就不是完全二叉树
int BinaryTreeComplete(TreeNode* root)
{
Queue q;
QInit(&q);
QPush(&q, root);//根进去了
int LevelSize = 1;
while (!QEmpty(&q))
{
TreeNode* first = QFront(&q);
QPop(&q);
if (first == NULL)
break;//通过这个出循环
QPush(&q, first->left);
QPush(&q, first->right);
}
// 已经遇到空节点,如果此时队列中后面的节点还有非空,就不是完全二叉树
while (!QEmpty(&q))
{
TreeNode* first = QFront(&q);
QPop(&q);
if (first != NULL)
{
QDestroy(&q);
return 0;
}
}
QDestroy(&q);
return 1;
}
终于啊,二叉树中较为基本的地方都已经梳理完毕了,相信在不久的将来,还会有二叉树的内容,大家敬请期待吧!!!