中国建设企业银行网站首页,成都成仁路网站建设,冠县哪做网站,dedecms改WordPress二叉排序树#xff08;二叉查找树#xff09;基本操作_20230417
前言
二叉排序树首先是一颗二叉树#xff0c;它不同于常规二叉树的地方在于#xff0c;如果左子树不为空#xff0c;那么左子树上所有结点的值都不大于根节点的值#xff0c;如果右子树不为空#xff0c…二叉排序树二叉查找树基本操作_20230417
前言
二叉排序树首先是一颗二叉树它不同于常规二叉树的地方在于如果左子树不为空那么左子树上所有结点的值都不大于根节点的值如果右子树不为空那么右子树上所有的值不小于根节点的值而且它的左右子树本身也属于二叉排序树。
二叉排序树的形式和元素的输入顺序相关它最坏的情况下可能退化为有序线性表。大多数条件下二叉排序树既具备二叉树的折半查找行者又采用了链表作为储存结构加强了数据储存的灵活性不失为一种优秀的数据储存结构。
下面的二叉排序树通过中序遍历就得到一组有序表。 二叉排序树的基本操作
2.1 查找操作
二叉排序树的查找操作操作可通过递归实现由于二叉排序树当中的每个元素都包含有数据域、左孩子指针和右孩子指针通过递归可以定位到是在左孩子还是右孩子区域进行查找。如果元素比对成功则返回 true如果查找失败则返回false. 如果查找成功其中的某个递归变量保留查找成功的结点如果没有找到目标元素则某个递归变量保留此元素的根节点父节点的位置。
查找的实际上是沿着根节点往下遍历的过程它会形成一颗合适的遍历路径如果配对成功路径上的结点都是目标结点的父节点。
看一个具体的例子。给点上述二叉排序树要求查找元素的值为30那么遍历形成路径用绿色虚线表示遍历经过了左–左–右的路径。 元素查找的实现, 如果发现递归结点已经为NULL意识是查询失败此二叉排序树当中不含有目标元素此时查找目标赋值为待查找元素的父节点同时返回查询失败标记false, false会在退栈过程中不断传递给当前的栈最终查找函数返回false.
同时如果当前结点的值和待查找的值相等意味着本次查询成功递归可以结束不再入函数栈同时返回查询成功的标记truetrue会在退栈过程中不断传递给上一级函数栈最终查找函数返回true。
typedef struct BiTNode
{SElemType data;struct BiTNode *lchild;struct BiTNode *rchild;
} BiTNode, *BiTree;bool find_bst(BiTree T, KeyType key, BiTree parent, BiTree *target_ptr)
{if(TNULL){*target_ptrparent;return false; //one of termination conditions, traveling with parent}else{//another condition of termination conditions//traveling with parentif(EQ(key,T-data.key)) {*target_ptrT;return true;}else if (LT(key, T-data.key)){return find_bst(T-lchild,key,T,target_ptr);}else{return find_bst(T-rchild,key,T,target_ptr);}}
}2.2 插入和创建树操作
二叉排序树是一类动态表其原因在于如果树中不含有待插入元素那么二叉排序树会执行插入操作从而达到动态更新表的目的。插入和创建实际上可以共用一个过程插入的过程也是创建树的过程。利用上面的查找函数可以实现插入的过程。正如前面所述插入过程需要先判断待插入元素是否在现有的表当中如果不包含在目前的表当中则需要执行插入操作并返回插入成功的标记true否则则直接返回未执行插入的标记false.
bool insert_bst(BiTree *bt, KeyType key)
{BiTree ptr;BiTree new_node;if(!find_bst(*bt,key,NULL,ptr)){new_node(BiTree)malloc(sizeof(BiTNode));new_node-data.keykey;new_node-data.valueNULL;new_node-lchildNULL;new_node-rchildNULL;if(ptrNULL) // dont leave this condition behind{*btnew_node;}else if(LT(key,ptr-data.key)){ptr-lchildnew_node;}else{ptr-rchildnew_node;}return true;}return false;
}2.3 二叉排序树删除操作
二叉排序树的结点删除分3种情况讨论
a.) 若P为叶子结点既PL和PR均为空树由于删除叶子结点不破坏树的结点只需要修改P结点的指针即可也就是*pNULL即可。 b.) 上述图若 P结点只有左子树或只有右子树此时只要令PL或PR称为父节点的左子树即可也即是把指针赋值为结点P即可
c.) 若P结点的左右子树均不为空如果删除元素P后需要保持二拆排序树仍然有序那么就有两种途径①-a途径称之为替代法用p元素的直接前驱元素S里面的值替代P里面的值P的左右孩子指针保持不变同时删除S结点把S结点的左孩子赋值给其双亲结点的右孩子②-b途径是利用待删除元素的左子树根节点来替代P所在结点同时把P结点原有的右子树赋值给左子树的最右端元素。
两种类型不同在于①-a利用原有结点的左右孩子指针只是替代元素②-b则是直接修改替换原有结点并更新现有结点的对应指针。 c) 删除的代码实现
二叉排序树的删除过程仍然采用递归函数如果找到待删除元素则执行删除操作并返回删除成功标记否则返回删除失败标记。
bool delete_bst(BiTree *T, KeyType key)
{//if deletion is succesfful, it will return true;//if deletion is not successful, it will return falseif(*TNULL){return false; // one termination condition}else{if(EQ(key,(*T)-data.key)){delete_action_b(T); //propagate the return valuereturn true; //the second termination condition}else if (LT(key, (*T)-data.key)){return delete_bst(((*T)-lchild),key);}else{return delete_bst(((*T)-rchild), key);}}
}分别用两个函数实现不同的删除模式
//①-a implementation code
void delete_action_a(BiTree *node)
{//p;//s;//list three scenarios of nodeBiTree p;BiTree s;if((*node)-lchildNULL){p*node;(*node)(*node)-rchild;free(p);}else if ((*node)-rchild NULL){p *node;(*node) (*node)-lchild;free(p);}else{p *node;s(*node)-lchild; //next onewhile(s-rchild!NULL){ps;ss-rchild;}(*node)-datas-data;if(p!(*node)){p-rchilds-lchild;}else{p-lchilds-lchild; //no right child and jumpt one node}free(s);}return;
}//②-b implementation code
void delete_action_b(BiTree *node)
{BiTree p;BiTree s;if ((*node)-lchild NULL){p *node;(*node) (*node)-rchild;free(p);}else if ((*node)-rchild NULL){p *node;(*node) (*node)-lchild;free(p);}else{p *node;s (*node)-lchild;while (s-rchild ! NULL){s s-rchild;}s-rchild(*node)-rchild; // 先后顺序非常重要(*node)(*node)-lchild; // 先后顺序非常重要free(p);}return;
}二叉查找树的形式
与静态二叉搜索树不同静态二叉搜索树的形式是唯一的对于相同的元素集合二叉查找树的形式会随着不同的排列顺序呈现不同的树的形态。由于树的形态不同造成树的深度不同导致平均查找长度不同(Average Search Length)如果输入有序元素二叉查找树就退化为有序线性表导致极端的情况发生。 这就为后面平衡二叉查找树的引入提供了应用场景本文仅针对二叉排序树不会对AVL树进一步阐述。
小结
本文学习了二叉排序树的不同操作包括插入、建树和删除等操作同时阐述了不同形态的二叉查找树会影响查找效率极端情况下有序输入会导致二叉排序树蜕变为线性表严重影查询效率。
参考资料
《数据结构》严蔚敏清华大学
