当前位置: 首页 > news >正文

二叉树的链式实现

目录

一、二叉树的基础操作

二、二叉树代码图解

2.1 遍历

2.2 求大小

2.3 创建与销毁

2.4 与队列结合解决问题

三、二叉树C语言源码汇总


二叉树的代码实现运用了函数递归的思想,了解函数递归的知识请见博主的另一篇博客:

http://t.csdnimg.cn/PoMtd

一、二叉树的基础操作

typedef int BTDataType;typedef struct BinaryTreeNode
{BTDataType data; // 当前结点值域	struct BinaryTreeNode* left; // 指向当前节点左孩子struct BinaryTreeNode* right; // 指向当前节点右孩子
}BTNode;//创建二叉树
BTNode* CreatBinaryTree();
//前序遍历
void PrevOrder(BTNode* root);
//中序遍历
void InOrder(BTNode* root);
//后序遍历
void PostOrder(BTNode* root);
//结点个数
int	TreeSize(BTNode* root);
//叶子结点个数
int TreeLeafSize(BTNode* root);
//二叉树高度
int TreeHeight(BTNode* root);
//二叉树第k层结点个数
int TreeLevelKSize(BTNode* root, int k);
//二叉树查找值为x的结点
BTNode* TreeFind(BTNode* root, int x);
// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* CreateTree(char* a, int* pi);
//二叉树的销毁
void BinaryTreeDestory(BTNode* root);
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root);
//层序遍历
void TreeLevelOrder(BTNode* root);

二、二叉树代码图解

2.1 遍历

详见博主的另一篇博客:http://t.csdnimg.cn/YnlIr

2.2 求大小

详见博主的另一篇博客:http://t.csdnimg.cn/Ce2Fs

2.3 创建与销毁

详见博主的另一篇博客:http://t.csdnimg.cn/LXt8P

2.4 与队列结合解决问题

详见博主的另一篇博客:http://t.csdnimg.cn/zbNis

三、二叉树C语言源码汇总

BTNode* BuyNode(int 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->right = node7;return node1;
}
//前序遍历
void PrevOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}printf("%d ", root->data);PrevOrder(root->left);PrevOrder(root->right);
}
//中序遍历
void InOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
}
//后序遍历
void PostOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);
}
//结点个数
int TreeSize(BTNode* root)
{if (root == NULL){return 0;}return TreeSize(root->left) + TreeSize(root->right) + 1;
}
//叶子结点个数
int TreeLeafSize(BTNode* root)
{if (root == NULL){return 0;}if (root->left == NULL && root->right == NULL){return 1;}return TreeLeafSize(root->left) + TreeLeafSize(root->right);}
//二叉树高度
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;
}
//求第K层的节点数目
int TreeLevelKSize(BTNode* root, int k)
{if (root == NULL){return 0;}if (k == 1){return 1;}return TreeLevelKSize(root->left, k - 1) + TreeLevelKSize(root->right, k - 1);
}
//查找值为x的节点
BTNode* TreeFind(BTNode* root, int x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode* ret1 = TreeFind(root->left, x);if (ret1){return ret1;}BTNode* ret2 = TreeFind(root->right, x);if (ret2){return ret2;}return NULL;
}
// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* CreateTree(char* a, int* pi)
{if (a[*pi] == '#'){(*pi)++;return NULL;}BTNode* root = (BTNode*)malloc(sizeof(BTNode));if (root == NULL){perror("malloc");exit(1);}root->data = a[(*pi)++];root->left = CreateTree(a, pi);root->right = CreateTree(a, pi);return root;
}
//二叉树的销毁
void BinaryTreeDestory(BTNode* root)
{//判空if (root == NULL){return NULL;}//释放左子树BinaryTreeDestory(root->left);//释放右子树BinaryTreeDestory(root->right);//释放本身结点free(root);
}
//层序遍历
void TreeLevelOrder(BTNode* root)
{Queue q;QueueInit(&q);if (root){QueuePush(&q, root);}while (QueueEmpty(&q)==false){BTNode* front = QueueFront(&q);QueuePop(&q);printf("%d ", front->data);if (front->left){QueuePush(&q, front->left);}if (front->right){QueuePush(&q, front->right);}}QueueDestroy(&q);
}
//判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);if (root != NULL){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;
}

http://www.lryc.cn/news/353205.html

相关文章:

  • STM32中断编程入门
  • 《我的阿勒泰》读后感
  • Android.mk简单介绍、规则与基本格式
  • 【MySQL精通之路】InnoDB(3)-MVCC多版本管理
  • uniapp 对接 微信App/支付宝App 支付
  • cmake配置opencv与boost库
  • 【Kotlin 一】Kotlin入门知识简介、变量声明、数字类型
  • Java 微信小程序登录(openId方式)
  • 为何程序员35岁就开始被嫌弃了?程序员该如何避免中年危机?
  • 【2024软考】史上最全!软考刷题+解析大合集(9万字全手工打,货真价实)
  • 【Spring Security + OAuth2】授权
  • 失落的方舟台服预下载教程 一键下载+账号注册教程
  • 【启明智显技术分享】SOM2D02-2GW核心板适配ALSA(适用Sigmastar ssd201/202D)
  • 人工智能的发展现状,AI将如何改变IT行业,哪些职业将最先失业
  • request.js使用Promise.all等待所有请求完成再进行数据赋值
  • Java开发者必知的时间处理工具:SimpleDateFormat类详解
  • 构造函数的用法
  • 环形链表Ⅱ-力扣
  • 【microros】解决 microros安装过程中的 undefined reference to `fmt::v6 问题
  • 29. 相似矩阵,若尔当型
  • 【论文阅读】 YOLOv10: Real-Time End-to-End Object Detection
  • Python读写文件
  • docker-如何将容器外的脚本放入容器内,将容器内的脚本放入容器外
  • 算法训练营第三十九天 | LeetCode 738 单调递增的数字、LeetCode 968 监控二叉树
  • Hive语法学习总结
  • 【Linux】TCP协议【中】{确认应答机制/超时重传机制/连接管理机制}
  • solidworks画螺母学习笔记
  • WebGL的医学培训软件开发
  • 新时代AI浪潮下,程序员和产品经理如何入局AIGC领域?
  • OWASP top10--SQL注入(一)