从键盘读入一串整数构造一棵二叉排序树，并对得到的二叉排序述进行中序遍历，得到有序序列。
#include
#include
typedef int TElemType;
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
int InitBiTree(BiTree *T)
{
*T = NULL;
return 1;
}
int SearchBST(BiTree T,TElemType e,BiTree f,BiTree *p)
{
if(!T)
{
*p = f;
return 0;
}
else
{
if(e==T->data)
{
*p = T;
return 1;
}
else
if(edata)
return SearchBST(T->lchild,e,T,p);
else
return SearchBST(T->rchild,e,T,p);
}
}
int InsertBST(BiTree *T,TElemType e)
{
BiTree s,p;
if(!SearchBST(*T,e,NULL,&p))
{
s = (BiTree)malloc(sizeof(BiTNode));
s->data = e;
s->lchild = s->rchild = NULL;
if(!p)
*T = s;
else
{
if(edata)
p->lchild = s;
else
p->rchild = s;
}
return 1;
}
else
return 0;
}
int Visit(TElemType e)
{
printf("%d ",e);
return 1;
}
int InOrderTraverse(BiTree T,int (* Visit)(TElemType e))//递归中序遍历二叉树
{
if(T)
{
if(InOrderTraverse(T->lchild,Visit))
if(Visit(T->data))
if(InOrderTraverse(T->rchild,Visit))
return 1;
return 0;
}
else
return 1;
}
int CreateBST(BiTree *T)
{
TElemType e;
scanf("%d",&e);
while(e!=-1)
{
InsertBST(T,e);
scanf("%d",&e);
}
return 1;
}
void main()
{
BiTree T;
InitBiTree(&T);
CreateBST(&T);
InOrderTraverse(T,Visit);
}
此定义为递归式定义。
二叉排序树又称二叉查找树，它可以是一棵空树，若非空时具有下述性质：
1、若根结点的左子树非空，则左子树上所有结点的关键字值均小于等于根结点的关键字值。
2、若根结点的右子树非空，则右子树上所有结点的关键字值均大于等于根结点的关键字值。
3、根结点的左、右子树也分别为二叉排序树。
二叉排序树建立说明：
当需要插入一个节点到二叉排序树时，需要先找到它的父节点。
其实 它就是用插入的节点不断的和每一个节点比较（第一次当然是和根节点比较啦），如果小于等于则进入左边子树，再与左边子树的根节点比较，直到找到它要放的位置，否则进入右子树，进行上述操作。
下面是我写的程序，是控制台下的程序：
#include
#include
using namespace std;
typedef struct node
{
int element;
struct node* left;
struct node* right;
}Node,*NodePtr;
void insertNode(NodePtr *head,int data)//插入节点，注意这用了指向指针的指针，很有意思
{
if (*head==NULL)
{
*head=new Node;
(*head)->element=data;
(*head)->left=NULL;
(*head)->right=NULL;
}
else
{
if (dataelement)
{
insertNode(&((*head)->left),data);
}
else
{
insertNode(&((*head)->right),data);
}
}
}
NodePtr creatTree()//构造二叉排序树，控制台下输入整数，0表示结束输入
{
NodePtr head=NULL;
int data;
scanf("%d",&data);
while(data!=0)
{
insertNode(&head,data);
scanf("%d",&data);
}
return head;
}
void printTree(NodePtr head)//中序遍历二叉排序树，得到有序序列
{
if(head!=NULL)
{
printTree(head->left);
printf("%d ",head->element);
printTree(head->right);
}
}
int main()
{
NodePtr head;
printf("请输入一串整数，空格隔开，0表示输入结束
");
head=creatTree();
printf("中序遍历二叉排序树
");
printTree(head);
printf("
");
return 0;
}
运行结果：
不知道符合你要求没，有问题可以hi我。
说明：为了保证输入的数据按要求构造出想要的、唯一确定的二叉树的形状，这里输入要求利用广义表的形式，虽然会显得繁琐一点，但足以保证严谨性。否则只是单纯一串数字，树形就能千变万化，不一定的。
#include <stdio.h>
#include <malloc.h>
#define MaxSize 10
#define Number 30
struct BiTNode{//定义数据结构
char data;
BiTNode *lchild,*rchild;
};
void InitBtree(BiTNode * &BT){//初始化二叉树
BT=NULL;
}
void CreateBiTree(BiTNode *&BT,char *str){//建立二叉树
BiTNode *s[MaxSize];
int top=-1;
BT=NULL;
BiTNode *p=NULL;
int k, j=0;
char ch;
ch=str[j];
while(ch!='\0'){
switch(ch){
case '(':
top++;
s[top]=p;
k=1;
break;
case ')':
top--;
break;
case ',':
k=2;
break;
default:
p=(struct BiTNode *) malloc(sizeof(struct BiTNode));
p->data=ch;
p->lchild=p->rchild=NULL;
if(BT==NULL)
BT=p;
else{
if(k==1)
s[top]->lchild=p;
else
s[top]->rchild=p;
}
}
j++;
ch=str[j];
}
}
void PrintBtree(BiTNode *BT){//输出二叉树
if(BT!=NULL){
putchar(BT->data);
if(BT->lchild!=NULL||BT->rchild!=NULL){
putchar('(');
PrintBtree(BT->lchild);
if(BT->rchild!=NULL)
putchar(',');
PrintBtree(BT->rchild);
putchar(')');
}
}
}
void inorder(BiTNode *BT){//中序遍历二叉树
if(BT!=NULL){
inorder(BT->lchild );
printf("%c ",BT->data);
inorder(BT->rchild );
}
}
void DeleteBtree(BiTNode *BT){//删除二叉树的所有的节点
if(BT!=NULL){
DeleteBtree(BT->lchild );
DeleteBtree(BT->rchild );
free(BT);
}
}
void ClearBtree(BiTNode *&BT){//清除二叉树
DeleteBtree(BT);
BT=NULL;
}
void main(){
BiTNode *BT,*BT1;
char c;
printf("请以广义表形式输入一个二叉数 （如A(B(C,D),E(,F))的形式）\n\n");
char string[Number]="A(B(,C),D(E(F),G(,H)))";
/*char string[Number],ch;
int i=0;
ch=getchar();
while(ch!='\n' && i<Number){
string[i]=ch;
i++;
ch=getchar();
}
string[i]='\0';
*///想要按要求自己输入只需去掉此部分的注释即可
printf("这里为了减少重复输入，测试采用默认的输入：\n");
InitBtree(BT);
CreateBiTree(BT,string);
PrintBtree(BT);
printf("\n\n\n中序遍历二叉树顺序为： ");
inorder(BT);
printf("\n\n");
ClearBtree(BT);
scanf("%c",&c );
}
从键盘读入一串整数构造一棵二叉排序树,并对得到的二叉排序述进行中序...
void ClearBtree(BiTNode *&BT){\/\/清除二叉树 DeleteBtree(BT);