Question

二叉排序树的实现 用顺序和二叉链表作存储结构

（1）以回车('\n')为输入结束标志,输入数列L，生成一棵二叉排序树T；
（2）对二叉排序树T作中序遍历，输出结果；
（3）输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”。
网上的都看过了 也不行 自己改改也没改出来 都怪自己平时不好好学习 现在急了两天以后就要交了 哪位可以帮忙回复一下 发送到zi_qing2008@126.com C或c++都可以 谢谢了

Answer 1

#include<stdio.h>
#include <stdlib.h>
typedef struct Tnode
{
int data;
struct Tnode *lchild,*rchild;
}*node,BSTnode;

searchBST(node t,int key,node f,node *p)
{
if(!t) {*p=f;return (0);} /*查找不成功*/
else if(key==t->data) {*p=t;return (1);} /*查找成功*/
else if(key<t->data) searchBST(t->lchild,key,t,p); /*在左子树中继续查找*/
else searchBST(t->rchild,key,t,p); /*在右子树中继续查找*/
}

insertBST(node *t,int key)
{
node p=NULL,s=NULL;
if(!searchBST(*t,key,NULL,&p)) /*查找不成功 */
{
s=(node)malloc(sizeof(BSTnode));
s->data=key;
s->lchild=s->rchild=NULL;
if(!p) *t=s; /*被插入节点*s为新的根节点*/
else if(key<p->data) p->lchild=s; /*被插节点*s为左孩子*/
else p->rchild=s; /*被插节点*s为右孩子*/
return (1);
}
else return (0); /*树中已有关键字相同的节点，不再插入*/
}

inorderTraverse(node *t) /*中序遍历*/
{
if(*t){
if(inorderTraverse(&(*t)->lchild))
{
printf("%d ",(*t)->data);
if(inorderTraverse(&(*t)->rchild));
}
}
else return(1);
}

node Delete(node t,int key)
{ /*若二叉排序树t中存在关键字等于key的数据元素时，则删除该数据元素节点
*/
node p=t,q=NULL,s,f;
while(p!=NULL)
{ if(p->data==key) break;
q=p;
if(p->data>key) p=p->lchild;
else p=p->rchild;
}
if(p==NULL) return t;
if(p->lchild==NULL)
{ if(q==NULL) t=p->rchild;
else if(q->lchild==p) q->lchild=p->rchild;
else q->rchild=p->rchild;
free(p);
}
else{ f=p;
s=p->lchild;
while(s->rchild)
{ f=s;
s=s->rchild; }
if(f==p) f->lchild=s->lchild;
else f->rchild=s->lchild;
p->data=s->data;
free (s);
} return t;
}

void main()
{
node T=NULL;
int num;
int s=0,j=0,i=0;
int ch=0;
node p=NULL;
printf("请输入一组数字并输入0为结束符,生成一棵二叉排序树T:\n");
do{
scanf("%d",&num);
if(!num) printf("你成功完成了输入!\n");
else insertBST(&T,num);
}
while(num);
printf("\n\n---操作菜单---\n");
printf("\n 0: 退出" );
printf("\n 1: 中序遍历");
printf("\n 2: 查找删除");
printf("\n--------------");

while(ch==ch)
{
printf("\n\n 选择操作并继续:");
scanf("%d",&ch);
switch(ch){
case 0: exit(0); /*0－－退出*/
case 1: printf(" 中序遍历结果是:\n ");
inorderTraverse(&T);
break;

case 2: printf(" 请输入你想删除的数字:");
scanf("%d",&num);
if(searchBST(T,num,NULL,&p))
{
T=Delete(T,num);
printf(" 你已成功删除该数字!\n ");
printf(" 删除该数字后的中序遍历结果为:\n ");
inorderTraverse(&T);
}
else printf(" 没有你想要删除的节点 %d!",num);
break;

default: printf("你的输入有误!请重新输入!\n");
break;
}
}
}

Answer 2

