binary_tree.cpp

C++的电子教程

//程序实例7_3
//二叉排序树
#include <stdio.h>
#include <stdlib.h>
//定义结点
typedef struct node
{
	int data;
	struct node *left;
	struct node *right;
}NODE;

//向二叉树排序树插入结点
void insert(NODE **t,NODE* s) 
{	if(*t==NULL)
		*t=s;  //将s所指结点作为根结点
	else
	{	if(s->data==(*t)->data) return;//表明同样值的结点已经存储
		else if(s->data < (*t)->data)
			insert(&((*t)->left),s);
		else 
			insert(&((*t)->right),s);
	}
}

//二叉树的生成
void create(NODE **root)
{	int x;
	NODE* s;
	printf("\n Input data (Exit for -1) : ");
	scanf("%d",&x);
	while(x!=-1)
	{	s=(NODE *)malloc(sizeof(NODE));
		s->data=x;
		s->left=NULL;
		s->right=NULL;
		insert(root,s);
		scanf("%d",&x);
	}
}

//中序遍历
void midorder(NODE *T)
{	if(T)
	{	midorder(T->left);
		printf("[%3d]",T->data);
		midorder(T->right);
	}
}

//二叉树中结点的删除
NODE* Delete(NODE *t,int x)
{	NODE *f, *r ,*p=t;    //p指向数值为x的结点
	f=NULL;  //指向p的父结点
	while(p!=NULL && p->data!=x) //查找值为x的结点
		if(x<p->data)
		{	f=p; 	p=p->left;	}
		else
		{	f=p;		p=p->right;	}

	if(p==NULL) 	printf("%d not found !\n",x);
	else if(p->left==NULL)  //被删除结点无左子树
	{	if(f==NULL)	
            t=p->right;   //p为根结点,其右子树作为新的根结点
		else if(f->left==p)	
            f->left=p->right;   //p为父结点的左子树
		else		
            f->right=p->right;  //p为父结点的右子树
	}
	else  //被删除结点有左子树
	{	r=p->left;
		while(r->right!=NULL)  r=r->right;   //找到最右边的结点
		r->right=p->right;   //把p的右子树作为r的右子树
		if(f==NULL)	
            t=p->left;   //p为根结点,其左子树作为新的根结点
		else if(f->left==p)	
            f->left=p->left;   //p为父结点的左子树
		else
			f->right=p->left;//p为父结点的右子树
	}
	free(p);	return t;
}

//二叉排序树的嵌套括号输出
void Print(NODE* b)
{	if(b!=NULL)
	{	printf("%d",b->data);
		if(b->left!=NULL || b->right!=NULL)
			printf("(");
		if(b->left)
		{	Print(b->left);
			if(b->right) printf(",");
			else printf(")");
		}
		if(b->right)
		{	
			Print (b->right);
			printf(")");
		}
	}
}

//主函数
void main()
{
	int y;
    NODE *root=NULL;

	printf("\n创建一棵二叉排序树！");
	create(&root);

	printf("二叉排序树中序序列为：");
	midorder(root);
	printf("\n");

	printf("二叉排序树的嵌套括号输出为：");
	Print(root);
    printf("\n");

	printf("要删除的值为：");
	scanf("%d",&y);
    root=Delete(root,y);
	printf("删除结点二叉排序树中序序列为：");
	midorder(root);
	printf("\n");

	printf("删除结点二叉排序树的嵌套括号输出为：");
	Print(root);
    printf("\n");
}