利用php做网站教程,深圳企业网站制作公司单位,集团网站群,外国设计网站代码位置#xff1a;test-c-2024: 对C语言习题代码的练习 (gitee.com)
一、前言#xff1a; 在现实中搜索二叉树为常用的二叉树之一#xff0c;今天我们就要通过链表来实现搜索二叉树。实现的操作有#xff1a;建二叉树、前序遍历、中序遍历、后序遍历、求树的节点个数、求… 代码位置test-c-2024: 对C语言习题代码的练习 (gitee.com)
一、前言 在现实中搜索二叉树为常用的二叉树之一今天我们就要通过链表来实现搜索二叉树。实现的操作有建二叉树、前序遍历、中序遍历、后序遍历、求树的节点个数、求树的高度、求k层节点个数、查找节点、层序遍历判断是否是完全二叉树二叉树的销毁。
二、代码实现
2.0-开辟空间函数及结构体 对于链表我们可以定义一个开辟空间的函数以便于后继的操作。对于结构体成员中我们需要包含节点值data和左右子树节点。
代码如下
#include stdio.h
#include assert.h
#include stdlib.h
#include Queue.htypedef 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(k1){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 * qBinaryTreeFind(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.htypedef 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.hvoid 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-tailNULL);pq-head pq-tailnewnode;}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语言的个人见解以及自我实现。若有大佬发现哪里有问题可以私信或评论指教一下我这个小萌新。非常感谢各位友友们的点赞关注收藏与支持我会更加努力的学习编程语言还望各位多多关照让我们一起进步吧
