建设企业功能型网站,企业信用信息公示系统广西,注册自己的网站,服装网站开发目的查找 #x1f388;3动态查找表#x1f52d;3.1二叉排序树#x1f3c6;3.1.1二叉排序树的类定义#x1f3c6;3.1.2二叉排序树的插入和生成#x1f3c6;3.1.3二叉树的查找#x1f3c6;3.1.4二叉排序树的删除 #x1f52d;3.2平衡二叉树#x1f3c6;3.2.1平衡二叉树的调整… 查找 3动态查找表3.1二叉排序树3.1.1二叉排序树的类定义3.1.2二叉排序树的插入和生成3.1.3二叉树的查找3.1.4二叉排序树的删除 3.2平衡二叉树3.2.1平衡二叉树的调整方法RR型调整LL型调整RL型调整LR型调整 3.2.2平衡二叉树的查找分析 3动态查找表
3.1二叉排序树
二叉排序树又称二叉查找树其或者是一棵空树或者是满足下列性质的二叉树
若它的左子树不空则左子树上所有元素的值均小于根结点元素的值。若它的右子树不空则右子树所有元素的值均大于根结点元素的值。左右子树分别为二叉排序树。
上述定义要求查找表中没有相同关键字的数据元素。 根据二叉排序树的定义可知对二叉排序树进行中序遍历可以得到一个有序序列。因此对于任意一个关键字序列构造一棵二叉排序树其实质是对此关键字序列进行排序使其变成有序序列。
3.1.1二叉排序树的类定义
#define _CRT_SECURE_NO_WARNINGS 1
#include iostream
using namespace std;
typedef int KeyType;
typedef int InfoType;
typedef struct
{KeyType key;//KeyType为关键字数据类型InfoType otherinfo;//其他域
}DElemType;
typedef struct BstNode
{DElemType data;BstNode* lchild, * rchild;
}BstNode;
class BsTree
{
private:BstNode* bst;void Insert(BstNode* t, DElemType e);//二叉排序树中递归插入一个结点BstNode* Search(BstNode* t, KeyType key);//递归查找关键字key
public:BsTree()//构造函数创建空的二叉排序树{bst NULL;}BstNode* SearchBST(KeyType key);//查找关键字等于key的结点void InsertBST(DElemType e);//递归创建的二叉树传递给私有成员void CreatBiTree(DElemType d[], int n);//生成二叉排序树n个数据在数组d中void DeleteBst(BstNode* t, DElemType e);//删除二叉排序树中的一个结点void Deletep(BstNode* p);/从二叉排序树中删除结点p,并重接它的左子树或右子树
};3.1.2二叉排序树的插入和生成
二叉排序树的插入操作应保证插入后仍满足二叉排序树的定义新插入的结点总是叶子结点。其插入过程如下
若二叉树t为空则生成一个根结点。将key于根结点的关键字比较若keydata,则将key插入到根结点的左子树中否则插入到根结点的右子树中。
void BsTree::Insert(BstNode* t, DElemType e)
{if (t NULL){t new BstNode;t-lchild t-rchild NULL;t-data e;return;}if (e.key t-data.key)Insert(t-lchild, e);//在左子树插入结点eelseInsert(t-rchild, e);//在右子树插入结点e
}
void BsTree::InsertBST(DElemType e)
{BstNode* t bst;Insert(t, e);bst t;
}
void BsTree::CreatBiTree(DElemType d[], int n)
{for (int i 0; i n; i){InsertBST(d[i]);}
}3.1.3二叉树的查找
由于二叉排序树按中序遍历可得有序序列所以在二叉排序树中进行查找与二分查找类似也是一个逐步缩小查找范围的过程查找的步骤如下
若二叉树t为空或keyt-data.key,则返回t。否则将key与根结点的关键字比较若keyt-datda.key,则递归查找左子树否则递归查找右子树。
BstNode* BsTree::Search(BstNode* t, KeyType key)
{if (t NULL || key t-data.key)return t;else if (key t-data.key)return Search(t-lchild, key);//查找左子树elsereturn Search(t-rchild, key);//查找右子树
}
BstNode* BsTree::SearchBST(KeyType key)
{BstNode* t bst;return Search(t, key);
}3.1.4二叉排序树的删除
二叉排序树中删除结点的原则是删除结点后仍是二叉排序树。 设在二叉排序树被删除结点是p,其双亲结点是f.不失一般性设p的左孩子或p为根结点。分三种情况讨论
若p为叶子结点则直接删除。如图a所示。若p只有左子树pl或只有右子树pr则令pl或pr直接成为双亲结点f的子树。如图b或c所示。 若被删除结点p既有左子树pl又有右子树pr,则在pl中选值最大的代替p,该数据按二叉排序树的性质应在左子树的最右下结点。
void BsTree::DeleteBst(BstNode* t, DElemType e)
{if (!t)return;else{if (e.key t-data.key)Deletep(t);else if (e.key t-data.key)DeleteBst(t-lchild, e);elseDeleteBst(t-rchild, e);}
}
void BsTree::Deletep(BstNode* p)
{if (!p)return;BstNode* s, * q;if (p-rchild NULL){q p;p p-lchild;delete q;}else if (p-lchild NULL){q p;p p-rchild;delete q;}else {q p;s p-lchild;while (s-rchild ! NULL){q s;s s-rchild;}p-data s-data;if (q ! p)q-rchild s-lchild;elseq-lchild s-rchild;delete s;}
}3.2平衡二叉树
平衡二叉树或者是一棵空的二叉排序树或者是具有下列性质的二叉排序树
它的左右子树均为平衡二叉树。左子树和右子树的高度之差的绝对值不超过1。
✅若将二叉树上结点的平衡因子定义为该结点的左子树的高度与右子树的高度之差则平衡二叉树上的所有结点的平衡因子只可能是1,0和-1。若平衡二叉树上有一个结点的平衡因子的绝对值大于1则该树就不是一棵平衡二叉树。
3.2.1平衡二叉树的调整方法
若向平衡二叉树中插入一个新结点而引起不平衡则采用以下方法进行调整
不涉及到不平衡点的双亲即以不平衡点为根的子树高度应保持不变。新结点插入后向根结点回溯找到第一个原平衡因子不为0的结点。在调整中仅涉及前面提到的最小子树。调整后二叉树的性质不变。
RR型调整
RR型调整是指在A结点的右孩子设为B结点的右子树上插入一个结点使得A结点的平衡因子由-1变为-2引起不平衡而产生的调整。如图所示带阴影区域表示插入结点h表示子树的树高。调整方法为单向左旋转平衡具体方法如下
把结点B变为调整后的最小子树的根结点。把结点A变成结点B的左孩子。把BL变成结点A的右子树。 LL型调整
LL型调整是指在A结点的左孩子设为B结点的左子树上插入一个结点使得A结点的平衡因子由1变为2引起不平衡而产生的调整。如图所示带阴影区域表示插入结点h表示子树的树高。调整方法为单向右旋转平衡具体方法如下
把结点B变为调整后的最小子树的根结点。把结点A变成结点B的右孩子。把BR变成结点A的左子树。
RL型调整
RL型调整是指在A结点的右孩子设为B结点的左子树上插入一个结点使得A结点的平衡因子由-1变为-2引起不平衡而产生的调整。如图所示带阴影区域表示插入结点h表示子树的树高。调整方法为右旋转后向左旋转平衡具体方法如下
把结点B的左孩子设为C变为调整后的最小子树的根结点。把结点A变成结点C的左孩子结点B变为结点C的右孩子。把结点C的右子树变为结点B的左子树。把结点C的左子树变为结点A的右子树。
LR型调整
LR型调整是指在A结点的左孩子设为B结点的右子树上插入一个结点使得A结点的平衡因子由1变为2引起不平衡而产生的调整。如图所示带阴影区域表示插入结点h表示子树的树高。调整方法为左旋转后向右旋转平衡具体方法如下
把结点B的右孩子设为C变为调整后的最小子树的根结点。把结点A变成结点C的右孩子结点B变为结点C的左孩子。把结点C的右子树变为结点A的左子树。把结点C的左子树变为结点B的右子树。
3.2.2平衡二叉树的查找分析 由于平衡二叉树关键字的查找过程与二叉排序树关键字的查找过程相同因此在平衡二叉树的查找过程中关键字的比较次数不超过平衡二叉树的深度。 好啦关于动态查找表二叉排序树和平衡二叉树的知识到这里就先结束啦后期会继续更新学习数据结构与算法的相关知识欢迎大家持续关注、点赞和评论❤️❤️❤️
