真颛 -
我也是参考别人的，你参考下：
#include<iostream>
#include<cstdlib>
#include<iomanip>
using namespace std;
const int size=1000;
struct BitNode{
int date;
BitNode *lchild,*rchild;//左右孩子
}*BiTree;
struct Stack{
BitNode *elem[size];
int length;
}S;
struct List{//长度
int elem[size];
int length;
}L;
int InitStack(Stack &L)
{
L.length=0;
return 0;
}
int Push(Stack &L,BitNode *e){//二叉排列数的插入
L.elem[L.length]=e;
L.length++;
return 0;
}
int Pop(Stack &L,BitNode *(&e)){//删除L的栈顶 元素，用e返回其值
e=L.elem[L.length-1];
L.length--;
return 0;
}
int InitList(List &L)
{
L.length=0;
return 0;
}
int ListInsert(int e,List &L)
{
L.elem[L.length]=e;
L.length++;
return 0;
}
bool SearchBst(BitNode *T,int key,BitNode *f,BitNode *(&p))//bool型变量，true or false.
{
if(!T){p=f;return false;}
//else if(T->date==key&&T->lchild!=NULL&&T->lchild->date!=key)
//{p=T; return true;}
else if(T->date<key) {return SearchBst(T->rchild,key,T,p);}
else return SearchBst(T->lchild,key,T,p);
}
int SearchBst_T(BitNode *T,int key,BitNode *f,BitNode *(&p),BitNode *(&q))
{
if(!T){p=f;return false;}
else if(T->date==key)
{q=f;p=T; return true;}
else if(T->date<key) {return SearchBst_T(T->rchild,key,T,p,q);}
else return SearchBst_T(T->lchild,key,T,p,q);
}
int InsertBst(BitNode *(&T),int key){
BitNode *s,*p=NULL;
if(!SearchBst(T,key,NULL,p)){
s=new BitNode;
s->date=key;
s->lchild=s->rchild=NULL;
if(!p) T=s;
else if(p->date<key) p->rchild=s;
else p->lchild=s;
return true;
}
else return false;
}
void output(BitNode *T,List &L,int &i)
{
ListInsert(T->date,L);
}
int InorderTraverse(BitNode *(&T))
{
BitNode *p;
InitStack(S); p=T;
int i=0;
while(p||S.length!=0){
if(p){Push(S,p);p=p->lchild;}
else{
Pop(S,p);
output(p,L,i);
p=p->rchild;
}
}
return true;
}
int Delete(BitNode *(&T))
{
BitNode *p,*q,*s;
int key;
cout<<"请输入删除的数："; //删除节点
cin>>key;
if(SearchBst_T(T,key,NULL,p,q))
{
if(!p->lchild)
{
if(q==NULL)
{
T=p->rchild;
}
else if(p==q->lchild)
{
q->lchild=p->rchild;
}
else if(p==q->rchild)
{
q->rchild=p->rchild;
}
delete(p);
}
else{
q=p;
s=p->lchild;
while(s->rchild){
q=s;
s=s->rchild;
}
p->date=s->date;
if(q!=p){
q->rchild=s->lchild;
}
else{
q->lchild=s->lchild;
}
delete s;
return true;
}
}
else{
cout<<"不存在此数！";
return false;
}
}
int welcome()
{
cout<<"—————请选择数字—————"<<endl;
cout<<"**** 1 二叉排序伪随机数******"<<endl;
cout<<"**** 2 二叉排序树的插入******"<<endl;
cout<<"**** 3 二叉排序树的删除******"<<endl;
cout<<"**** 4 退出******************"<<endl;
cout<<"******************************"<<endl;
}
int main()
{
int n,D,k,flag;
welcome();
while(cin>>flag)
{
InitList(L);
if(flag==1)
{
cout<<"请输入随即数的个数：";
cin>>n;
for(int i=0;i<n;i++)
{
D=1+rand()%1000;
ListInsert(D,L);
}
BiTree=NULL;
for(int j=0;j<L.length;j++)
InsertBst(BiTree,L.elem[j]);
cout<<"---排序前---";
for(k=0;k<L.length;k++)
{
if(k%10==0)
cout<<endl;
cout<<left<<setw(6)<<L.elem[k];
}
InitList(L);
InorderTraverse(BiTree);
cout<<endl<<"---排序后---";
for(k=0;k<L.length;k++)
{
if(k%10==0)
cout<<endl;
cout<<left<<setw(6)<<L.elem[k];
}
cout<<endl<<endl;
}
else if(flag==2)
{
cout<<"请输入插入的数：";
cin>>D;
InsertBst(BiTree,D);
InorderTraverse(BiTree);
cout<<"---插入后---";
for(k=0;k<L.length;k++)
{
if(k%10==0)
cout<<endl;
cout<<left<<setw(6)<<L.elem[k];
}
cout<<endl<<endl;
}
else if(flag==3){
Delete(BiTree);
InorderTraverse(BiTree);
cout<<endl<<"---删除后---";
for(k=0;k<L.length;k++)
{
if(k%10==0)
cout<<endl;
cout<<left<<setw(6)<<L.elem[k];
}
cout<<endl<<endl;
}
else break;
}
return 0;
}
阳光下的日耳曼尼亚 -
我也是参考别人的，你参考下：
#include<iostream>
#include<cstdlib>
#include<iomanip>
using
namespace
std;
const
int
size=1000;
struct
BitNode{
int
date;
BitNode
*lchild,*rchild;//左右孩子
}*BiTree;
struct
Stack{
BitNode
*elem[size];
int
length;
}S;
struct
List{//长度
int
elem[size];
int
length;
}L;
int
InitStack(Stack
&L)
{
L.length=0;
return
0;
}
int
Push(Stack
&L,BitNode
*e){//二叉排列数的插入
L.elem[L.length]=e;
L.length++;
return
0;
}
int
Pop(Stack
&L,BitNode
*(&e)){//删除L的栈顶
元素，用e返回其值
e=L.elem[L.length-1];
L.length--;
return
0;
}
int
InitList(List
&L)
{
L.length=0;
return
0;
}
int
ListInsert(int
e,List
&L)
{
L.elem[L.length]=e;
L.length++;
return
0;
}
bool
SearchBst(BitNode
*T,int
key,BitNode
*f,BitNode
*(&p))//bool型变量，true
or
false.
{
if(!T){p=f;return
false;}
//else
if(T->date==key&&T->lchild!=NULL&&T->lchild->date!=key)
//{p=T;
return
true;}
else
if(T->date<key)
{return
SearchBst(T->rchild,key,T,p);}
else
return
SearchBst(T->lchild,key,T,p);
}
int
SearchBst_T(BitNode
*T,int
key,BitNode
*f,BitNode
*(&p),BitNode
*(&q))
{
if(!T){p=f;return
false;}
else
if(T->date==key)
{q=f;p=T;
return
true;}
else
if(T->date<key)
{return
SearchBst_T(T->rchild,key,T,p,q);}
else
return
SearchBst_T(T->lchild,key,T,p,q);
}
int
InsertBst(BitNode
*(&T),int
key){
BitNode
*s,*p=NULL;
if(!SearchBst(T,key,NULL,p)){
s=new
BitNode;
s->date=key;
s->lchild=s->rchild=NULL;
if(!p)
T=s;
else
if(p->date<key)
p->rchild=s;
else
p->lchild=s;
return
true;
}
else
return
false;
}
void
output(BitNode
*T,List
&L,int
&i)
{
ListInsert(T->date,L);
}
int
InorderTraverse(BitNode
*(&T))
{
BitNode
*p;
InitStack(S);
p=T;
int
i=0;
while(p||S.length!=0){
if(p){Push(S,p);p=p->lchild;}
else{
Pop(S,p);
output(p,L,i);
p=p->rchild;
}
}
return
true;
}
int
Delete(BitNode
*(&T))
{
BitNode
*p,*q,*s;
int
key;
cout<<"请输入删除的数：";
//删除节点
cin>>key;
if(SearchBst_T(T,key,NULL,p,q))
{
if(!p->lchild)
{
if(q==NULL)
{
T=p->rchild;
}
else
if(p==q->lchild)
{
q->lchild=p->rchild;
}
else
if(p==q->rchild)
{
q->rchild=p->rchild;
}
delete(p);
}
else{
q=p;
s=p->lchild;
while(s->rchild){
q=s;
s=s->rchild;
}
p->date=s->date;
if(q!=p){
q->rchild=s->lchild;
}
else{
q->lchild=s->lchild;
}
delete
s;
return
true;
}
}
else{
cout<<"不存在此数！";
return
false;
}
}
int
welcome()
{
cout<<"—————请选择数字—————"<<endl;
cout<<"****
1
二叉排序伪随机数******"<<endl;
cout<<"****
2
二叉排序树的插入******"<<endl;
cout<<"****
3
二叉排序树的删除******"<<endl;
cout<<"****
4
退出******************"<<endl;
cout<<"******************************"<<endl;
}
int
main()
{
int
n,D,k,flag;
welcome();
while(cin>>flag)
{
InitList(L);
if(flag==1)
{
cout<<"请输入随即数的个数：";
cin>>n;
for(int
i=0;i<n;i++)
{
D=1+rand()%1000;
ListInsert(D,L);
}
BiTree=NULL;
for(int
j=0;j<L.length;j++)
InsertBst(BiTree,L.elem[j]);
cout<<"---排序前---";
for(k=0;k<L.length;k++)
{
if(k%10==0)
cout<<endl;
cout<<left<<setw(6)<<L.elem[k];
}
InitList(L);
InorderTraverse(BiTree);
cout<<endl<<"---排序后---";
for(k=0;k<L.length;k++)
{
if(k%10==0)
cout<<endl;
cout<<left<<setw(6)<<L.elem[k];
}
cout<<endl<<endl;
}
else
if(flag==2)
{
cout<<"请输入插入的数：";
cin>>D;
InsertBst(BiTree,D);
InorderTraverse(BiTree);
cout<<"---插入后---";
for(k=0;k<L.length;k++)
{
if(k%10==0)
cout<<endl;
cout<<left<<setw(6)<<L.elem[k];
}
cout<<endl<<endl;
}
else
if(flag==3){
Delete(BiTree);
InorderTraverse(BiTree);
cout<<endl<<"---删除后---";
for(k=0;k<L.length;k++)
{
if(k%10==0)
cout<<endl;
cout<<left<<setw(6)<<L.elem[k];
}
cout<<endl<<endl;
}
else
break;
}
return
0;
}
不白九百 -
本二叉树创建规则， 小于当前节点的数插入当前节点的左子树，大于当前节点的插入右子树，依次类推直到找到对应的节点。
打印的时候，通过递归的方法调用遍历函数，按照先左子树，再本节点，再右子树的方法，从而保证打印出来的数列是排序好了的。
程序运行实际效果：
Input number serials, seperated by white spaces!
1 12312 7 -123 +34 99 100 99 101 [然后回车]
After sorting:
-123 1 7 34 99 100 101 12312
#include <stdio.h>
#include <string.h>
#define MAX_STRING_SIZE (4096)
#define MAX_NODES (100)
typedef struct struc_BTREE_NODE
{
int value;
struct struc_BTREE_NODE * parent;
struct struc_BTREE_NODE * left;
struct struc_BTREE_NODE * right;
} BTREE_NODE;
BTREE_NODE nodes[MAX_NODES];
BTREE_NODE * pTreeTop = NULL;
BTREE_NODE * alloc_node(value)
{
static int occupied_nodes = 0;
BTREE_NODE * pNode;
if(occupied_nodes < MAX_NODES)
{
pNode = &nodes[occupied_nodes++];
pNode->value = value;
pNode->parent = NULL;
pNode->left = NULL;
pNode->right = NULL;
return pNode;
}
else
{
return NULL;
}
}
BTREE_NODE * find_in_tree(int value)
{
BTREE_NODE * pNode = pTreeTop;
if(pNode == NULL)
{
/* tree is empty */
return NULL;
}
while(pNode->value != value)
{
if(pNode->value > value && pNode->left != NULL)
{
pNode = pNode->left;
}
else if(pNode->value < value && pNode->right != NULL)
{
pNode = pNode->right;
}
else
{
break;
}
}
return pNode;
}
void insert_node(int value)
{
BTREE_NODE * pNode;
BTREE_NODE * pParent;
pParent = find_in_tree(value);
if(pParent != NULL && pParent->value == value)
{
return;
}
pNode = alloc_node(value);
if(pNode == NULL)
{
printf("No enough nodes ");
return;
}
if(pParent == NULL)
{
pTreeTop = pNode;
}
else if (pParent->value > value)
{
pParent->left = pNode;
pNode->parent = pParent;
}
else
{
pParent->right = pNode;
pNode->parent = pParent;
}
}
void traverse_tree(BTREE_NODE * pTree)
{
if(pTree == NULL)
{
return;
}
if(pTree->left != NULL)
{
traverse_tree(pTree->left);
}
printf("%d ", pTree->value);
if(pTree->right != NULL)
{
traverse_tree(pTree->right);
}
}
int main()
{
char buffer[MAX_STRING_SIZE];
char * p;
int i, len;
char ch;
printf("Input number serials, seperated by white spaces! ");
len = 0;
while(((ch = getchar()) != " ") && len < MAX_STRING_SIZE)
{
if(ch >= "0" && ch <= "9")
{
buffer[len++] = ch;
}
else
{
switch(ch)
{
case " ":
buffer[len++] = " ";
break;
case "-":
case "+":
buffer[len++] = ch;
break;
default:
printf(" Invalid character! ");
return -1;
}
}
}
buffer[len] = " ";
for(i = 0; i < len; i += (strlen(p)+1))
{
p = &buffer[i];
if(*p != " ")
{
insert_node(atoi(p));
}
}
printf("After sorting: ");
traverse_tree(pTreeTop);
printf(" ");
return 0;
}