数据结构—链式二叉树-C语言

        代码位置：test-c-2024: 对C语言习题代码的练习 (gitee.com)

一、前言：

        在现实中搜索二叉树为常用的二叉树之一，今天我们就要通过链表来实现搜索二叉树。实现的操作有：建二叉树、前序遍历、中序遍历、后序遍历、求树的节点个数、求树的高度、求k层节点个数、查找节点、层序遍历，判断是否是完全二叉树，二叉树的销毁。

二、代码实现：

2.0-开辟空间函数及结构体：

        对于链表我们可以定义一个开辟空间的函数以便于后继的操作。对于结构体成员中我们需要包含节点值data和左右子树节点。

代码如下：

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include "Queue.h"typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;BTNode* BuyNode(BTDataType x)		//开辟空间
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc node");return NULL;}node->data = x;node->left = NULL;node->right = NULL;return node;
}

2.1-建二叉树：

        对于建二叉树我们需要手动搓一个二叉树。

建的树如图所示：

代码如下：

BTNode* CreatTree()			//建二叉树
{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;
}

2.2-前序遍历：

        二叉树前序遍历规则为：先访问根节点在访问左子树最后访问右子树。我这里是通过函数递归实现的访问。

代码如下：

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

2.3-中序遍历：

        二叉树中序遍历规则为：先访问左子树在访问根节点最后访问右子树。我这里是通过函数递归实现的访问。

代码如下：

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

2.4-后序遍历：

        二叉树后序遍历规则为：先访问左子树在访问右子树最后访问根节点。我这里是通过函数递归实现的访问。

代码如下：

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

2.5-求树的节点个数：

        这里是通过三目操作符以及递归来实现的统计节点个数。原理是如果该节点不是空节点则整体个数加1，然后继续访问下一子树，直到遍历完为止。

代码如下：

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

2.6-求树的高度：

        这里是通过leftHeight和rightHeight来存储左右子树高度值，然后在return中通过三目运算符来返回高的那一子树在加1（这里加1是节点本身占一个高度）

代码如下：

int TreeHeight(BTNode* root)
{if (root == NULL)return 0;int leftHeight = TreeHeight(root->left);int rightHeight = TreeHeight(root->right);return leftHeight> rightHeight? leftHeight + 1: rightHeight + 1;
}

2.7-求k层节点个数：

        这里是通过递归传k-1是为了找到k层的所有节点若存在则返回1，不存在返回0然后将所有返回值相加返回即是第k层的节点个数。

代码如下：

int TreeLeave(BTNode* root,int k)		//求k层节点个数
{assert(k > 0);if (root == NULL){return 0;}if(k==1){return 1;}return TreeLeave(root->left, k - 1) +TreeLeave(root->right, k - 1);
}

2.8-查找节点：

        这里是通过递归遍历一遍树查找是否存在查找值若存在则返回该节点，若不存在则返回NULL。（注：这个函数只能查找出该值前序遍历第一次出现的位置）

代码如下：

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)		//查找
{if (root == NULL){return 0;}if (root->data == x){return root;}BTNode* p = BinaryTreeFind(root->left, x);if(p)return p;BTNode * q=BinaryTreeFind(root->right, x);if (q )return q;return NULL;
}

2.9-层序遍历：

        这里需要用到队列以前的博客里我们实现过队列，所以这里我们可以当个CV工程师将以前的代码复制过来即可。

队列代码：

#pragma once#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef struct BinaryTreeNode* QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;void QueueInit(Queue* pq);								//初始化
void QueueDestory(Queue* pq);							//释放销毁
void QueuePush(Queue* pq,QDataType x);		//入队	
void QueuePop(Queue* pq);								//出队
int QueueSize(Queue* pq);								//元素个数
bool QueueEmpty(Queue* pq);							//判断队空
QDataType QueueFront(Queue* pq);					//队头数据
QDataType QueueBack(Queue* pq);					//队尾数据

#define _CRT_SECURE_NO_WARNINGS 1#include "Queue.h"void QueueInit(Queue* pq)			    					//初始化
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}void QueueDestory(Queue* pq)     					//释放销毁
{assert(pq);QNode* cur =pq->head;while (cur){pq->head = cur->next;free(cur);cur = NULL;cur = pq->head;}pq->head = pq->tail = NULL;pq->size = 0;
}void QueuePush(Queue* pq, QDataType x)		//入队	
{QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc");return;}newnode->data = x;newnode->next = NULL;if (pq->head == NULL){assert(pq->tail==NULL);pq->head = pq->tail=newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}void QueuePop(Queue* pq)								//出队
{assert(pq);assert(!QueueEmpty(pq));QNode* del = pq->head;pq->head = pq->head->next;free(del);del = NULL;if (pq->head == NULL){pq->tail = NULL;}pq->size--;
}int QueueSize(Queue* pq)								//元素个数
{assert(pq);return pq->size;
}bool QueueEmpty(Queue* pq)							//判断队空
{assert(pq);return pq->size == 0;
}QDataType QueueFront(Queue* pq)					//队头数据
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}QDataType QueueBack(Queue* pq)					//队尾数据
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}

遍历代码如下：

void LevelOrder(BTNode* root)				//层序遍历
{Queue p;QueueInit(&p);if(root)QueuePush(&p, root);while (!QueueEmpty(&p)){BTNode* front = QueueFront(&p);		//取队列首元素的值QueuePop(&p);printf("%d ", front->data);if (front->left)			//入下一层元素{QueuePush(&p, front->left);}if (front->right){QueuePush(&p, front->right);}}QueueDestory(&p);
}

        层序遍历代码执行的过程如图所示：

2.10-判断是否是完全二叉树：

        判断完全二叉树是通过层序遍历和队列来实现。注意这里的层序遍历遇到空树也需要入队，为了判断二叉树是否为完全二叉树。原理：//层序遍历第一次遇到NULL时若后面没有数据节点则是完全二叉树，反之则不是

代码如下：

bool TreeComplete(BTNode* root)		//判断是否是完全二叉树
{Queue pq;QueueInit(&pq);QueuePush(&pq, root);while (!QueueEmpty(&pq)){BTNode* front = QueueFront(&pq);if (QueueFront(&pq) == NULL){break;}QueuePop(&pq);QueuePush(&pq, front->left);QueuePush(&pq, front->right);}//层序遍历第一次遇到NULL时若后面没有数据节点则是完全二叉树，反之则不是while (!QueueEmpty(&pq))				{if (QueueFront(&pq) != NULL){QueueDestory(&pq);return false;}QueuePop(&pq);}QueueDestory(&pq);return true;
}

2.11-二叉树的销毁：

        二叉树销毁需遍历一遍链表，这里采用后序遍历比较方便，因为另外两个遍历都会因为释放根节点后左右子节点不好释放而产生不必要的麻烦，所以这里最好是使用后序遍历。注意这里只是释放掉了空间，因为这里是一级指针所以这里置空属于局部变量不会影响外部，所以在主函数调用时我们需手动置空。

如图所示：

代码如下：

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

三、结语：

递归效果图展示：

最终效果图为：

        上述内容，即是我个人对数据结构-链式二叉树-搜索二叉树-C语言的个人见解以及自我实现。若有大佬发现哪里有问题可以私信或评论指教一下我这个小萌新。非常感谢各位友友们的点赞，关注，收藏与支持，我会更加努力的学习编程语言，还望各位多多关照，让我们一起进步吧！