二叉排序树 你的名字 2022-08-25 05:29 151阅读 0赞 \#define FALSE 0 \#define TRUE 1 \#define ElemType int \#define Status int \#define EQ(a,b) ((a)==(b)) \#define LT(a,b) ((a)<(b)) \#define LQ(a,b) ((a)>(b)) \#include \#include \#include using namespace std; typedef struct BiTNode \{ // 结点结构 ElemType data; struct BiTNode \*lchild, \*rchild; // 左右孩子指针 \} BiTNode, \*BiTree; Status SearchBST (BiTree T, ElemType key, BiTree f, BiTree &p ) \{ // 在根指针 T 所指二叉排序树中递归地查找其关键字等于 key 的数据元素,若查找成功,则返回指针 p 指向该数据元素的结点,并返回TRUE; // 否则表明查找不成功,返回指针 p 指向查找路径上访问的最后一个结点,并返回函FALSE, 指针 f 指向当前访问 的结点的双亲,其初始调用值为NULL if (!T) \{ p = f; return FALSE; \} // 查找不成功 else if ( EQ(key, T->data) ) \{ p = T; return TRUE; \} // 查找成功 else if ( LT(key, T->data) ) SearchBST (T->lchild, key, T, p ); // 在左子树中继续查找 else SearchBST (T->rchild, key, T, p );// 在右子树中继续查找 \} // SearchBST void Delete ( BiTree &p ) \{ // 从二叉排序树中删除结点 p, 并重接它的左子树或右子树 BiTree q,s; if (!p->rchild) \{ // 右子树为空树则只需重接它的左子树 q = p; p = p->lchild; free(q); \} else if (!p->lchild) \{ // 左子树为空树只需重接它的右子树 q = p; p = p->rchild; free(q); \} else\{ //左右子树都不空 q = p; s = p->lchild; while (s->rchild) \{s = s->rchild; \} // 转左,然后向右到尽头 s-> rchild = q-> rchild;// 将待删除结点的右子树重接到S上 p = p->lchild; free(q); \} \} // Delete Status InsertBST(BiTree &T, ElemType e ) \{ // 当二叉排序树中不存在关键字等于 e.key 的数据元素时,插入元素值为 e 的结点,并返回 TRUE; 否则,不进行插入并返回FALSE BiTree p,s; if (!SearchBST ( T, e, NULL, p ))\{ s = (BiTree) malloc (sizeof (BiTNode)); // 为新结点分配空间 s->data = e; s->lchild = s->rchild = NULL; if ( !p ) T = s; // 插入 s 为新的根结点 else if ( LT(e, p->data) ) p->lchild = s;// 插入 \*s 为 \*p 的左孩子 else p->rchild = s; // 插入 \*s 为 \*p 的右孩子 return TRUE; // 插入成功 \} else return FALSE; \} // InsertBST Status DeleteBST (BiTree &T, ElemType key ) \{ // 若二叉排序树 T 中存在其关键字等于 key 的数据元素,则删除该数据元素结点,并返回函数值 TRUE,否则返回函数值 FALSE if (!T) return FALSE; // 不存在关键字等于key的数据元素 else \{ if ( EQ (key, T->data) ) \{ Delete (T); return TRUE; \}// 找到关键字等于key的数据元素 else if ( LT (key, T->data) ) DeleteBST ( T->lchild, key ); // 继续在左子树中进行查找 else DeleteBST ( T->rchild, key ); // 继续在右子树中进行查找 \} \} // DeleteBST void InOrderTraverse(BiTree T) \{//中序遍历二叉树,递归 if(T)\{ InOrderTraverse(T->lchild); cout<<T->data<<" "; InOrderTraverse(T->rchild); \} \} int arr\[10\] = \{1,5,6,4,3,2,7,8,10,9\}; int main() \{ ElemType e; int door = 1,c,flag; BiTree T,p; T = NULL; for(int i=0; i<10; ++i) InsertBST(T,arr\[i\]); while(door)\{ cout<<endl<<"请输入要查找元素:"; cin>>e; if(SearchBST(T,e,NULL,p)) \{ cout<<endl<<"查找成功!"<<endl<<"是否将其从二叉排序树中删除: 1.是 2.否 "<<endl; cin>>flag; if(flag) DeleteBST(T,e); \} else \{ cout<<"查找失败!"<<endl<<"是否将元素插入到二叉排序树中: 1.是 2.否 "<<endl; cin>>flag; if(flag) DeleteBST(T,e); InsertBST(T,e); \} cout<<endl<<"--------1.继续查找 2.查看二叉排序树元素 0.退出----------"<<endl<<"请输入数字继续操作:"; cin>>c; switch(c)\{ case 1: door =1; break; case 2: cout<<"二叉排序树中序遍历为:"; InOrderTraverse(T); cout<<endl<<"是否继续查找: 1.是 2.否 "<<endl; cin>>flag; if(flag)\{ door =1; break; \} else \{ cout<<"退出程序!"<<endl; door = 0 ; break;\} case 0: door =0; break; default: cout<<"输入错误,退出程序!"<<endl; door = 0; break; \} //switch \}//while return 0; \}
相关 二叉树和排序二叉树 二叉树 > 相关名词 > > 根节点 > > 左叶子节点 > > 右叶子节点 > > 子树 > > 高度 > 二叉树的排序方式: > > - 广度遍历( 灰太狼/ 2023年08月17日 16:53/ 0 赞/ 91 阅读
相关 二叉排序树 \define FALSE 0 \define TRUE 1 \define ElemType int \define Status int \define EQ(a, 你的名字/ 2022年08月25日 05:29/ 0 赞/ 152 阅读
相关 二叉排序树 Problem Description 二叉排序树的定义是:或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它 偏执的太偏执、/ 2022年07月12日 07:48/ 0 赞/ 137 阅读
相关 二叉排序树 Problem Description 二叉排序树的定义是:或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 怼烎@/ 2022年07月12日 03:54/ 0 赞/ 140 阅读
相关 二叉排序树 二叉排序树(Binary Sort Tree)性质: (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2)若右子树不空,则右子树上所有结点的值均大于它的 r囧r小猫/ 2022年06月16日 08:58/ 0 赞/ 165 阅读
相关 二叉排序树 题目描述 输入一系列整数,建立二叉排序数,并进行前序,中序,后序遍历。 输入 输入第一行包括一个整数n(1<=n<=100)。 接下来的一行包 痛定思痛。/ 2022年05月31日 01:58/ 0 赞/ 138 阅读
相关 二叉树-详解二叉排序树 二叉搜索树 首先二叉排序树也是一棵二叉树,所谓二叉树,就是“任何节点最多只允许两个子节点”,这两个子节点称为左右子节点。如下便是一个二叉树。 ![这里写图片描述][2 旧城等待,/ 2022年05月17日 01:18/ 0 赞/ 283 阅读
相关 二叉排序树 include<iostream> using namespace std; struct BiTree { in 拼搏现实的明天。/ 2022年05月14日 23:12/ 0 赞/ 198 阅读
相关 二叉排序树 二叉排序树BST,又叫二叉搜索树 或者是一棵空树,或者是具有下列性质的二叉树: (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2)若右子树不空 川长思鸟来/ 2022年02月24日 07:48/ 0 赞/ 209 阅读
还没有评论,来说两句吧...