能将平衡二叉树的C语言编程出来吗

时间: 2023-12-20 09:11:54 浏览: 40
当然可以,以下是基于C语言实现平衡二叉树的代码示例: ```c #include <stdio.h> #include <stdlib.h> // 定义平衡二叉树的结构体 typedef struct AVLNode { int key; int height; struct AVLNode *left; struct AVLNode *right; } AVLNode; // 获取节点高度 int getHeight(AVLNode *node) { if (node == NULL) { return 0; } return node->height; } // 获取节点平衡因子 int getBalanceFactor(AVLNode *node) { if (node == NULL) { return 0; } return getHeight(node->left) - getHeight(node->right); } // 更新节点高度 void updateHeight(AVLNode *node) { node->height = 1 + (getHeight(node->left) > getHeight(node->right) ? getHeight(node->left) : getHeight(node->right)); } // 左旋操作 AVLNode *leftRotate(AVLNode *node) { AVLNode *newRoot = node->right; node->right = newRoot->left; newRoot->left = node; updateHeight(node); updateHeight(newRoot); return newRoot; } // 右旋操作 AVLNode *rightRotate(AVLNode *node) { AVLNode *newRoot = node->left; node->left = newRoot->right; newRoot->right = node; updateHeight(node); updateHeight(newRoot); return newRoot; } // 平衡二叉树插入操作 AVLNode *insert(AVLNode *root, int key) { if (root == NULL) { // 创建新节点并返回 AVLNode *newNode = (AVLNode *)malloc(sizeof(AVLNode)); newNode->key = key; newNode->height = 1; newNode->left = NULL; newNode->right = NULL; return newNode; } if (key < root->key) { // 插入到左子树 root->left = insert(root->left, key); } else if (key > root->key) { // 插入到右子树 root->right = insert(root->right, key); } else { // 已存在该节点,不需要插入 return root; } // 更新节点高度 updateHeight(root); // 判断平衡因子,如果不平衡就进行旋转 int balanceFactor = getBalanceFactor(root); if (balanceFactor > 1 && key < root->left->key) { // LL型,进行右旋操作 return rightRotate(root); } else if (balanceFactor < -1 && key > root->right->key) { // RR型,进行左旋操作 return leftRotate(root); } else if (balanceFactor > 1 && key > root->left->key) { // LR型,先进行左旋再进行右旋 root->left = leftRotate(root->left); return rightRotate(root); } else if (balanceFactor < -1 && key < root->right->key) { // RL型,先进行右旋再进行左旋 root->right = rightRotate(root->right); return leftRotate(root); } return root; } // 中序遍历平衡二叉树 void inorderTraversal(AVLNode *root) { if (root == NULL) { return; } inorderTraversal(root->left); printf("%d ", root->key); inorderTraversal(root->right); } int main() { AVLNode *root = NULL; int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90}; int i; // 插入数据并构建平衡二叉树 for (i = 0; i < sizeof(arr) / sizeof(arr[0]); i++) { root = insert(root, arr[i]); } // 中序遍历平衡二叉树 inorderTraversal(root); return 0; } ``` 以上代码实现了平衡二叉树的插入操作和中序遍历操作,你可以根据需要进行修改和扩展。

相关推荐

最新推荐

recommend-type

C语言数据结构之平衡二叉树(AVL树)实现方法示例

主要介绍了C语言数据结构之平衡二叉树(AVL树)实现方法,结合实例形式分析了C语言平衡二叉树的相关定义与使用技巧,需要的朋友可以参考下
recommend-type

课设 - 平衡二叉树的演示 .docx

(1) 构建一个平衡二叉树并实现创建、插入、查找、删除、销毁等操作。每种操作均提示输入关键字。每次插入或删除一个结点后,更新平衡二叉树的显示。 (2) 平衡二叉树的显示采用凹入表现形式。 (3)输入的...
recommend-type

C语言中计算二叉树的宽度的两种方式

主要介绍了C语言中计算二叉树的宽度的两种方式的相关资料,需要的朋友可以参考下
recommend-type

C语言判定一棵二叉树是否为二叉搜索树的方法分析

主要介绍了C语言判定一棵二叉树是否为二叉搜索树的方法,结合实例形式综合对比分析了C语言针对二叉搜索树判定的原理、算法、效率及相关实现技巧,需要的朋友可以参考下
recommend-type

c语言 实现二叉树操作 用栈实现算术表达式求值

(1)题目一的内容和要求: 1、编写已知二叉树的先序、中序序列,恢复此二叉树的程序 2、编写求二叉树深度的程序 ... 2、将一个表达式的中缀形式转化为相应的后缀形式 3、依据后缀表达式计算表达式的值
recommend-type

zigbee-cluster-library-specification

最新的zigbee-cluster-library-specification说明文档。
recommend-type

管理建模和仿真的文件

管理Boualem Benatallah引用此版本:布阿利姆·贝纳塔拉。管理建模和仿真。约瑟夫-傅立叶大学-格勒诺布尔第一大学,1996年。法语。NNT:电话:00345357HAL ID:电话:00345357https://theses.hal.science/tel-003453572008年12月9日提交HAL是一个多学科的开放存取档案馆,用于存放和传播科学研究论文,无论它们是否被公开。论文可以来自法国或国外的教学和研究机构,也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire
recommend-type

优化MATLAB分段函数绘制:提升效率,绘制更快速

![优化MATLAB分段函数绘制:提升效率,绘制更快速](https://ucc.alicdn.com/pic/developer-ecology/666d2a4198c6409c9694db36397539c1.png?x-oss-process=image/resize,s_500,m_lfit) # 1. MATLAB分段函数绘制概述** 分段函数绘制是一种常用的技术,用于可视化不同区间内具有不同数学表达式的函数。在MATLAB中,分段函数可以通过使用if-else语句或switch-case语句来实现。 **绘制过程** MATLAB分段函数绘制的过程通常包括以下步骤: 1.
recommend-type

SDN如何实现简易防火墙

SDN可以通过控制器来实现简易防火墙。具体步骤如下: 1. 定义防火墙规则:在控制器上定义防火墙规则,例如禁止某些IP地址或端口访问,或者只允许来自特定IP地址或端口的流量通过。 2. 获取流量信息:SDN交换机会将流量信息发送给控制器。控制器可以根据防火墙规则对流量进行过滤。 3. 过滤流量:控制器根据防火墙规则对流量进行过滤,满足规则的流量可以通过,不满足规则的流量则被阻止。 4. 配置交换机:控制器根据防火墙规则配置交换机,只允许通过满足规则的流量,不满足规则的流量则被阻止。 需要注意的是,这种简易防火墙并不能完全保护网络安全,只能起到一定的防护作用,对于更严格的安全要求,需要
recommend-type

JSBSim Reference Manual

JSBSim参考手册,其中包含JSBSim简介,JSBSim配置文件xml的编写语法,编程手册以及一些应用实例等。其中有部分内容还没有写完,估计有生之年很难看到完整版了,但是内容还是很有参考价值的。