二叉树排序算法实现（数据结构课程设计）

Question

总体设计：设计单向链表实现二叉树的创建及排序；
要求： （1）设计单向链表，能够将一组数字(数量为2的N次方)顺序构建一个满二叉树。
（2）对该二叉树进行排序，要求实现将所有数字按照从左向右递增的顺序排序实现；
邮箱：[email protected] 最好发到邮箱，注明用户名即可

Answer 1

#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 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
}

Answer 2

/*以下是用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;

}

}