ude"string.h"
#include<stdlib.h>
#define Max 20 //结点的最大个数
typedef struct node{
char data;
struct node *lchild,*rchild;
}BinTNode; //自定义二叉树的结点类型
typedef BinTNode *BinTree; //定义二叉树的指针
int NodeNum,leaf; //NodeNum为结点数，leaf为叶子数
//==========基于先序遍历算法创建二叉树==============
//=====要求输入先序序列，其中加入虚结点"#"以示空指针的位置==========
BinTree CreatBinTree(void)
{
BinTree T;
char ch;
if((ch=getchar())=='#')
return(NULL); //读入#，返回空指针
else{
T=(BinTNode *)malloc(sizeof(BinTNode)); //生成结点
T->data=ch;
T->lchild=CreatBinTree(); //构造左子树
T->rchild=CreatBinTree(); //构造右子树
return(T);
}
}
//========NLR 先序遍历=============
void Preorder(BinTree T)
{
if(T) {
printf("%c",T->data); //访问结点
Preorder(T->lchild); //先序遍历左子树
Preorder(T->rchild); //先序遍历右子树
}
}
//========LNR 中序遍历===============

void Inorder(BinTree T)

{
if(T){
Inorder(T->lchild);
printf("%c",T->data);
Inorder(T->rchild);
}
}
//==========LRN 后序遍历============
void Postorder(BinTree T)
{
if(T){
Postorder(T->lchild);
Postorder(T->rchild);
printf("%c",T->data);
}
}

//=====采用后序遍历求二叉树的深度、结点数及叶子数的递归算法========

int hl,hr,max;TreeDepth(BinTree T)

{
if(T){
hl=TreeDepth(T->lchild); //求左深度
hr=TreeDepth(T->rchild); //求右深度
max=hl>hr? hl:hr; //取左右深度的最大值

NodeNum=NodeNum+1; //求结点数
if(hl==0&&hr==0) leaf=leaf+1; //若左右深度为0，即为叶子。
return(max+1);
}
else return(0);
}

//====利用"先进先出"（FIFO）队列，按层次遍历二叉树==========
void Levelorder(BinTree T)
{
int front=0,rear=1;
BinTNode *cq[Max],*p; //定义结点的指针数组cq
cq[1]=T; //根入队
while(front!=rear)
{
front=(front+1)%NodeNum;
p=cq[front]; //出队
printf("%c",p->data); //出队，输出结点的值
if(p->lchild!=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->lchild; //左子树入队
}
if(p->rchild!=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->rchild; //右子树入队
}
}
}

//==========主函数=================

void main()
{
BinTree root;
int i,depth;
printf("\n");
printf("Creat Bin_Tree； Input preorder:"); //输入完全二叉树的先序序列，
// 用#代表虚结点，如ABD###CE##F##
root=CreatBinTree(); //创建二叉树，返回根结点
do { //从菜单中选择遍历方式，输入序号。
printf("\t********** select ************\n");
printf("\t1: Preorder Traversal\n");
printf("\t2: Iorder Traversal\n");
printf("\t3: Postorder traversal\n");
printf("\t4: PostTreeDepth,Node number,Leaf number\n");
printf("\t5: Level Depth\n"); //按层次遍历之前，先选择4，求出该树的结点数。
printf("\t0: Exit\n");
printf("\t*******************************\n");
scanf("%d",&i); //输入菜单序号（0-5）
switch (i){
case 1: printf("Print Bin_tree Preorder: ");
Preorder(root); //先序遍历
break;
case 2: printf("Print Bin_Tree Inorder: ");
Inorder(root); //中序遍历
break;
case 3: printf("Print Bin_Tree Postorder: ");
Postorder(root); //后序遍历
break;
case 4: depth=TreeDepth(root); //求树的深度及叶子数
printf("BinTree Depth=%d BinTree Node number=%d",depth,NodeNum);
printf(" BinTree Leaf number=%d",leaf);
break;
case 5: printf("LevePrint Bin_Tree: ");
Levelorder(root); //按层次遍历
break;
default: exit(1);
}
printf("\n");
} while(i!=0);
}

Answer 3

C我很久不用了