二进制排序树（二进制搜索树）

二进制排序树是具有以下属性的空树或二进制树:

（1）如果其左子树不为空，则左子树上所有节点的值都小于其根节点的值.

（2）如果右子树不为空，则右子树中所有节点的值都大于其根节点的值.

（3）它的左和右子树也是二进制排序树.

二分类树具有类似半搜索的特征二叉排序树 查找，并且使用名称表作为存储结构，因此它是一个动态查找表

插入二进制排序树

二进制排序树是一种动态树表，其特征在于树的结构通常不是一次生成的，而是在搜索过程中，当没有节点的键等于给定值时. 树插入. 新插入的节点必须是新添加的叶节点，并且是搜索失败时在搜索路径上访问的最后一个节点的左或右子节点.

在插入过程中: 如果二叉树为空，则将要插入的节点* S作为根节点插入到空树中；

当二叉树不为空时，将要插入到节点中的关键字S->键与树的root关键字进行比较. 如果它们相等，则无需插入；大于插入右子树中；在树上. 继续这种方式，直到将节点* S作为新叶子插入到二叉树中，或者直分支找到相同的关键字.

二进制排序树的删除过程

让* p为要删除的节点，其父节点为* f，左右子树为PL，PR

（1）如果* p节点是叶节点，即PL PR为空，则只要修改父节点的指针，删除* p不会破坏整个树的结构.

（2）如果* p节点仅具有左子树PL或仅具有右子树PR，有时

当* p是* f的左子代时，删除* p并将PL或PR用作* p的父* f的左子树；

当* p是* f的右子时，删除* p并将PL或PR用作* p的父* f的右子树；

⑶如果节点* p的左右子树都不为空，则首先找到* p的中阶前任节点* s（注意* s是* p Point左子树中最右边的最低节点，其右链域为空），然后有两种方法:

①让* p的左子树直接链接到* p的父节点* f的左链，而* p的右子树直接链接到* p的中阶前任节点* s的右链.

②用* p的中级前任节点* s替换* p（即，将* s的数据复制到* p），将* s的左子树链接到* s * q的父节点在左侧（或右侧）链上.

理解删除操作的更简单方法是: * p是要删除的节点，然后将* p向下移动到叶节点并删除它；您可以将其与右侧子树中的最小关键字交换，也可以将其与左侧子树中的最大关键字交换. 如果* p本身是叶节点，则直接将其删除；如果它是一个非叶节点二叉排序树 查找，则它至少具有一个非空子树，因此至少有一个这样的交换是可能的；如果在交换之后，* p不是叶节点为了进行进一步的交换，* p必须最终到达可删除的树的底部，即成为叶节点.

二元排序树的性能分析

二叉搜索树中搜索的运行时间与树的高度T成正比. 因为具有n个节点的树的高度对于小是O（logn），对于大是O（n）；

对于具有n个关键字元素的数据项，高度为h的二叉搜索树T的空间复杂度为O（n）；查找元素，插入元素和删除元素的时间复杂度均为O（h）；

二元排序树的搜索过程类似于二分法，它也是逐渐缩小搜索范围的过程. 如果搜索成功，它将采用从根节点到要检查的节点的路径. 如果失败，它将采用从根节点到叶节点的路径. 因此，在搜索过程中与关键字进行比较的次数不会超过树的深度.

因为具有n个节点的二元排序树不是唯一的，所以具有n个节点的二元排序树的平均搜索长度与树的形状有关；

最佳情况: 二进制排序树和二进制决策树具有相同的形式；

最坏的情况: 二进制排序树是单个分支树，平均搜索长度与顺序搜索相同；

就平均性能而言，二进制排序树上的搜索与二进制搜索没有太大区别，并且二进制排序树上的插入和删除节点非常方便，而无需移动很多节点.

/ ************************************************** **** ************************** /

/ *构建一个二叉搜索树，然后查找元素，删除元素，调整并遍历输出* /

/ ************************************************** **** ************************** /

#include

#include

#include

#define错误0

使用命名空间标准；

struct TreeNode // //查找树节点

{

int m_nValue;

TreeNode * lchild; //左孩子

TreeNode * rchild; //合适的孩子

};

class BSTree //二进制搜索树类

