数据结构C++ |
您所在的位置：网站首页 › 二叉树排序算法 › 数据结构C++ |
|
数据结构C++——二叉排序树
文章目录
数据结构C++——二叉排序树一、前言二、二叉排序树的相关概念三、树表的查找①二叉排序树的存储表示②二叉排序树的递归查找③二叉排序树的插入④二叉排序树的创建⑤二叉排序树的删除
四、完整测试代码五、总结
一、前言
二叉排序树用到了二叉树中序遍历的知识，以及树的相关操作部分的知识，由于笔者在之前的文章中已介绍过树的知识，在此不再过多赘述，对此部分不太了解的读者欢迎移步此文章，共同学习！： 数据结构C++——二叉树的遍历（递归和非递归）及一些简单操作 二、二叉排序树的相关概念（1）二叉排序树：又称二叉查找树，它是一种对排序和查找都很有用的特殊二叉树。 （2）二叉排序树或者是一棵空树，或者是具有下列性质的二叉树： a、若它的左子树不空，则左子树上所有结点的值均小千它的根结点的值； b、若它的右子树不空，则右子树上所有结点的值均大千它的根结点的值； c、它的左、 右子树也分别为二叉排序树。 （3）二叉排序树是递归定义的。 由定义可以得出二叉排序树的一个重要性质：中序遍历一棵二叉树时可以得到一个结点值递增的有序序列。 三、树表的查找 ①二叉排序树的存储表示二叉排序树的存储表示 /*-----------二叉排序树的二叉链表的存储表示-----------*/ #define ENDFLAG 999 typedef int KeyType; typedef int InfoType; typedef struct { KeyType key;//关键子项 InfoType otherinfo;//其他数据域 }ElemType; typedef struct BSTNode { ElemType data;//每个结点的数据域包括关键字项和其他数据项 struct BSTNode* lchild, * rchild;//左右孩子指针 }BSTNode,*BSTree; ②二叉排序树的递归查找二叉排序树的递归查找 二叉排序树递归查找的算法思路： 1：若传入关键字值小于此时的树节点值，则递归遍历树的左子树 2：若传入关键字值大于此时的树节点值，则递归遍历树的右子树 3、若此时关键字值等于此时树节点值，则返回指向该数据元素结点的指针，否则返回空指针 /*-----------二叉排序树的查找--------------*/ /*--------- 二叉排序树的递归查找-----------*/ BSTree SearchBST(BSTree T, KeyType key) { //在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素 //若查找成功，则返回指向该数据元素结点的指针，否则返回空指针 if ((!T) || key == T->data.key) return T;//查找结束 else if (key data.key) return SearchBST(T->lchild, key);//在左子树中继续查找 else return SearchBST(T->rchild, key);//在右子树中继续查找 } ③二叉排序树的插入二叉排序树的插入 二叉排序树的插入算法思路： 1：若传入关键字值小于此时树结点值，则插入到树的左子树 2：若传入关键字值大于此时树结点值，则插入到树的右子树 3：找到插入位置后，生成新节点S，将将S的数据域置为e，新结点S作为叶子结点，将S链接到已找到的插入位置 /*----------二叉排序树的插入------------*/ void InsertBST(BSTree& T, ElemType e) { if (!T) { BSTNode* S = new BSTNode;//生成新结点*S S->data = e;//新结点*S的数据域置为e S->lchild = S->rchild = NULL;//新结点*S作为叶子结点 T = S;//把新结点*S链接到已找到的插入位置 } else if (e.key data.key) InsertBST(T->lchild, e);//将*S插入左子树 else if (e.key > T->data.key) InsertBST(T->rchild, e);//将*S插入右子树 } ④二叉排序树的创建二叉排序树的创建 二叉排序树的创建算法思路： 1：预定义一个输入结束值ENDFLAG 2：不断输入关键字key，调用InsertBST()函数将树元素插入到树中 /*----------二叉排序树的创建-----------*/ void CreatBST(BSTree& T) { //依次读入一个关键字为key的结点，将此结点插入二叉排序树T中 T = NULL;//将二叉排序树T初始化为空树 ElemType e; cin >> e.key; while (e.key != ENDFLAG) { InsertBST(T, e); cin >> e.key; } InsertBST(T, e); } ⑤二叉排序树的删除二叉排序树的删除 二叉排序树的删除算法思路： 1：找到传入关键字在二叉排序树中的位置，p指向该位置，f指向p的双亲结点 2：当删除结点为叶子结点时，直接删除此结点即刻 3：当删除结点无左子树时或无右子树时，删除结点接上p的左子树或右子树即可 4：若删除结点有左子树和右子树，则找到该结点的直接前驱，即左子树的右下结点，用前驱结点替换被删除结点。 /*---------二叉排序树的删除----------*/ void DeleteBST(BSTree& T, KeyType key) { //从二叉排序树T中删除关键字等于key的结点 BSTNode* p = new BSTNode; BSTNode* f = new BSTNode; p = T; f = NULL;//初始化 /*--------------下面的while循环从根开始查找关键字等于key的结点*p----------*/ while (p) { if (p->data.key == key) break;//找到关键字等于key的结点*p，结束循环 f = p;//*f为*p的双亲结点 if (p->data.key > key) p = p->lchild;//在*p的左子树中继续查找 else p = p->rchild;//在*p的右子树中继续查找 } if (!p) return;//找不到被删结点则返回 /*------考虑3种情况实现p所指子树内部的处理：*p左右子树均不空、无右子树、无左子树----*/ BSTNode* q = new BSTNode; q = p; if ((p->lchild) && (p->rchild)) {//被删结点*p左右子树均不空 BSTNode* s = new BSTNode; s = p->lchild; while (s->rchild) {//在*p的左子树中继续查找其前驱结点，即右下结点 q = s; s = s->rchild;//向右到尽头 } p->data = s->data;//s指向被删结点的“前驱” if (q != p) q->rchild = s->lchild;//重接*q的右子树 else q->lchild = s->lchild;//重接*q的左子树 delete s; return; } else if (!p->rchild)//被删结点*p无右子树，只需重接其左子树 p = p->lchild; else if (!p->lchild)//被删结点*p无左子树，只需重接其右子树 p = p->rchild; /*---------将p所指的子树挂接到其双亲结点*f相应的位置---------*/ if (!f) T = p;//被删结点为根结点 else if (q == f->lchild) f->lchild = p;//挂接到*f的左子树位置 else f->rchild = p;//挂接到*f的右子树位置 delete q; } 四、完整测试代码测试代码 #include using namespace std; /*-----------二叉排序树的二叉链表的存储表示-----------*/ #define ENDFLAG 999 typedef int KeyType; typedef int InfoType; typedef struct { KeyType key;//关键子项 InfoType otherinfo;//其他数据域 }ElemType; typedef struct BSTNode { ElemType data;//每个结点的数据域包括关键字项和其他数据项 struct BSTNode* lchild, * rchild;//左右孩子指针 }BSTNode,*BSTree; /*-----------二叉排序树的查找--------------*/ /*--------- 二叉排序树的递归查找-----------*/ BSTree SearchBST(BSTree T, KeyType key) { //在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素 //若查找成功，则返回指向该数据元素结点的指针，否则返回空指针 if ((!T) || key == T->data.key) return T;//查找结束 else if (key data.key) return SearchBST(T->lchild, key);//在左子树中继续查找 else return SearchBST(T->rchild, key);//在右子树中继续查找 } /*----------二叉排序树的插入------------*/ void InsertBST(BSTree& T, ElemType e) { if (!T) { BSTNode* S = new BSTNode;//生成新结点*S S->data = e;//新结点*S的数据域置为e S->lchild = S->rchild = NULL;//新结点*S作为叶子结点 T = S;//把新结点*S链接到已找到的插入位置 } else if (e.key data.key) InsertBST(T->lchild, e);//将*S插入左子树 else if (e.key > T->data.key) InsertBST(T->rchild, e);//将*S插入右子树 } /*----------二叉排序树的创建-----------*/ void CreatBST(BSTree& T) { //依次读入一个关键字为key的结点，将此结点插入二叉排序树T中 T = NULL;//将二叉排序树T初始化为空树 ElemType e; cin >> e.key; while (e.key != ENDFLAG) { InsertBST(T, e); cin >> e.key; } InsertBST(T, e); } /*---------二叉排序树的删除----------*/ void DeleteBST(BSTree& T, KeyType key) { //从二叉排序树T中删除关键字等于key的结点 BSTNode* p = new BSTNode; BSTNode* f = new BSTNode; p = T; f = NULL;//初始化 /*--------------下面的while循环从根开始查找关键字等于key的结点*p----------*/ while (p) { if (p->data.key == key) break;//找到关键字等于key的结点*p，结束循环 f = p;//*f为*p的双亲结点 if (p->data.key > key) p = p->lchild;//在*p的左子树中继续查找 else p = p->rchild;//在*p的右子树中继续查找 } if (!p) return;//找不到被删结点则返回 /*------考虑3种情况实现p所指子树内部的处理：*p左右子树均不空、无右子树、无左子树----*/ BSTNode* q = new BSTNode; q = p; if ((p->lchild) && (p->rchild)) {//被删结点*p左右子树均不空 BSTNode* s = new BSTNode; s = p->lchild; while (s->rchild) {//在*p的左子树中继续查找其前驱结点，即右下结点 q = s; s = s->rchild;//向右到尽头 } p->data = s->data;//s指向被删结点的“前驱” if (q != p) q->rchild = s->lchild;//重接*q的右子树 else q->lchild = s->lchild;//重接*q的左子树 delete s; return; } else if (!p->rchild)//被删结点*p无右子树，只需重接其左子树 p = p->lchild; else if (!p->lchild)//被删结点*p无左子树，只需重接其右子树 p = p->rchild; /*---------将p所指的子树挂接到其双亲结点*f相应的位置---------*/ if (!f) T = p;//被删结点为根结点 else if (q == f->lchild) f->lchild = p;//挂接到*f的左子树位置 else f->rchild = p;//挂接到*f的右子树位置 delete q; } /*------------二叉树的中序遍历------------*/ void InorderTree(BSTree T) { if (T) { InorderTree(T->lchild); cout |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
| CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |