政务网站建设工作的通知,长春seo经理,电子商务平台网站推广,苏州生活网在上堆中已经介绍了什么是二叉树#xff0c;所以这里直接写二叉树实现。
1、二叉树的构建
二叉树的构建第一步肯定是初始化#xff0c;也就是构建这棵树#xff0c;这里是利用前序遍历构建的#xff0c;因为这里是利用链表形式创建的二叉树#xff0c;所以这里就是和之前…在上堆中已经介绍了什么是二叉树所以这里直接写二叉树实现。
1、二叉树的构建
二叉树的构建第一步肯定是初始化也就是构建这棵树这里是利用前序遍历构建的因为这里是利用链表形式创建的二叉树所以这里就是和之前文章一样先是申请地址的函数紧接着就是递归去申请空间因为构建的树是字符型所以这里在#号停下构建并且递归返回销毁也是递归销毁因为左节点和右节点最后肯定为空所以可以直接判断这两个节点代码如下
//申请地址
BTNode* BuyNode(BTDataType* a)
{BTNode* newnode (BTNode*)malloc(sizeof(BTNode));if (newnode NULL){perror(malloc fail);return NULL;}newnode-data *a;newnode-left NULL;newnode-right NULL;return newnode;
}// 通过前序遍历的数组ABD##E#H##CF##G##构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a,int* pi)
{if (a[*pi] #){(*pi);return NULL;}BTNode* root BuyNode(a[*pi]);(*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);
} 2、二叉树的前序遍历
这个前序遍历就是按照根左节点右节点的形式去打印数据当判断到当前地址为空时也就是说这个节点到头了就可以直接返回接着递归了所以这种就是打印前序遍历的代码如下。
void BinaryTreePrevOrder(BTNode* root)
{if (root NULL){printf(N );return ;}printf(%c , root-data);BinaryTreePrevOrder(root-left); BinaryTreePrevOrder(root-right);
}
3、二叉树的中序遍历
这个和前序遍历没多大区别不同的就是打印位置变了如下代码就是先遍历左节点紧接着就是在左节点遍历完返回打印一直到根节点最后咋递归遍历右节点打印。
void BinaryTreeInOrder(BTNode* root)
{if (root NULL){printf(N );return;}BinaryTreeInOrder(root-left);printf(%c , root-data);BinaryTreeInOrder(root-right);
}
4、二叉树的后续遍历
后续遍历说白了就是先遍历左节点然后是右节点最后是根节点代码如下。
void BinaryTreePostOrder(BTNode* root)
{if (root NULL){printf(N );return;}BinaryTreePostOrder(root-left);BinaryTreePostOrder(root-right);printf(%c , root-data);
}
5、二叉树的层序遍历
这个就不是利用递归了他是利用队列的先进先出的特性进行遍历的就是根节点出队的时候带进左节点和右节点然后左节点出的时候带入左节点的左节点和右节点这样循环下去就可以遍历整个树代码如下队列代码文章末会附上。
void BinaryTreeLevelOrder(BTNode* root)
{Queue q;QueueInit(q);if (root)QueuePush(q, root);int levelSize 1;while (!QueueEmpty(q)){// 一层一层出while (levelSize--){BTNode* front QueueFront(q);QueuePop(q);printf(%c , front-data);if (front-left)QueuePush(q, front-left);if (front-right)QueuePush(q, front-right);}printf(\n);levelSize QueueSize(q);}printf(\n);QueueDestroy(q);
}
6、二叉树的一些小功能
如二叉树的节点个数这个就可以直接遍历到空节点然后返回的时候1就可以判断出来了。
二叉树的叶子节点个数这个也是遍历到最后一层但是他的返回就是只有为叶子时才返回1然后左右遍历相加就可以得出。
这个就是遍历左右两边在返回时计算自己这边多高然后谁高返回谁。
查找第k层的节点数这个就是递归的--k当k等于1时就到了这层然后去计算这层有几个节点数然后左右两边一加就可以得出。
查找某个值这里就是去遍历然后找到了这个值后记录这个值然后进行返回这个值的地址。
判断这个树是否是完全二叉树完全二叉树的概念在堆里面写了他就是利用层序遍历会带出后续节点的特性去判断当是完全二叉树时不会出现中间是空的情况。
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{if (root NULL)return 0;return BinaryTreeSize(root-left) BinaryTreeSize(root-right) 1;
}// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{if (rootNULL)return 0;if (root-left NULL root-right NULL){return 1;}return BinaryTreeLeafSize(root-left) BinaryTreeLeafSize(root-right);
}//二叉树高度
int BinaryTreeHigh(BTNode* root)
{if (root NULL){return 0;}int LeftHigh BinaryTreeHigh(root-left);int RightHigh BinaryTreeHigh(root-right);return LeftHigh RightHigh ? LeftHigh 1 : RightHigh 1;
}// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{assert(k 0);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* ret1BinaryTreeFind(root-left,x);if (ret1)return ret1;BTNode* ret2BinaryTreeFind(root-right,x);if (ret2)return ret2;return NULL;
}// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(q);if (root)QueuePush(q, root);int levelSize 1;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;
}
7、测试代码、运行结果以及全部代码
这里测试是吧上文所有案例都带上了。
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include BT.h
#include QL.hint main()
{char arr[] { ABD##E#H##CF##G## };int pi 0;BTNode* root BinaryTreeCreate(arr, pi);BinaryTreePrevOrder(root);printf(\n);BinaryTreeInOrder(root);printf(\n);BinaryTreePostOrder(root);printf(\n);BinaryTreeLevelOrder(root);printf(\n);printf(%d\n, BinaryTreeSize(root));printf(%d\n, BinaryTreeLeafSize(root));printf(%d\n, BinaryTreeHigh(root));printf(%d\n, BinaryTreeLevelKSize(root,3));printf(%d\n, BinaryTreeLevelKSize(root,4));BTNode* root1 BinaryTreeFind(root, E);printf(%c\n,root1-data );printf(%d\n, BinaryTreeComplete(root));BinaryTreeDestory(root);root NULL;return 0;
}
BT.c
#define _CRT_SECURE_NO_WARNINGS 1
#include BT.h
#include QL.h//申请地址
BTNode* BuyNode(BTDataType* a)
{BTNode* newnode (BTNode*)malloc(sizeof(BTNode));if (newnode NULL){perror(malloc fail);return NULL;}newnode-data *a;newnode-left NULL;newnode-right NULL;return newnode;
}// 通过前序遍历的数组ABD##E#H##CF##G##构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a,int* pi)
{if (a[*pi] #){(*pi);return NULL;}BTNode* root BuyNode(a[*pi]);(*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);
}// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{if (root NULL)return 0;return BinaryTreeSize(root-left) BinaryTreeSize(root-right) 1;
}// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{if (rootNULL)return 0;if (root-left NULL root-right NULL){return 1;}return BinaryTreeLeafSize(root-left) BinaryTreeLeafSize(root-right);
}//二叉树高度
int BinaryTreeHigh(BTNode* root)
{if (root NULL){return 0;}int LeftHigh BinaryTreeHigh(root-left);int RightHigh BinaryTreeHigh(root-right);return LeftHigh RightHigh ? LeftHigh 1 : RightHigh 1;
}// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{assert(k 0);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* ret1BinaryTreeFind(root-left,x);if (ret1)return ret1;BTNode* ret2BinaryTreeFind(root-right,x);if (ret2)return ret2;return NULL;
}// 二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root)
{if (root NULL){printf(N );return ;}printf(%c , root-data);BinaryTreePrevOrder(root-left); BinaryTreePrevOrder(root-right);
}// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{if (root NULL){printf(N );return;}BinaryTreeInOrder(root-left);printf(%c , root-data);BinaryTreeInOrder(root-right);
}// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{if (root NULL){printf(N );return;}BinaryTreePostOrder(root-left);BinaryTreePostOrder(root-right);printf(%c , root-data);
}
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{Queue q;QueueInit(q);if (root)QueuePush(q, root);int levelSize 1;while (!QueueEmpty(q)){// 一层一层出while (levelSize--){BTNode* front QueueFront(q);QueuePop(q);printf(%c , front-data);if (front-left)QueuePush(q, front-left);if (front-right)QueuePush(q, front-right);}printf(\n);levelSize QueueSize(q);}printf(\n);QueueDestroy(q);
}// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(q);if (root)QueuePush(q, root);int levelSize 1;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;
}
BT.h
#pragma once
#include stdio.h
#include stdlib.h
#include stdbool.h
#include assert.h
#include string.h
typedef char BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;
//申请地址
BTNode* BuyNode(BTDataType* a);
// 通过前序遍历的数组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 BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root);
//二叉树的高度
int BinaryTreeHigh(BTNode* root);
QL.c
#define _CRT_SECURE_NO_WARNINGS 1
#include QL.h// 初始化队列
void QueueInit(Queue* pq)
{assert(pq);pq-phead NULL;pq-ptail NULL;pq-size 0;
}// 队尾入队列
void QueuePush(Queue* pq, QDataType data)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);return;}newnode-data data;newnode-next NULL;if (pq-ptail NULL){assert(pq-pheadNULL);pq-phead pq-ptail newnode;}else{pq-ptail-next newnode;pq-ptail newnode;}pq-size;
}// 队头出队列
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq-phead-next NULL){free(pq-phead);pq-phead pq-ptail NULL;}else{QNode* next pq-phead-next;free(pq-phead);pq-phead next;}pq-size--;
}// 获取队列头部元素
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-phead-data;
}// 获取队列队尾元素
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-ptail-data;
}// 获取队列中有效元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}// 检测队列是否为空如果为空返回非零结果如果非空返回0
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-size0;
}// 销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur pq-phead;while (cur){QNode* next cur-next;free(cur);cur next;}pq-phead pq-ptail NULL;pq-size 0;
}
QL.h
#pragma once
#include stdio.h
#include stdlib.h
#include assert.h
#include stdbool.h
typedef int QDataType;
// 链式结构表示队列
typedef struct QueueNode
{struct QueueNode* next;QDataType data;}QNode;// 队列的结构
typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;// 初始化队列
void QueueInit(Queue* pq);
// 队尾入队列
void QueuePush(Queue* pq, QDataType data);
// 队头出队列
void QueuePop(Queue* pq);
// 获取队列头部元素
QDataType QueueFront(Queue* pq);
// 获取队列队尾元素
QDataType QueueBack(Queue* pq);
// 获取队列中有效元素个数
int QueueSize(Queue* pq);
// 检测队列是否为空如果为空返回非零结果如果非空返回0
bool QueueEmpty(Queue* pq);
// 销毁队列
void QueueDestroy(Queue* pq);
