// 链式二叉查找树的各种操作.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include<iostream>
using namespace std;
struct BSTree
{
int data;
BSTree *left;
BSTree *right;
};
//标记在插入时，如果已存在，则为true ，表示不需要插入，否则为false
bool flag = false;
int a[100];
//查找操作
BSTree *search(BSTree *r,int x)
{
if(r==NULL)
return NULL;
else
{
if(r->data==x)
return r;
else if(r->data>x)
return search(r->left,x);
else
return search(r->right,x);
}
}
//返回最小值节点
BSTree *BSTMinNum(BSTree *r)
{
BSTree *s=r;
while(s->left!=NULL)
{
s=s->left;
}
return s;
}
//返回最大值节点
BSTree *BSTMaxNum(BSTree *r)
{
BSTree *s=r;
while(s->right!=NULL)
{
s=s->right;
}
return s;
}
//获得其父节点
BSTree *getFather(BSTree *r, BSTree *s)
{
BSTree *sf;
if(r==NULL||r==s)
sf=NULL;
else
{
if(s==r->left||s==r->right)
sf= r;
else if(s->data > r->data)
sf=getFather(r->right,s);
else
sf=getFather(r->left,s);
}
return sf;
}
//获得节点中序的前趋节点
//此操作不需要遍历树
BSTree *searchPreMidOrder(BSTree *r,int val)
{
BSTree *s = search(r,val);
if(s==NULL)
return NULL;
else
{
//如果左儿子节点非空，则找到左子树的最大值节点
if(s->left!=NULL)
return BSTMaxNum(s->left);
//如果左儿子节点空，则找到第一个有右儿子节点的其祖辈节点
BSTree *p = getFather(r,s);
while(p!=NULL&&s==p->left)
{
s=p;
p=getFather(r,s);
}
return p;
}
}
//获得节点中序的后继节点
//此操作不需要遍历树
BSTree *searchPostMidOrder(BSTree *r,int val)
{
BSTree *s = search(r,val);
if(s==NULL)
return NULL;
else
{
//如果右儿子节点非空，则找到右子树的最小值节点
if(s->right!=NULL)
{
return BSTMinNum(s->right);
}
//如果右儿子节点为空，则找到第一个有左儿子节点的其祖辈节点
BSTree *p = getFather(r,s);
while(p!=NULL&&s==p->right)
{
s=p;
p=getFather(r,s);
}
return p;
}
}
//插入操作
BSTree* insert(BSTree *r,BSTree *s)
{
//首先查找树中是否已存在此节点
BSTree *p = search(r,s->data);
if(p==NULL)
{
flag = false;
if(r==NULL)
{
r=s;
}
else if(s->data<r->data)
r->left = insert(r->left,s);
else if(s->data>r->data)
r->right = insert(r->right,s);
}
else
flag = true;
return r;
}
//建树
BSTree * createBSTree(BSTree *r,int *a,int n)
{
int i;
BSTree * t;
t = r;
for(i=0;i<n;i++)
{
BSTree *s = (BSTree*)malloc(sizeof(BSTree));
s->data=a[i];
s->left=NULL;
s->right=NULL;
t = insert(t,s);
}
return t;
}
//删除操作
BSTree * deleteNode(BSTree *r,BSTree *s)
{
//BSTNODE * temp, * tfather, * pf;
BSTree *temp,*father,*sf;
//pf = getfather(p, r);
sf=getFather(r,s);
//被删除结点是叶子结点, 不是根结点
if(s->left==NULL&&s->right==NULL&&sf!=NULL)
//
if(sf->left==s)
sf->left=NULL;
//
else
sf->right=NULL;
//被删除结点是叶子结点,又是根结点
else if(s->left==NULL&&s->right==NULL&&sf==NULL)
r=NULL;
//被删除结点有右孩子,无左孩子.被删结点是根结点
else if(s->left==NULL&&s->right!=NULL&&sf!=NULL)
if(sf->left==s)
sf->left=s->right;
else
sf->right=s->right;
//被删除结点有右孩子,无左孩子.被删结点是根结点
else if(s->left==NULL&&s->right!=NULL&&sf==NULL)
r=s->right;
//被删结点有左孩子,无右孩子.被删结点不是根结点
else if(s->left!=NULL&&s->right==NULL&&sf!=NULL)
if(sf->left==s)
sf->left=s->left;
else
sf->right=s->left;
//被删结点有左孩子,无右孩子.被删结点是根结点
else if(s->left!=NULL&&s->right==NULL&&sf==NULL)
r=s->left;
else if(s->left!=NULL&&s->right!=NULL)
{
temp = s->left;
father = s;
//找出左子树最大的节点
while(temp->right!=NULL)
{
father=temp;
temp=temp->right;
}
s->data = temp->data;
if(father!=s)
father->right = temp->left;
else
father->left=temp->left;
}
if(r==NULL)
cout<<"删除之后，二叉排序树为空！"<<endl;
else
cout<<"删除成功！"<<endl;
return r;
}
//前序输出
void preOrder(BSTree *r)
{
if(r==NULL)
return;
else
{
cout<<r->data<<" ";
preOrder(r->left);
preOrder(r->right);
}
}
//中序输出
void inOrder(BSTree *r)
{
if(r==NULL)
return ;
else
{
inOrder(r->left);
cout<<r->data<<" ";
inOrder(r->right);
}
}
//后续输出
void postOrder(BSTree *r)
{
if(r==NULL)
return ;
else
{
postOrder(r->left);
postOrder(r->right);
cout<<r->data<<" ";
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int cases;
cout<<"请输入案例个数："<<endl;
cin>>cases;
while(cases--)
{
memset(a,0,sizeof(a));
int n;
flag = false;
BSTree *root=NULL;
cout<<"请输入元素个数："<<endl;
cin>>n;
int i;
cout<<"请输入这些元素："<<endl;
for(i=0;i<n;i++)
cin>>a[i];
cout<<"建立二叉排序树!"<<endl;
root = createBSTree(root,a,n);
if(root!=NULL)
cout<<"二叉排序树建立成功！"<<endl;
else
{
cout<<"二叉排序树建立失败！"<<endl;
return 0;
}
cout<<"此二叉树根的值为："<<endl;
cout<<root->data<<endl;
cout<<"请选择您要进行的操作："<<endl;
cout<<"1.插入(I/i)"<<endl;
cout<<"2.查找(S/s)"<<endl;
cout<<"3.删除(D/d)"<<endl;
cout<<"4.先序输出(P/p)"<<endl;
cout<<"5.中序输出(M/m)"<<endl;
cout<<"6.后序输出(L/l)"<<endl;
cout<<"7.退出(E/e)"<<endl;
char s;
cin>>s;
while(1)
{
if(s=='E'||s=='e')
break;
else if(s=='I'||s=='i')
{
cout<<"请输入您要插入的值："<<endl;
int x;
cin>>x;
BSTree *p =(BSTree*)malloc(sizeof(BSTree));
p->data = x;
p->left = NULL;
p->right = NULL;
root = insert(root,p);
if(flag==false)
cout<<"插入成功！"<<endl;
else
{
cout<<"此二叉树中已存在此值！"<<endl;
flag=false;//恢复原值
}
}
else if(s=='S'||s=='s')
{
cout<<"请问您需要查询哪种信息？"<<endl;
cout<<"1.此值的相关信息(1)："<<endl;
cout<<"2.二叉排序树最小值(2)："<<endl;
cout<<"3.二叉排序树最大值(3)："<<endl;
cout<<"4.此值的中序前趋节点值(4)："<<endl;
cout<<"5.此值的中序后继节点值(5)："<<endl;
cout<<"6.退出查询(6)："<<endl;
int cs;
cin>>cs;
while(1)
{
if(cs==1)
{
cout<<"请输入您要查找的值："<<endl;
int x;
cin>>x;
BSTree *p=search(root,x);
BSTree *pfather=getFather(root,p);
cout<<"查找的值为："<<p->data<<endl;
if(pfather!=NULL)
cout<<"其父节点的值为："<<pfather->data<<endl;
else
cout<<"它是根节点，没有父节点！"<<endl;
if(p->left==NULL&&p->right==NULL)
cout<<"它是叶子节点，没有子节点"<<endl;
else
{
if(p->left != NULL)
cout<<"其左儿子节点的值为："<<p->left->data<<endl;
else
cout<<"其左儿子节点为空！"<<endl;
if(p->right != NULL)
cout<<"其右儿子的值为："<<p->right->data<<endl;
else
cout<<"其右儿子节点为空！"<<endl;
}
}
else if(cs==2)
{
BSTree * node = BSTMinNum(root);
cout<<"此二叉排序树的最小值为："<<node->data<<endl;
}
else if(cs==3)
{
BSTree * node = BSTMaxNum(root);
cout<<"此二叉排序树的最大值为："<<node->data<<endl;
}
else if(cs==4)
{
int val;
cout<<"请输入一个值："<<endl;
cin>>val;
BSTree *node = searchPreMidOrder(root,val);
if(node==NULL)
cout<<"不存在此其值为"<<val<<"的节点或其前趋节点"<<endl;
else
{
cout<<"此节点的值为："<<val<<endl;
cout<<"其中序前趋节点的值："<<node->data<<endl;
}
}
else if(cs==5)
{
int val;
cout<<"请输入一个值："<<endl;
cin>>val;
BSTree *node = searchPostMidOrder(root,val);
if(node==NULL)
cout<<"不存在此其值为"<<val<<"的节点或其后继节点"<<endl;
else
{
cout<<"此节点的值为："<<val<<endl;
cout<<"其中序后继节点的值："<<node->data<<endl;
}
}
else if(cs==6)
break;
else
{
cout<<"输入的指令不对，请重新输入！"<<endl;
}
cout<<"请问您需要查询哪种信息？"<<endl;
cin>>cs;
}
}
else if(s=='D'||s=='d')
{
cout<<"请输入您要删除的节点的值："<<endl;
int value;
cin>>value;
cout<<"你确定要删除吗？(Yy/Nn)"<<endl;
char order;
cin>>order;
while(1)
{
if(order=='Y'||order=='y')
{
BSTree * node;
node = search(root,value);
if(node==NULL)
cout<<"该节点不存在！"<<endl;
else
BSTree *nodeDel = deleteNode(root,node);
break;
}
else if(order=='N'||order=='n')
{
break;
}
else
{
cout<<"命令不正确，请重新输入！"<<endl;
cin>>order;
}
}
}
else if(s=='P'||s=='p')
{
cout<<"其前序输出为："<<endl;
preOrder(root);
cout<<endl;
}
else if(s=='M'||s=='m')
{
cout<<"其中序输出为："<<endl;
inOrder(root);
cout<<endl;
}
else if(s=='L'||s=='l')
{
cout<<"其后序输出为："<<endl;
postOrder(root);
cout<<endl;
}
else
{
cout<<"命令有误，请重新输入！"<<endl;
}
cout<<"请选择您要进行的操作："<<endl;
cin>>s;
}
}
system("pause");
return 0;
}
分享到：
相关推荐
以下是二叉排序树的基本操作的C++实现： 1. **插入操作**：在二叉排序树中插入一个新的节点，需要找到合适的插入位置。从根节点开始，如果新键值小于当前节点的键值，就向左子树递归；反之，向右子树递归。直到找到...
在实际编程中，这些概念和方法可以结合C++的面向对象特性进行封装，创建一个二叉排序树类，提供插入、查找、删除等方法，并实现相应的逻辑。通过练习和实践，可以深入理解二叉排序树的工作原理及其在数据结构和算法...
总之，这个C++程序提供了对二叉查找树基本操作的全面实现，包括增删查改以及多种遍历方式，这些功能在实际的编程项目中非常常见，对于理解和掌握数据结构有重要意义。通过阅读和理解这段代码，开发者可以加深对二叉...
这种结构使得二叉排序树在查找、插入和删除操作上有较高的效率。 在给定的场景中，我们需要用C++来处理一个文件，该文件包含不少于100个整型数，并计算这些数在二叉排序树中的平均查找长度。平均查找长度（Average ...
### 二叉查找树的C++实现 #### 一、二叉查找树简介 二叉查找树(Binary Search Tree)，也称作有序或排序二叉树，是一种特殊的二叉树数据结构，其每个节点包含一个键（key）和两个指针（指向左子树和右子树）。对于...
二叉排序树（Binary Sort Tree，BST），也称为二叉查找树或有序二叉树，是一种特殊类型的二叉树，其每个节点的左子树只包含比其小的元素，右子树包含比其大的元素，且整个树保持自平衡。在本实验报告中，我们将深入...
二叉查找树（Binary Search Tree，BST），也称为二叉排序树，是一种特殊的二叉树数据结构，它的每个节点都包含一个键值，且满足以下性质： 1. 节点的左子树只包含键小于当前节点的节点。 2. 节点的右子树只包含键...
二叉查找树的插入、删除、遍历和查找等操作的C++实现，二叉查找树采用泛型结构
在"数据结构实验之二叉排序树"中，我们主要关注的是如何利用二叉排序树实现动态查找、插入和删除操作。动态查找是指在数据结构中搜索特定值的过程，对于二叉排序树，这个过程通常从根节点开始，如果目标值小于当前...
二叉排序树，用前序遍历是就是增序排列，的创建删、插入、查询
二叉排序树（Binary Search Tree，BST），也称为二叉查找树或有序二叉树，是一种自平衡的二叉树数据结构，它在处理搜索、插入和删除操作时具有较高的效率。二叉排序树的主要特点是：对于任意节点，其左子树中的所有...
二叉排序树实现的学生管理 有创建插入 删除 查找等功能
在VC++环境下实现二叉查找树，通常会涉及C++的类封装、指针操作以及递归算法。 首先，我们需要定义一个名为`BstTree`的类，这个类将包含二叉查找树的基本属性和方法。类的定义可能如下： ```cpp class BstTree { ...
在iOS编程中，实现二叉排序树的增删改查操作是数据结构和算法的重要应用。CodeBlocks是一款跨平台的C++集成开发环境，虽然通常用于Windows，但它同样支持创建和调试Objective-C代码，这是iOS开发的主要语言。 ### ...
二叉排序树，又称二叉查找树或二叉有序树，是一种特殊的二叉树数据结构，它的每个节点都满足以下两个性质：1) 左子树中的所有节点的值都小于当前节点的值；2) 右子树中的所有节点的值都大于当前节点的值。这种结构...
本节将详细介绍二叉排序树的编程实现，包括生成、插入、删除等基本操作。 **2.1 数据类型定义** 首先定义一个二叉排序树的节点结构体： ```cpp struct TreeNode { int data; TreeNode* left; TreeNode* right;...
二叉排序树 二叉排序树是一种特殊的二叉树，它的每个节点都满足以下性质：左子树所有节点的值都小于根...通过本实验，我们掌握了二叉排序树的基本操作，如创建、插入、删除、查找等，并了解了二叉排序树的应用场景。
### C++中的二叉排序树算法详解 #### 引言 在计算机科学中，二叉排序树...本篇文章通过分析一段具体的C++代码，深入浅出地介绍了二叉排序树的核心概念和实现细节，希望能帮助读者更好地理解和运用这一数据结构。