首页 / 算法 / 数据结构：3.4 二叉搜索树、平衡二叉树
数据结构：3.4 二叉搜索树、平衡二叉树
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了数据结构：3.4 二叉搜索树、平衡二叉树，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1829字，纯文字阅读大概需要3分钟。
内容图文
二叉搜索树：
特征：左子树键值 < 根结点键值 < 右子树键值
左右子树也都是二叉搜索树
#include <stdio.h> #include <stdlib.h> typedef int ElementType; typedef struct TNode *Position; typedef Position BinTree; struct TNode{ ElementType Data; BinTree Left; BinTree Right; };
操作集：
查找：查找效率取决于树的高度
Position Find( BinTree BST, ElementType X ) {
while
(BST) {
if( X > BST->Data )
BST = BST->Right;
elseif( X < BST->Data )
BST = BST->Left;
elsereturn BST;
}
return NULL;
}
Position FindMin( BinTree BST ) {
if( BST )
while( BST->Left ) BST = BST->Left;
return BST;
}
Position FindMax( BinTree BST ) {
if( BST )
while( BST->Right ) BST = BST->Right;
return BST;
}
插入：要先找到插入元素的位置
//
插入
BinTree Insert( BinTree BST, ElementType X ) {
if( !BST ) { //若原树为空，则生成一个
BST = malloc(sizeof(struct TNode));
BST->Data = X;
BST->Left = BST->Right = NULL;
}
else {
if( X < BST->Data )
BST->Left = Insert( BST->Left,X );
elseif( X > BST->Data )
BST->Right = Insert( BST->Right,X );
} //若X已经存在，就不插入return BST;
}
删除：有三种情况
//
删除
BinTree Delete( BinTree BST, ElementType X ) {
Position Tmp;
if(!BST) printf("Not Found\n");
elseif( X < BST->Data )
BST->Left = Delete(BST->Left,X); //左子树递归删除elseif( X > BST->Data )
BST->Right = Delete(BST->Right,X); //右子树递归删除else//找到了要删除的结点if( BST->Left && BST->Right ) { //被删除结点有左、右两个子结点
Tmp = FindMin ( BST->Right );
//在右子树中找到最小元素填充被删处
BST->Data = Tmp->Data;
BST->Right = Delete( BST->Right,BST->Data ); //删除右子树中最小的元素 }
else { //被删结点有 一个或无 子结点
Tmp = BST;
if( !BST->Left )
BST = BST->Right;
elseif( !BST->Right )
BST = BST->Left;
free( Tmp );
}
return BST;
}
平衡二叉树
特征：左右子树的高度差小于等于1
节点数为 n 的平衡二叉树的最大高度为 O(log n)（向上取整）
平衡二叉树的调整：插入结点后二叉树不平衡，RR旋转或LL旋转
原文：https://www.cnblogs.com/Pio-GD/p/14379553.html
内容总结
以上是互联网集市为您收集整理的数据结构：3.4 二叉搜索树、平衡二叉树全部内容，希望文章能够帮你解决数据结构：3.4 二叉搜索树、平衡二叉树所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。