首页 / 算法 / 数据结构与算法问题 二叉搜索树
数据结构与算法问题 二叉搜索树
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了数据结构与算法问题 二叉搜索树,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含4156字,纯文字阅读大概需要6分钟。
内容图文
1、序
详细实现了二叉查找树的各种操作:插入结点、构造二叉树、删除结点、查找、 查找最大值、查找最小值、查找指定结点的前驱和后继
2、二叉查找树简介
它或者是一棵空树;或者是具有下列性质的二叉树: (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值; (3)左、右子树也分别为二叉排序树
3、二叉查找树的各种操作
此处给出代码,注释非常详细,具体操作请参考代码:
#include <iostream> using namespace std; typedef struct Binary_Search_Tree //结点结构体 { int data; Binary_Search_Tree * lchild; Binary_Search_Tree * rchild; Binary_Search_Tree * parent; }Binary_Search_Tree ; void insert(Binary_Search_Tree * & root,int data) //插入 { Binary_Search_Tree * p=new Binary_Search_Tree; p->data=data; p->lchild=p->rchild=p->parent=NULL; if(root==NULL) //如果为空树,即插入结点为根结点 { root=p; return ; } //插入到当前父节点的右节点 if(root->rchild==NULL&&root->data<data) { root->rchild=p; p->parent=root; return ; } //插入到当前父结点的左节点 if(root->lchild==NULL&&root->data>data) { p->parent=root; root->lchild=p; return ; } if(root->data>data) insert(root->lchild,data); else if(root->data < data) insert(root->rchild,data); else return; } void create(Binary_Search_Tree * & root,int a[],int size) { root=NULL; for(int i=0;i<size;i++) insert(root,a[i]); } //查找元素,找到返回关键字的结点指针,没找到则返回NULL Binary_Search_Tree * search(Binary_Search_Tree * &root,int data) { if(root==NULL) return NULL; if(data<root->data) return search(root->lchild,data); else if(data>root->data) return search(root->rchild,data); else return root; } //递归方式找到最小的元素 Binary_Search_Tree * searchmin(Binary_Search_Tree * &root) { if(root==NULL) return NULL; if(root->lchild==NULL) return root; else return searchmin(root->lchild); } //递归方式寻找最大的元素 Binary_Search_Tree * searchmax(Binary_Search_Tree * &root) { if(root==NULL) return NULL; if(root->rchild==NULL) return root; else return searchmax(root->rchild); } //查找某个节点的前驱 Binary_Search_Tree * seachpredecessor(Binary_Search_Tree * & p) { //空树 if(p=NULL) return p; if(p->lchild) return searchmax(p->lchild); //无左子树,查找某个结点的右字树遍历完了 else { if(p->lchild==NULL) return NULL; //向上寻找前驱 while(p) { if(p->parent->rchild==p) break; } return p->parent; } } //查找某个元素的后继 Binary_Search_Tree * searchsuccessor(Binary_Search_Tree * & p) { if(p==NULL) return p; if(p->rchild) return searchmin(p->rchild); else { if(p->rchild==NULL) return NULL; //向上寻找后继 while(p) { if(p->parent->lchild==p) break; } return p->parent; } } //根据关键字删除某个结点 //如果把根结点删掉,那么要改变根结点的地址,所以传二级指针 void deletetree(Binary_Search_Tree * & root,int data) { Binary_Search_Tree *q; Binary_Search_Tree *p=search(root,data); if(!p) return ; //如果没有左,右子结点,则直接删除 if(p->lchild==NULL&&p->rchild==NULL) { if(p->parent==NULL) { delete p; root=NULL; } else { if(p==p->parent->lchild) p->parent->lchild=NULL; else p->parent->rchild=NULL; delete p; } } //如果有左结点,没有右结点 if(p->lchild&&!(p->rchild)) { p->lchild->parent=p->parent; if(p->parent==NULL) root=p->lchild; else if(p==p->parent->lchild) p->parent->lchild=p->lchild; else p->parent->rchild=p->lchild; delete p; } //如果有右结点,没有左结点 else if(p->rchild&&!(p->lchild)) { p->rchild->parent=p->parent; if(p->parent==NULL) root=p->rchild; else if(p->parent->lchild==p) p->parent->lchild=p->rchild; else p->parent->rchild=p->rchild; delete p; } //如果既有左结点,又有右结点 else if(p->rchild&&p->lchild) { if(p->parent==NULL) root=p->rchild; if(p->parent->lchild==p) p->parent->lchild=p->rchild; else if(p->parent->rchild==p) p->parent->rchild=p->lchild; delete p; } else { //找到要删除点的后继 q=searchsuccessor(p); int temp=q->data; //删除后继节点 deletetree(root,q->data); p->data=temp; } } int main() { Binary_Search_Tree * root=NULL; int a[12]={15,1,21,3,7,17,20,2,4,13,9}; create(root,a,11); Binary_Search_Tree * x=new Binary_Search_Tree; deletetree(root,21); //删除结点21 x=searchmin(root); cout<<x->data; cout<<endl; x=searchmax(root); cout<<x->data; cout<<endl; return 0; }
原文:http://blog.csdn.net/leviathan_/article/details/38540555
内容总结
以上是互联网集市为您收集整理的数据结构与算法问题 二叉搜索树全部内容,希望文章能够帮你解决数据结构与算法问题 二叉搜索树所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。