二叉树排序算法实现(数据结构课程设计)
下面的程序包含了树二叉树的所有操作
在二叉树的应用中有二叉排序树。
都是C语言,只不过用了C++的cin(输入)和cout(输出),因为这两个不需要格式控制符。
//建一个工程:包含头文件:bittree.h Cpp文件:bittree.cpp main函数:main.cpp
编译运行就可以了。
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//头文件 bittree.h
#ifndef _DEF
#define _DEF
#include
#include
#include
using namespace std;
#define TURE 1
#define OK 1
#define FALSE 0
#define ERROR 0
#define INFEASIBLE -1//不可实行的
#define OVERFLOW -2
typedef int stadus;
typedef char Telemtype;
//typedef int Telemtype2;//为了二叉排序树的创建
typedef char ElemType;
#define STACK_SIZE 100;
#define STACKINCREMENT 10;
//二叉树
typedef struct bitnode{
Telemtype data;
struct bitnode *lchild,*rchild;
}BitNode,*BitTree;
extern stadus CreateBitTree(BitTree &T);
extern stadus PreOrderTraverse(BitTree T);
extern stadus InOrderTraverse(BitTree T);
extern stadus PostOrderTraverse(BitTree T);
typedef BitNode selemtypechar;
typedef BitTree selemtypechar2;
// 栈
typedef struct SqStack{
selemtypechar2 *base;
selemtypechar2 *top;
int stacksize;
}sqstack;
extern stadus initstackC(sqstack &S);
extern stadus gettopC(sqstack S,selemtypechar2 &e);
extern stadus pushC(sqstack &S,selemtypechar2 e);
extern stadus popC(sqstack &S,selemtypechar2 &e);
extern stadus destroyC(sqstack &S);//销毁
extern stadus clearC(sqstack &S);//置空
extern stadus stackempty(sqstack S);
//栈实现二叉树的输出
extern stadus PreOrderTraverse2(BitTree T);
extern stadus InOrderTraverse2(BitTree T);
extern stadus PostOrderTraverse2(BitTree T);
//二叉树的应用
extern stadus Depth(BitTree T);
extern stadus Single(BitTree T);
extern stadus Double(BitTree T);
extern stadus CountLeaf(BitTree T);
extern void Change_Left_Right(BitTree T);
//二叉层次遍历用到队列
typedef BitTree Qelemtype;
typedef struct QNode{
Qelemtype data;
struct QNode *next;
}qnode,*QueuePtr;
typedef struct {
QueuePtr front;
QueuePtr rear;
}LinkQueue;
extern stadus InitQueue(LinkQueue &Q);
extern stadus DestroyQueue(LinkQueue &Q);
extern stadus EnterQueue(LinkQueue &Q,Qelemtype e);
extern stadus DeQueue(LinkQueue &Q,Qelemtype &e);
//二叉层次遍历
extern stadus LevelOrder(BitTree T);
//二叉排序树
extern void insert(BitTree &T,ElemType x);
extern void CreateBiTree2(BitTree &root);
#endif
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//cpp文件 bittree.cpp
#include "bittree.h"
#include
stadus initstackC (sqstack &s)
{
s.base=(selemtypechar2 *)malloc(100*sizeof(selemtypechar));//用STACKINCREMENT会报错???
if (!s.base) exit(OVERFLOW);
s.top=s.base;
s.stacksize=100;
return OK;
}
stadus gettopC(sqstack s,selemtypechar2 &e)
{
if(s.base==s.top) return ERROR;
e=*(s.top-1);
return OK;
}
stadus pushC(sqstack &s,selemtypechar2 e)
{
if ((s.top-s.base)>=s.stacksize)
{
s.base=(selemtypechar2 *)realloc(s.base,((s.stacksize+10)*(sizeof(selemtypechar))));
if(!s.base) exit(OVERFLOW);
s.top=s.base+s.stacksize;
s.stacksize+=10;
}
*(s.top++)=e;
//s.top++;
return OK;
}
stadus popC(sqstack &s,selemtypechar2 &e)
{
if(s.top==s.base) return ERROR;
--s.top;
e=*(s.top);
return OK;
}
stadus destroyC(sqstack &s)
{
free(s.base); s.base=NULL;s.top=NULL;
return OK;
}
stadus clearC(sqstack &s)
{
s.top=s.base;
return OK;
}
stadus stackempty(sqstack s)
{
if(s.top!=s.base) return ERROR;
else
return OK;
}
//二叉树
stadus CreateBitTree(BitTree &T)//创建
{
Telemtype ch;
cin>>ch;
if(ch=='#') T=NULL;
else{
T=(BitTree)malloc(sizeof(BitNode));
if (!T) exit (OVERFLOW);
T->data=ch;
CreateBitTree(T->lchild);
CreateBitTree(T->rchild);
}
return OK;
}
stadus PreOrderTraverse(BitTree T)//先序访问
{
if(!T) return ERROR;
else if (T)
{
coutdata<<" ";
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
return OK;
}
stadus InOrderTraverse(BitTree T)//中序
{
if(!T) return ERROR;
else if (T)
{
InOrderTraverse(T->lchild);
coutdata<<" ";
InOrderTraverse(T->rchild);
}
return OK;
}
stadus PostOrderTraverse(BitTree T)//后序
{
if(!T) return ERROR;
else if (T)
{
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
coutdata<<" ";
}
return OK;
}
//栈实现二叉树的访问
stadus PreOrderTraverse2(BitTree T)//先序
{
sqstack s;
BitTree p;
initstackC(s);
p=T;
//pushC(s,p);
while (p||!stackempty(s))
{
//popC(s,p);
if (p)
{
pushC(s,p);
if(!p->data)return ERROR;
coutdata<<" ";
//p1=p;
p=p->lchild;
if (p==NULL)
{
popC(s,p);
p=p->rchild;
}
else
pushC(s,p);
}
else {
popC(s,p);
popC(s,p);
p=p->rchild;
if (p==NULL)
{
popC(s,p);
if (p==NULL)
{
return OK;
}
else
{
p=p->rchild;
}
}
else{
pushC(s,p);
if(!p->data)return ERROR;
coutdata<<" ";
p=p->lchild;//左空不压栈
if (p==NULL)
{
popC(s,p);
p=p->rchild;
}
else
pushC(s,p);
}
}
}
destroyC(s);
return OK;
}
stadus InOrderTraverse2(BitTree T)//中序
{
sqstack s;
BitTree p;
initstackC(s);
p=T;
while (p||!stackempty(s))
{
if (p)
{
pushC(s,p);
p=p->lchild;
}
else {
popC(s,p);
if(!p->data)return ERROR;
coutdata<<" ";
p=p->rchild;
}
}
destroyC(s);
return OK;
}
stadus PostOrderTraverse2(BitTree T)//后序
{
sqstack s;
BitTree p;
initstackC(s);
p=T;
while (p||!stackempty(s))
{
if (p)
{
pushC(s,p);
p=p->lchild;
if (p==NULL)
{
popC(s,p);
//p=p->rchild;
if (p->rchild==NULL)
{
if(!p->data)return ERROR;
coutdata<<" ";
//p=p->rchild;
popC(s,p);
if (p==NULL)
{
return OK;
}
else
{
//pushC(s,p);//???右结点重复压栈???
//p1=p;
p=p->rchild;
//p->rchild=NULL;
}
}
else
{
p=p->rchild;
}
}
else
continue ;
}
else
{
//popC(s,p);
if(!p->data)return ERROR;
coutdata<<" ";
popC(s,p);
if (p==NULL)
{
return OK;
}
else
{
//pushC(s,p);
//p1=p;
p=p->rchild;
//p->rchild=NULL;
}
}
}
destroyC(s);
return OK;
}
//二叉树的应用
//二叉树的深度
stadus Depth(BitTree T)
{
int depthval,depthLeft,depthRight;
if (!T) depthval=0;
else{
depthLeft=Depth(T->lchild);
depthRight=Depth(T->rchild);
depthval=1+(depthLeft>depthRight?depthLeft:depthRight);
}
return depthval;
}
//二叉树的单分支结点数
stadus Single(BitTree T)
{
if (T==NULL) return 0; //空树
else if (T->lchild==NULL && T->rchild==NULL) return 0; //叶子结点
else{
if (!T->lchild && T->rchild) return Single(T->rchild)+1;//只有左单分支
if (T->lchild && !T->rchild) return Single(T->lchild)+1;//只有右单分支
if(T->lchild && T->rchild) return Single(T->lchild)+Single(T->rchild);//双分支结点
}
}
//二叉树的多分支结点数
stadus Double(BitTree T)
{
if (T==NULL) return 0; //空树
else if (T->lchild==NULL && T->rchild==NULL) return 0; //叶子结点
else{
if (!T->lchild && T->rchild) return Double(T->rchild);//只有左单分支
if (T->lchild && !T->rchild) return Double(T->lchild);//只有右单分支
if(T->lchild && T->rchild) return Double(T->lchild)+Double(T->rchild)+1;//双分支结点
}
}
//叶子结点
stadus CountLeaf(BitTree T)
{
int num,num1,num2;
if(T==NULL) num=0;
else if(T->lchild==NULL&&T->rchild==NULL)
num=1;
else
{
num1=CountLeaf(T->lchild);
num2=CountLeaf(T->rchild);
num=num1+num2;
}
return num;
}
//交换左右子树
void Change_Left_Right(BitTree T)
{
BitTree Temp;
if (T)
{
Change_Left_Right(T->lchild);
Change_Left_Right(T->rchild);
Temp=T->lchild;
T->lchild=T->rchild;
T->rchild=Temp;
}
}
//二叉层次遍历用到队列
stadus InitQueue(LinkQueue &Q)
{
Q.front=Q.rear=(QueuePtr)malloc(100*sizeof(qnode));
if(!Q.front) exit(OVERFLOW);
Q.front->next=NULL;
return OK;
}
stadus DestroyQueue(LinkQueue &Q)
{
while (Q.front)
{
Q.rear=Q.front->next;
free(Q.front);
Q.front=Q.rear;
}
return OK;
}
stadus EnterQueue(LinkQueue &Q,Qelemtype e)
{
QueuePtr p;
p=(QueuePtr)malloc(sizeof(qnode));
if(!p) return ERROR;
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return OK;
}
stadus DeQueue(LinkQueue &Q,Qelemtype &e)
{ QueuePtr p;
if(Q.front==Q.rear) return ERROR;
p=Q.front->next;e=p->data;
Q.front->next=p->next;
if(Q.rear==p)Q.rear=Q.front;
free(p);
return OK;
}
//二叉层次遍历
stadus LevelOrder(BitTree T)
{
LinkQueue Q;
BitTree B;
InitQueue(Q);
if (T!=NULL)
{
EnterQueue(Q,T);
while (!(Q.front==Q.rear))
{
DeQueue(Q,B);
coutdata<<" ";
if(B->lchild!=NULL) EnterQueue(Q,B->lchild);
if(B->rchild!=NULL) EnterQueue(Q,B->rchild);
}
}
return OK;
}
//二叉排序树
void insert(BitTree &T,ElemType x)
{
if (T==NULL)
{
T=(BitTree)malloc(sizeof(BitNode));
T->data=x;
T->lchild=T->rchild=NULL;
}
else
{
if(xdata)insert(T->lchild,x);
if(x>=T->data)insert(T->rchild,x);
}
}
void CreateBiTree2(BitTree &root)
{
ElemType x;
root=NULL;
cout"<<endl;
cout"<<endl;
cin>>x;
while (x!='#')
{
insert(root,x);
cin>>x;
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//主函数 main.cpp
#include "bittree.h"
void main()
{
system("cls");
system("color f0");
BitTree T;
Create:
cout:"<<endl;
CreateBitTree(T);
BitTree T1(T);
select:
cout<<''<<''<<"----------------MAIN-MENU----------------"<<endl;
cout<<''<<''<<"&1、先序输出 2、中序输出 3、后序输出 &"<<endl;
cout<<''<<''<<"&4、栈实现输出 5、重新创建二叉树 0、退出&"<<endl;
cout<<''<<''<<"------------6、二叉树的应用-------------"<<endl;
char sel;
getchar();
cin>>sel;
switch (sel)//总
{
case '0':
break;
case '1':cout<<endl<<"---------------------------------"<<endl;
PreOrderTraverse(T);
cout<<endl<<"---------------------------------"<<endl;
goto select;
case '2':cout<<endl<<"---------------------------------"<<endl;
InOrderTraverse(T);
cout<<endl<<"---------------------------------"<<endl;
goto select;
case '3':cout<<endl<<"---------------------------------"<<endl;
PostOrderTraverse(T);
cout<<endl<<"---------------------------------"<<endl;
goto select;
case '4':
stackcout:
cout<<endl<<''<<" -------------------SUB-MENU1---------------------"<<endl;
cout<<''<<" &1、先序输出 2、中序输出 3、后序输出 4、返回 &"<<endl;
cout<<''<<" ------------------------------------------------"<<endl;
cin>>sel;
switch (sel)//栈关于树的输出
{
case '1':cout<<endl<<"---------------------------------"<<endl;
PreOrderTraverse2(T1);//p->lchild==null,时 T 的值被修改!!!!!!!!
cout<<endl<<"---------------------------------"<<endl;
goto stackcout;
case '2':cout<<endl<<"---------------------------------"<<endl;
InOrderTraverse2(T);
cout<<endl<<"---------------------------------"<<endl;
goto stackcout;
case '3':cout<<endl<<"---------------------------------"<<endl;
PostOrderTraverse(T1);//栈实现未写完
cout<<endl<<"---------------------------------"<<endl;
goto stackcout;
case '4':goto select;
default:cout<<"选择错误!!!"<<endl;
goto stackcout;
}
case '5':
goto Create;
case '6':
{
SUB_MENU2:
cout<<''<<''<<"-------------------------SUB-MENU2---------------------"<<endl;
cout<<''<<''<<"&1、二叉树的深度 2、二叉树的单分支结点数 &"<<endl;
cout<<''<<''<<"&3、二叉树的多分支结点数 4、二叉树的叶子结点数 &"<<endl;
cout<<''<<''<<"&5、二叉层次遍历 6、二叉排序树 7、交换左右子树 &"<<endl;
cout<<''<<''<<"&------------------8、输出 0、返回--------------------&"<<endl;
cin>>sel;
switch (sel)//二叉树的应用
{
case '0':
goto select;
case '1':
{
int deepth=0;
deepth=Depth(T);
cout<<endl<<"---------------------------------"<<endl;
cout<<"树的深度为:"<<deepth<<endl;
cout<<endl<<"---------------------------------"<<endl;
}
goto SUB_MENU2;
case '2':
{
int cou_sig;
cou_sig=Single(T);
cout<<endl<<"---------------------------------"<<endl;
cout<<"此树的单分支结点为数:"<<cou_sig<<endl;
cout<<endl<<"---------------------------------"<<endl;
}
goto SUB_MENU2;
case '3':
{
int cou_dou;
cou_dou=Double(T);
cout<<endl<<"---------------------------------"<<endl;
cout<<"此树的双分支结点数为:"<<cou_dou<<endl;
cout<<endl<<"---------------------------------"<<endl;
}
goto SUB_MENU2;
case '4':
{
int cou_leaf;
cou_leaf=CountLeaf(T);
cout<<endl<<"---------------------------------"<<endl;
cout<<"此树的叶子结点数为:"<<cou_leaf<<endl;
cout<<endl<<"---------------------------------"<<endl;
}
goto SUB_MENU2;
case '5':
{
cout<<"二叉层次遍历的结果为:"<<endl;
cout<<endl<<"---------------------------------"<<endl;
LevelOrder(T);
cout<<endl<<"---------------------------------"<<endl;
}
goto SUB_MENU2;
case '6':
{
BitTree T3;
CreateBiTree2(T3);
SUB3:
cout<<''<<"-------------------------SUB-MENU2-------------------"<<endl;
cout<<''<<" &1、先序输出 2、中序输出 3、后序输出 0、返回 &"<<endl;
cout<<''<<"-----------------------------------------------------"<<endl;
cin>>sel;
switch (sel)//二叉树的层次遍历
{
case '0':
break;
case '1':cout<<endl<<"---------------------------------"<<endl;
PreOrderTraverse(T3);
cout<<endl<<"---------------------------------"<<endl;
goto SUB3;
case '2':cout<<endl<<"---------------------------------"<<endl;
InOrderTraverse(T3);
cout<<endl<<"---------------------------------"<<endl;
goto SUB3;
case '3':cout<<endl<<"---------------------------------"<<endl;
PostOrderTraverse(T3);
cout<<endl<<"---------------------------------"<<endl;
goto SUB3;
default:
cout<<"选择错误!!!"<<endl;
goto SUB3;
}
}
goto SUB_MENU2;
case '7':
{
Change_Left_Right(T);
cout<<endl<<"---------------------------------"<<endl;
cout<<"交换完成,请选择8输出查看!!!"<<endl;
cout<<endl<<"---------------------------------"<<endl;
}
goto SUB_MENU2;
case '8':
goto select;
default:
cout<<"选择错误!!!"<<endl;
goto SUB_MENU2;
}
}
break;
default :
cout<<endl<<"选择错误!!!"<<endl;
goto select;
}
}
晕了,真是好纠结,我在写完下面的代码后,才在网上找了找,居然发现和你的题目完全一样的代码,算了,我就直接发在网上找到的文档和代码给你吧,可怜我写了这么久代码呀。。。。。已发,请注意查收。
代码写好了。
VC下经测试通过。
不过如果你还要论文之类的或者设计文档,我也比较难帮到你了。
#include
using namespace std;
class node
{
public:
node(int i):data(i),left(NULL),right(NULL){}
void inorder(node *&root) //中序遍历,符合升序输出
{
if(root!=NULL)
{
inorder(root->left);
coutdata<<' ';
inorder(root->right);
}
}
void insert(node *&ptr,int item) //在查找树中插入元素
{
if(ptr==NULL)
ptr=new node(item);
else if(itemdata)
insert(ptr->left,item);
else insert(ptr->right,item);
}
node *find(node *&ptr,int item) //在查找树中查找元素,找到返回所在结点指针,找不到返回空指针。
{
if(ptr==NULL)
return NULL;
if(ptr->data==item)
return ptr;
else if(itemdata)
find(ptr->left,item);
else find(ptr->right,item);
}
node *&findy(node *&ptr,int item) //在查找树中查找肯定存在的元素,并返回其引用
{
if(ptr->data==item)
return ptr;
else if(itemdata)
findy(ptr->left,item);
else findy(ptr->right,item);
}
node* rl(){return left;}
node* rr(){return right;}
void dele(node *&ptr) //删除值为item所在结点
{
if(ptr->rl()==NULL&&ptr->rr()==NULL)
ptr=NULL;
else if(ptr->rr()==NULL)
ptr=ptr->rl();
else
ptr=ptr->rr();
}
private:
int data;
node *left; //左孩子结点
node *right; //右孩子结点
};
int main()
{
int t,i=0,j;
cout<<"输入数字个数(结点个数):";
cin>>t;
cout<<"输入"<<t<<"个数字,数字之间用空格隔开:";
cin>>j;
node *x=new node(j);
for(;i<t-1;i++)
{
cin>>j;
x->insert(x,j);
}
cout<<"中序遍历为:";
x->inorder(x); //作中序遍历
cout<<"
输入操作(当输入-1时程序结束):"<<endl;
cin>>j;
while(j!=-1)
{
node *t=x->find(x,j); //定位结点
if(t!=NULL)
{
node *&y=x->findy(x,j);
x->dele(y);
cout<<"中序遍历为:";
x->inorder(x);
}
else cout<<"无"<<j;
cout<<"
输入操作(当输入-1时程序结束):"<<endl;
cin>>j;
}
return 0;
}
附测试数据一组
8
22 33 1 50 88 99 77 55
33
50
51
55
-1
有什么不明的话可以M我或者留言我。
#include<stdio.h>
#define NUM 7 //宏定义
int i; //变量类型定义
typedef struct Node{
int data ; //数据域
struct Node *next; //指针域
}Node,*LNode; //用结构体构造结点及相应的指针
typedef struct Tree{
int data ;
struct Tree *left ;
struct Tree *right ;
}Tree,*LTree ; //用结构体构造树及相应的指针
CreateList( LNode Head ) //创建单链表
{
for(int i=1 ; i <=NUM ; i++) //创建循环,依次输入NUM个数据
{
LNode temp ; //中间结点
temp = (LNode) malloc( sizeof( Node ) ); //动态存储分配
temp-> next = NULL; //中间结点初始化
scanf("%2d",&temp-> data); //输入赋值到结点temp数据域
temp-> next = Head-> next ;
Head-> next = temp ; //将temp结点插入链表
}
return 1 ;//返回1
}
InsertSqTree( LTree &root , LNode temp ) //二叉树排序原则的设定
{
if(!root) //root为NULL时执行
{
root = (LTree)malloc(sizeof(Tree)); //动态存储分配
root-> left =NULL;
root-> right=NULL; //初始化
root-> data = temp-> data ; //赋值插入
return 1 ; //函数正常执行,返回1
}
else
{
if(root-> data>= temp-> data)
return InsertSqTree( root-> left , temp ) ; //比较插入左子树
else if(root-> data <temp-> data)
return InsertSqTree( root-> right , temp ); //比较插入右子树
}
return 1 ; //如果满足,就不做处理,返回1
}
void BianLiTree(LTree root) //采用中序遍历,实现将所有数字按从左向右递增的顺序排序
{
if(root) //root不为空执行
{BianLiTree(root-> left); //左递归处理至叶子结点,当root-> left为NULL时不执行
printf("%4d ",root-> data); //输出
BianLiTree(root-> right); //处理右结点
}
}
int main()
{
LNode Head = NULL;
LTree root = NULL ; //初始化
Head = (LNode) malloc(sizeof(Node)); //动态存储分配
Head-> next = NULL ; //初始化
printf("please input numbers:\n");//输入提示语句
if(!CreateList( Head )) //建单链表成功返回1不执行下一语句
return 0; //结束函数,返回0
LNode temp = Head-> next ; //将头指针的指针域赋值予中间结点
while( temp ) //temp为NULL时停止执行
{
if(!InsertSqTree( root ,temp )) //排序正常执行,返回1不执行下一语句
return 0 ; //结束函数,返回0
Head-> next = temp-> next ; //将中间指针的指针域赋值予头结点指针域
free(temp); //释放空间
temp = Head-> next ; //将头指针的指针域赋值予中间结点,以上三句实现了temp指针后移
}
printf("the result is:\n");//输出提示语句
BianLiTree(root); //采用中序遍历,输出并观察树结点
return 1; //函数正常结,返回1
}
/*以下是用c++ 实现的二叉排序树的源代码*/
#include<iostream.h>
typedef struct TreeNode
{
int key;
struct TreeNode *left;
struct TreeNode *right;
}treeNode;
class BiSortTree
{
public:
BiSortTree(void);
void desplayTree(void);//显示这个树
void insertTree(int key);//在树中插入一个值
deleteTree(int key);//在树中删除一个值
treeNode* searchTree(int key);//在树中查找一个值
~BiSortTree();
private:
treeNode* buildTree(treeNode* head,int number);//建立一个树
treeNode* search(treeNode* head ,int key);//查找
treeNode* BiSortTree::searchParent(treeNode* head,treeNode* p);//查找出p的父亲节点的指针
treeNode* BiSortTree::searchMinRight(treeNode* head);//找到右子树中最小的节点
void showTree(treeNode* head);//显示
void destroyTree(treeNode* head);//删除
treeNode *Head;
};
/**************以下是建立一个二叉排序树****************/
BiSortTree::BiSortTree()
{
cout<<"建立一棵二叉排序树,请输入你要建树的所有数(以-1 作为结束标志!): "<<endl;
Head=NULL;
int number;
cin>>number;
while(number!=-1)
{
Head=buildTree(Head,number);
cin>>number;
}
}
treeNode* BiSortTree::buildTree(treeNode* head,int number)
{
treeNode *p;
p=new treeNode;
p->key=number;
p->left =p->right=NULL;
if(head==NULL)
{
return p;
}
else
{
if(p->key <head->key)
head->left=buildTree(head->left,number);
else
head->right=buildTree(head->right,number);
return head;
}
}
/*****************以下是在一棵二叉排序树插入一个数***********************************/
void BiSortTree::insertTree(int key)
{
Head=buildTree(Head,key);
}
/*****************以下是在一个二叉排序树查找一个数是否存在*************************/
treeNode* BiSortTree::searchTree(int key)
{
return search(Head,key);
}
treeNode* BiSortTree::search(treeNode* head ,int key)
{
if(head==NULL)
return NULL;
if(head->key==key)
return head;
else
{
if(key<head->key )
return search( head->left,key);
else
return search(head->right,key);
}
}
/************以下是在一个二叉排序树删除一个给定的值*********************************/
BiSortTree::deleteTree(int key)
{
treeNode *p;
p=NULL;
p=search(Head,key);
if(p==NULL)
{
cout<<"Don't find the key";
}
if(p==Head)
{
Head=NULL;
}
else
{
treeNode* parent;
parent=searchParent(Head,p);
if(p->left==NULL&&p->right==NULL)//叶子节点
{
if(parent->left==p)
{
parent->left=NULL;
}
else
{
parent->right=NULL;
}
}
else//非叶子节点
{
if(p->right==NULL)//该节点没有右孩子
{
if(parent->left==p)
{
parent->left=p->left ;
}
else
{
parent->right=p->left;
}
}
else//该点有左右孩子
{
treeNode * rightMinSon,* secondParent;//secondParent为右子树中的最小节点的父亲
rightMinSon=searchMinRight(p->right);
secondParent=searchParent(p->right ,rightMinSon);
secondParent->left=rightMinSon->right;
if(p->right==rightMinSon)//右子树中的最小节点的父亲为p
{
p->right=rightMinSon->right ;
}
p->key=rightMinSon->key ;
}
}
}
}
treeNode* BiSortTree::searchParent(treeNode* head,treeNode* p)
{
if(head->left==p||head->right==p||head==p||head==NULL)
return head;
else
{
if(p->key<head->key)
return searchParent(head->left ,p);
else
return searchParent(head->right ,p);
}
}
treeNode* BiSortTree::searchMinRight(treeNode* head)//找到右子树中最小的节点
{
if(head->left ==NULL||head==NULL)
{
return head;
}
else
{
return searchMinRight(head->left);
}
}
/*****************以下是显示一个二叉排序树****************************************/
void BiSortTree::desplayTree(void)
{
showTree(Head);
cout<<endl;
}
void BiSortTree::showTree(treeNode* Head)
{
if(Head!=NULL)
{
showTree(Head->left ) ;
cout<<Head->key<<' ' ;
showTree(Head->right) ;
}
}
/*****************以下是删除一棵整二叉排序树************************************/
BiSortTree::~BiSortTree()
{
cout<<"已经消除了一棵树!!!!"<<endl;
destroyTree(Head);
}
void BiSortTree::destroyTree(treeNode* head )
{
if(head!=NULL)
{
destroyTree(head->left );
destroyTree(head->right );
delete head;
}
}
/*********************/
void print()
{
cout<<endl<<endl<<"以下是对二叉排序树的基本操作:"<<endl
<<"1.显示树"<<endl
<<"2.插入一个节点"<<endl
<<"3.寻找一个节点"<<endl
<<"4.删除一个节点"<<endl;
}
void main()
{
BiSortTree tree;
int number;
int choiceNumber;
char flag;
while(1)
{
print() ;
cout<<"请选择你要进行的操作(1~4)"<<endl;
cin>>choiceNumber;
switch(choiceNumber)
{
case 1:
tree.desplayTree();break;
case 2:
cout<<"请插入一个数: "<<endl;
cin>>number;
tree.insertTree(number);
tree.desplayTree();
break;
case 3:
cout<<"请插入你要找数: "<<endl;
cin>>number;
if(tree.searchTree(number)==NULL)
{
cout<<"没有发现"<<endl;
}
else
{
cout<<"发现"<<endl;
}
break;
case 4:
cout<<"请输入你要删除的数: "<<endl;
cin>>number;
tree.deleteTree(number);
tree.desplayTree();
break;
default: break;
}
cout<<"你是否要继续(Y/N)?"<<endl;
cin>>flag;
if(flag=='N'||flag=='n')
break;
}
}
八大经典排序算法原理及实现
该系列文章主要是记录下自己暑假这段时间的学习笔记,暑期也在实习,抽空学了很多,每个方面的知识我都会另起一篇博客去记录,每篇头部主要是另起博客的链接。冒泡排序算法应该是大家第一个接触的算法,其原理都应该懂,但我还是想以自己的语言来叙述下其步奏:按照计算时间复杂度的规则,去掉常数、去掉最...
排序算法python实现
选择排序算法 选择排序是一种简单直观的排序算法,无论什么数据进去都是 O(n?) 的时间复杂度。所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间。插入排序算法 插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴,但它的原理应该是最容易理解的了,因为只要打过扑克...
面试必会八大排序算法(Python)
排序演示 选择排序的示例动画。红色表示当前最小值,黄色表示已排序序列,蓝色表示当前位置。算法实现 六、堆排序 介绍 堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。利用数组的特点快速指定索引的元素。基本思想 堆分为大根堆和小根堆,是完全二叉树。...
设计一个算法从二叉树中来查找给定节点的双亲结点
\/\/ 创建二叉树是按照"二叉排序树"的原则,例如:\/\/ 输入序列20 15 10 12 18 25 30 16 17, 第1个数据是20,作为根结点,\/\/ 第2个数据是15,比20小,作为20的左分支,第3个数据是10,比20和15小,\/\/ 作为15的左分支,第4个数是12,比20和15小,但比10大,作为10的右分支,\/\/ 如此类推,创建...
已知T为一棵二叉排序树设计算法按递减次序打印各节点的值
中序遍历,用栈可以。二叉排序树递减次序打印 include <stdio.h> int InsertBST(BSTNode *&p,KeyType k){ if (p==NULL) \/\/原树为空,新插入的记录为根结点 return InsertBST(p->lchild,k); \/\/插入到*p的左子树中 else return InsertBST(p->rchild,k); \/\/插入到*p的右子树中 BSTNod...
排序算法学习分享(一)选择排序
与选择排序相比,堆排序的高效率在于其利用了堆的特性,每次操作都能减少排序的复杂性。堆排序就像一个精巧的魔术,通过局部调整,实现了全局的有序。总的来说,选择排序以其直观易懂的步骤展示了排序的基本原理,而堆排序则通过堆的智慧,提升了排序的效率。两者都是排序算法家族中的瑰宝,值得我们深入...
C语言二叉树排序的一道题目
include<stdio.h> include<stdlib.h> define Maxsize 100 typedef char elemtype;typedef struct node { elemtype data;struct node* lchild;struct node* rchild;}BTNode;include<stdio.h> include<stdlib.h> define Maxsize 100 typedef char elemtype;int BTWidth(BTNode *b){ struct { int lno;...
大学要学会这8种算法程序员
算法一: 快速排序算法 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序n个项目要O(nlogn)次比较。在最坏状况下则需要O(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他O(nlogn)算法更快,因为它的内部循环 (innerloop)可以在大部分的架构上很有效率地被实现出来。
c++之数据排序
各种排序算法的比较1.稳定性比较 插入排序、冒泡排序、二叉树排序、二路归并排序及其他线形排序是稳定的。 选择排序、希尔排序、快速排序、堆排序是不稳定的。2.时间复杂性比较 插入排序、冒泡排序、选择排序的时间复杂性为O(n2);快速排序、堆排序、归并排序的时间复杂性为O(nlog2n);桶排序的时间复杂性为O(n)...
如何用Python实现八大排序算法
希尔排序是非稳定排序算法。该方法因DL.Shell于1959年提出而得名。 希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。代码实现def shell_sort(lists)...
侯质上生: #include <malloc.h> #include<stdio.h> #define NUM 7 //宏定义 int i; //变量类型定义 typedef struct Node{int data ; //数据域struct Node *next; //指针域 }Node,*LNode; //用结构体构造结点及相应的指针typedef struct Tree{int data ;struct ...
冕宁县13145625496: 数据结构课程设计:二叉排序树的实现 - ?
侯质上生: /*以下是用c++ 实现的二叉排序树的源代码*/#include<iostream.h> typedef struct TreeNode { int key; struct TreeNode *left; struct TreeNode *right;}treeNode;class BiSortTree { public:BiSortTree(void); void desplayTree(void);//显示这个树 void ...
冕宁县13145625496: 数据结构课程设计(C版语言)二叉排序树算法 - ?
侯质上生: #include<stdio.h>#include<stdlib.h>#include<conio.h> typedef int DataType; //定义数据类型,以int为例 struct BSTNode //定义二叉排序树节点类型 { DataType data; struct BSTNode *lchild,*rchild; }; int insert(struct BSTNode **root,DataType data...
冕宁县13145625496: 二叉排序树的实现 用顺序和二叉链表作存储结构 数据结构课程设计?
侯质上生: Program p6_6(Input, Output); Type tree=^node; node=Record data:Integer; lchild,rchild:tree; End; Var bt:tree; n:Integer; Procedure creat_order_tree(Var btx:tree;nx:Integer); Var p,s,f:tree; flag:Boolean; Begin New(s); s^.data:=nx; s^.lchild:=Nil; s^....
冕宁县13145625496: 二叉排序树的构造与运算 (数据结构C语言版)课程设计 - ?
侯质上生: //木有wint-tc,没运行,不好意思.以前写的,楼主看能用否.#include<stdio.h>#include<stdlib.h> typedef struct BiT{ char data; struct BiT *lchild; struct BiT *rchild; }BiT; BiT* CreateBiTree(BiT *T) { //构造二叉链表表示的二叉树T char ch; scanf("%c...
冕宁县13145625496: 二叉排序树问题,课程设计采用顺序存储方式或二叉链表存储方式保存二叉排序树?
侯质上生: #include<stdio.h> #include<stdlib.h> typedef struct node { int data; node *left; node *right; }node; node* CreateTree(node *root,int n) { if(root==NULL) { root=(node *)malloc(sizeof(node)); root->data=n; root->left=NULL; root->right=...
冕宁县13145625496: c++ 数据结构 课程设计 - ?
侯质上生: 1、起泡排序 算法:核心思想是扫描数据清单,寻找出现乱序的两个相邻的项目.当找到这两个项目后,交换项目的位置然后继续扫描.重复上面的操作直到所有的项目都按顺序排好 bubblesort(struct rec r[],int n) { int i,j; struct rec w; unsigned ...
冕宁县13145625496: 数据结构 课程设计 二叉树操作?
侯质上生: #include <stdio.h> #include <malloc.h> #define MaxSize 100 typedef char ElemType; typedef struct node { ElemType data; struct node *lchild; struct node *rchild; }BTNode; void CreateBTNode(BTNode *&b,char *str) { BTNode *St[MaxSize],*p=NULL...
冕宁县13145625496: 求高手帮我做份数据结构课程设计的详细答案{二叉排序树操作},我们要交作业,做的好,我把分都给你!! - ?
侯质上生: #include "stdio.h"#include"stdlib.h"#include typedef struct BTREE {char data;struct BTREE *left;struct BTREE *right; } BTNode,*BTree; BTree node; void createBST(BTree *T, char ord); BTree createBT() { BTree *T,t; int tong,i; t=(BTree)...
冕宁县13145625496: 课程设计任务书:构建一棵二叉排序树的C程序的设计 - ?
侯质上生: 好吧,程序我帮你写好了,功能完全能按你的要求来实现. VC下通过. #include <stdio.h> #include <stdlib.h>struct node {node(int i):data(i),left(NULL),right(NULL){}int data;node *left; //左孩子结点node *right; //右孩子结点void inorder(...