编辑代码

/***********************************************************/
/****************   二叉排序树 （143页——145页）**********
		 算法6.13【二叉排序树插入新结点的递归算法】
		 算法6.14【二叉排序树插入新结点的非递归算法】
		 算法6.15【二叉排序树的生成算法】
************************************************************/
#include <stdlib.h>
#include <stdio.h>

/*********二叉排序树的结点类型定义（143页）********************/
typedef int keytype;
typedef int datatype;

typedef struct node {
	keytype key;  //关键字项
	//datatype other;  //其他数据项
	struct node *lchild, *rchild; // 左右指针域
} bstnode;

/******************************************************************
		 算法6.13【二叉排序树插入新结点的递归算法】（144页）
************************************************************/
bstnode *INSERTBST1(bstnode *&t, bstnode *s )

// t为二叉排序树的根指针，s为插入的结点指针
{
	if (t == NULL)
		t = s;    //原树为空, 返回s作为根指针
	else {
		if (s->key < t->key)
			INSERTBST1( t->lchild, s );   //在左子树中查找插入位置　
		else
			INSERTBST1( t->rchild, s );   //在右子树中查找插入位置
	}
	return t;
}//  INSERTBST1

/******************************************************************
		 算法6.14【二叉排序树插入新结点的非递归算法】（144页）
************************************************************/
bstnode *INSERTBST2(bstnode *&t, bstnode *s )

// t为二叉排序树的根指针，s为插入的结点指针
{
	bstnode *f, *p;
	p = t;
	while (p != NULL) {
		f = p;          //f指向*p结点双亲
		if (s->key == p->key)
			return NULL;     //树中已有结点*s，无须插入
		if (s->key < p->key)
			p = p->lchild;    //在左子树中查找插入位置
		else
			p = p->rchild;    //在右子树中查找插入位置
	}
	if (t == NULL) {
		t = s;          //原树为空, 返回s作为根指针
	} else {
		if (s->key < f->key)
			f->lchild = s;   //将*s插入为*f的左孩子　
		else
			f->rchild = s;    //将*s插入为*f的右孩子
	}
	return t;
}//  INSERTBST2


/******************************************************************
		 算法6.15【二叉排序树的生成算法】（144页）
************************************************************/
bstnode *CREATBST( ) {
//生成二叉排序树
	bstnode *t, *s;
	keytype keyvalue, endflag = 0;  //endflag为结点结束标志
	//datatype data;
	t = NULL;    // 设置二叉排序树的初态为空树
	printf("输入结点的关键字值，结束标志为0\n");
	scanf("%d", &keyvalue);     //读入一个结点的关键字
	while (keyvalue != endflag) {  // 输入非结束标志，执行以下操作
		s = (bstnode *)malloc(sizeof(bstnode)); //申请新结点
		s->lchild = s->rchild = NULL;     //新结点指针域置空
		s->key = keyvalue;
		/*
		printf("输入结点的其他数据值\n")
		scanf ("%d", &data);            //读入结点的其他数据
		s->other = data;
		*/
		INSERTBST2(t, s);      //将新结点插入树t中，调用INSERTBST1或INSERTBST2
		scanf("%d", &keyvalue);      //读入下一个结点的关键字
	}
	return t;
}

///*
int SearchBST(bstnode *bt, keytype k) {
//以递归方式输出从根节点到查找到的节点的路径

	if (bt == NULL) {
		return 0;
	} else if (k == bt->key) {
		//printf("%3d %3c", bt->key, bt->other);
		printf("%3d", bt->key);
		return 1;
	} else if (k < bt->key) {
		printf("%3d", bt->key);
		return SearchBST(bt->lchild, k); //在左子树中递归查找
	} else {
		printf("%3d", bt->key);
		return SearchBST(bt->rchild, k); //在右子树中递归查找
	}
}
//*/

void show(bstnode *t) {
	if (t == NULL) {
		return;
	}
	show(t->lchild);
	printf("%3d", t->key);
	show(t->rchild);
}


int main() {
	bstnode *tree;
	tree = CREATBST( );
	printf("生成的二叉排序树为\n");
	show(tree);
	printf("\n");
	keytype val;
	printf("输入要查找的结点\n");
	scanf("%d", &val);
	printf("以递归方式输出从根节点到所查结点%d的路径\n", val);
	SearchBST(tree, val);
	return 0;
}

//测试样例1 (教材第145页图6.20)
// 输入关键字序列  6 2 8 4 9 7 2 0

//测试样例2 (教材第145页图6.20)
// 输入关键字序列  8 4 2 9 6 7 2 0