公众号 网站开发,网站首页菜单栏,iis .net 网站架设,全面的郑州网站建设文章目录 前言#x1f31f;一、二叉树链式结构的实现#x1f30f;1.1 二叉树叶子节点个数#x1f4ab;代码#xff1a;#x1f4ab;流程图#xff1a; #x1f30f;1.2 二叉树的高度#x1f4ab;第一种写法(不支持)#xff1a;#x1f4d2;代码#xff1a;#x1f… 文章目录 前言一、二叉树链式结构的实现1.1 二叉树叶子节点个数代码流程图 1.2 二叉树的高度第一种写法(不支持)代码流程图 第二种写法代码流程图 1.3 二叉树第K层的节点个数代码流程图 1.4 二叉树查找值为x的节点第一种写法(错误示范)代码流程图 第二种写法(正确写法)代码流程图 1.5 层序遍历代码思路流程(多种嵌套) 1.6 二叉树销毁(采用后序)代码流程图 1.7 判断二叉树是否是完全二叉树代码思路流程 二、二叉树链式结构完整代码总结 前言 个人主页小沈熬夜秃头中୧⍤⃝❅ 小编介绍欢迎来到我的乱七八糟小星球 专栏数据结构 本章内容手撕链式二叉树 送给各位成为更好的自己才是应该做的事 记得 评论 点赞 收藏 关注哦~ 提示以下是本篇文章正文内容下面案例可供参考
一、二叉树链式结构的实现
1.1 二叉树叶子节点个数
代码
int BTreeLeafSize(BTNode* root)
{if (root NULL)return 0;if (root-left NULL root-right NULL)return 1;return BTreeLeafSize(root-left) BTreeLeafSize(root-right);
}流程图 1.2 二叉树的高度
第一种写法(不支持)
代码
int BTreeHeight(BTNode* root)
{if (root NULL)return 0;return BTreeHeight(root-left) BTreeHeight(root-right) ?BTreeHeight(root-left) 1 : BTreeHeight(root-right) 1;
}流程图 由图可知每次比较完后并没有记录数据而是再次调用当树跃高底层最大的那个函数调用的次数就越多所以这种方法虽然对但是耗时太长而底层也就变成了所谓的天选打工人 第二种写法
代码
int BTreeHeight(BTNode* root)
{if (root NULL)return 0;int leftHeight BTreeHeight(root-left);int rightHeight BTreeHeight(root-right );return leftHeight rightHeight ? leftHeight 1 : rightHeight 1;
}流程图 每次调用都记录上数据这样比较完直接返回大的那个1 1.3 二叉树第K层的节点个数
代码
int BTreeLevelKSize(BTNode* root,int k)
{if (root NULL)return 0;if (k 1)return 1;return BTreeLevelKSize(root-left, k - 1) BTreeLevelKSize(root-right, k - 1);
}流程图 1.4 二叉树查找值为x的节点
第一种写法(错误示范)
代码
BTNode* BTreeFind(BTNode* root, BTDataType x)
{if (root NULL)return NULL;if (root-data x)return root;BTreeFind(root-left, x);BTreeFind(root-right, x);
}流程图 第二种写法(正确写法)
代码
BTNode* BTreeFind(BTNode* root, BTDataType x)
{if (root NULL)return NULL;if (root-data x)return root;BTNode* ret1 BTreeFind(root-left, x);if (ret1)return ret1;BTNode* ret2 BTreeFind(root-left, x);if (ret2)return ret2;return NULL;
}流程图 1.5 层序遍历
代码
void LevelOrder(BTNode* root)
{Queue q;QueueInit(q);if (root)QueuePush(q, root);while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);printf(%d , front-data);if (front-left)QueuePush(q, front-left);if (front-right)QueuePush(q, front-right);}printf(\n);QueueDestroy(q);
}思路流程(多种嵌套) 对于层序遍历,可以采用队列的思想(先进先出) 具体核心思想上一层出时带下一层进队列所以进入时不能存储树节点的值而是存储树节点指针 1.6 二叉树销毁(采用后序)
代码
void BTreeDestroy(BTNode* root)
{if (root NULL)return;BTreeDestroy(root-left);BTreeDestroy(root-right);free(root);
}流程图 1.7 判断二叉树是否是完全二叉树
代码
bool BTreeComplete(BTNode* root)
{Queue q;QueueInit(q);if (root)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 ! NULL)//往外拿数出现非空就不是完全二叉树{return false;QueueDestroy(q);}}return true;QueueDestroy(q);
}思路流程 和上述层序遍历一样采用队列思想上一层出时带下一层进入出现NULL时跳出然后将里面的数字往外拿出现非空不是完全二叉树N代表空 二、二叉树链式结构完整代码
//Queue.h
#pragma once
#includeassert.h
#includestdbool.h
#includestdlib.htypedef struct BinaryTreeNode* 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 QueueDestroy(Queue* pq);
//尾插(入队)
void QueuePush(Queue* pq, QDataType x);
//头删(出队)
void QueuePop(Queue* pq);
//队头数据
QDataType QueueFront(Queue* pq);
//队尾数据
QDataType QueueBack(Queue* pq);
//数据个数
int QueueSize(Queue* pq);
//判空
bool QueueEmpty(Queue* pq);//Queue.c
#includeQueue.h
void QueueInit(Queue* pq)
{assert(pq);pq-phead NULL;pq-ptail NULL;pq-size 0;
}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;
}void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail\n);return;}newnode-data x;newnode-next NULL;if (pq-ptail NULL){assert(pq-phead NULL);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 NULL;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;
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq-size 0;/*return pq-phead NULL pq-ptail NULL;*/return pq-size 0;
}//Test.c
#includestdlib.h
#includestdio.h
#includeassert.h
#includeQueue.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 fail);return NULL;}node-data x;node-left NULL;node-right NULL;return node;
}
BTNode* CreatBinaryTree()
{BTNode* node1 BuyNode(1);BTNode* node2 BuyNode(2);BTNode* node3 BuyNode(3);BTNode* node4 BuyNode(4);BTNode* node5 BuyNode(5);BTNode* node6 BuyNode(6);BTNode* node7 BuyNode(7);node1-left node2;node1-right node4;node2-left node3;node4-left node5;node4-right node6;node5-left node7;return node1;
}void PrevOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}printf(%d , root-data);PrevOrder(root-left);PrevOrder(root-right);
}void InOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}InOrder(root-left);printf(%d , root-data);InOrder(root-right);
}void PostOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}PostOrder(root-left);PostOrder(root-right);printf(%d , root-data);
}//二叉树节点个数 --- 遍历计数
//int size 0;
//void BTreeSzie(BTNode* root)
//{
// if (root NULL)
// {
// return size;
// }
// size;
// BTreeSzie(root-left);
// BTreeSzie(root-right);
// return size;
//}//int BTreeSzie(BTNode* root)
//{
// static int size 0;
// //printf(%p,%d\n, size,size);
// if (root NULL)
// {
// return size;
// }
// size;
// BTreeSzie(root-left );
// BTreeSzie(root-right );
// return size;
//}int BTreeSzie(BTNode* root)
{return root NULL ? 0 :BTreeSzie(root-left) BTreeSzie(root-right) 1;
}//二叉树叶子节点个数
int BTreeLeafSize(BTNode* root)
{if (root NULL)return 0;if (root-left NULL root-right NULL)return 1;return BTreeLeafSize(root-left) BTreeLeafSize(root-right);
}//二叉树树的高度
int BTreeHeight(BTNode* root)
{if (root NULL)return 0;int leftHeight BTreeHeight(root-left);int rightHeight BTreeHeight(root-right);return leftHeight rightHeight ? leftHeight 1 : rightHeight 1;
}//二叉树第k层的节点个数
int BTreeLevelKSize(BTNode* root, int k)
{assert(k 1);if (root NULL)return 0;if (k 1)return 1;return BTreeLevelKSize(root-left, k - 1) BTreeLevelKSize(root-right, k - 1);
}//二叉树查找值为x的节点
BTNode* BTreeFind(BTNode* root, BTDataType x)
{if (root NULL)return NULL;if (root-data x)return root;/*BTNode* ret1 BTreeFind(root-left, x);if (ret1)return ret1;BTNode* ret2 BTreeFind(root-left, x);if (ret2)return ret2;return NULL;*///BTreeFind(root-left, x);//BTreeFind(root-right, x);//return NULL;BTNode* ret1 BTreeFind(root-left, x);if (ret1)return ret1;return BTreeFind(root-left, x);
}//层序遍历---用队列
void LevelOrder(BTNode* root)
{Queue q;QueueInit(q);if (root)QueuePush(q, root);while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);printf(%d , front-data);if (front-left)QueuePush(q, front-left);if (front-right)QueuePush(q, front-right);}printf(\n);QueueDestroy(q);
}void BTreeDestroy(BTNode* root)
{if (root NULL)return;BTreeDestroy(root-left);BTreeDestroy(root-right);free(root);
}//判断二叉树是否是完全二叉树
bool BTreeComplete(BTNode* root)
{Queue q;QueueInit(q);if (root)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 ! NULL){return false;QueueDestroy(q);}}return true;QueueDestroy(q);
}int main()
{BTNode* root CreatBinaryTree();PrevOrder(root);printf(\n);InOrder(root);printf(\n);PostOrder(root);printf(\n);//printf(BTreeSize:%d\n, BTreeSzie(root));//printf(BTreeSize:%d\n, BTreeSzie(root));//printf(BTreeSize:%d\n, BTreeSzie(root));/*BTreeSzie(root);printf(BTreeSize:%d\n, size);size 0;BTreeSzie(root);printf(BTreeSize:%d\n, size);size 0;BTreeSzie(root);printf(BTreeSize:%d\n, size);*/printf(BTreeSize:%d\n, BTreeSzie(root));printf(BTreeLeafSize: % d\n, BTreeLeafSize(root));printf(BTreeHeight: % d\n, BTreeHeight(root));printf(BTreeLevelKSize: % d\n, BTreeLevelKSize(root, 3));printf(BTreeLevelKSize: % d\n, BTreeLevelKSize(root, 2));LevelOrder(root);printf(BTreeComplete: % d\n, BTreeComplete(root));BTreeDestroy(root);root NULL;return 0;
}总结 Ending,今天的链式二叉树的内容就到此结束啦~如果后续想了解更多就请关注我吧一键三连哦 ~