{

私人:

公开

:

BSTree（）;

〜BSTree（）;

void InsertTree（TreeNode *和root，int数据）； //插入以构建二叉搜索树

TreeNode * SearchTree（TreeNode *根，整数数据）； //在二进制搜索树中搜索和查找元素

void DeleteTree（TreeNode *和根，int数据）； //删除二叉搜索树搜索中的元素

void TrvaerTree（TreeNode *根）； //遍历

void MidTrvaerTree（TreeNode *根）； //中阶遍历

void AftTrvaerTree（TreeNode *根）； //后遍历

};

BSTree :: BSTree（）

{

}

BSTree ::〜BSTree（）

{

}

void Swap（int＆a，int＆b）//交换两个数据，请注意将引用变量用作参数

{

int temp;

temp = a;

a = b;

b =温度；

}

void BSTree ::插入树（TreeNode *和根，整数数据）//插入数据以构建二叉搜索树

{

如果（root == NULL）

{

root =（TreeNode *）malloc（sizeof（TreeNode））; //分配节点

如果（！root）

退出（错误）；

root-> m_nValue =数据;

root-> lchild = NULL;

root-> rchild = NULL;

}

否则if（data> root-> m_nValue）

InsertTree（根目录-> rchild，数据）；

否则，如果（数据 m_nValue）

InsertTree（根目录-> lchild，数据）；

}

void BSTree :: TrvaerTree（TreeNode *根）//预遍历

{

如果（根）

{

cout <<“”“ << root-> m_nValue;

}

如果（root-> lchild）

TrvaerTree（根目录-> lchild）；

如果（root-> rchild）

TrvaerTree（根目录-> rchild）；

}

void BSTree :: MidTrvaerTree（TreeNode *根）//序列遍历

{

如果（root-> lchild）

MidTrvaerTree（root-> lchild）;

如果（根）

{

cout <<“”“ << root-> m_nValue;

}

如果（root-> rchild）

MidTrvaerTree（root-> rchild）;

}

void BSTree :: AftTrvaerTree（TreeNode *根）//后遍历

{

如果（root-> lchild）

AftTrvaerTree（根目录-> lchild）；

如果（root-> rchild）

AftTrvaerTree（根目录-> rchild）；

如果（根）

{

cout <<“”“ << root-> m_nValue;

}

}

TreeNode * BSTree :: SearchTree（TreeNode *根，整数数据）//二进制搜索树搜索

{

如果（根）

{

如果（root-> m_nValue ==数据）

返回根；

否则if（data> root-> m_nValue）

SearchTree（根目录-> rchild，数据）；

else SearchTree（根目录-> lchild，数据）；

}

否则返回NULL;

}

/ *删除二叉搜索树中的元素，首先将要删除的元素调整为叶节点，调整侧面

公式是，您可以将其与右侧子树中的最小关键字交换，也可以与左侧子树中的交换

最多交换关键字；如果不是交换后的叶子节点，则进一步调整；成功

在叶节点之后直接将其删除. 删除的树仍然是二进制搜索树* /

void BSTree :: DeleteTree（TreeNode *和根，int数据）

{

TreeNode * p，* q，* r;

q = SearchTree（根，数据）； //找到要删除的节点

p = q;

while（p-> rchild || p-> lchild）

{

r = p; //记录父节点

if（p-> rchild）//在右侧子树中找到最小的

{

p = p-> rchild;

同时（p-> lchild）

{

r = p;

p = p-> lchild;

}

交换（p-> m_nValue，q-> m_nValue）; //交换节点元素

q = p; //更新q的位置

}

else if（p-> lchild）//在左侧子树中找到最大的

{

p = p-> lchild;

同时（p-> rchild）

{

r = p;

p = p-> rchild;

}

交换（p-> m_nValue，q-> m_nValue）; //交换节点元素

q = p;

}

}

if（r-> lchild == p）//删除叶节点

r-> lchild = NULL;

否则if（r-> rchild == p）

r-> rchild = NULL;

免费（p）;

p = NULL;

}

int main（）

{

BSTree BiTree = BSTree（）;

TreeNode * root = NULL;

int数据；

同时（1）

{

cin >>数据；

如果（数据== 0）中断;

BiTree.InsertTree（根，数据）；

}

BiTree.TrvaerTree（根）；

cout << endl;

BiTree.MidTrvaerTree（根）；

cout << endl;

BiTree.AftTrvaerTree（根）；

cout << endl;

cin >>数据；

BiTree.DeleteTree（根，数据）；

cout <<“删除后: ” << endl;

// BiTree.AdjustTree（根）；

cout <<“调整后: ” << endl;

BiTree.TrvaerTree（根）；

cout << endl;

BiTree.MidTrvaerTree（根）；

返回1；

}

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-187147-1.html