/* 二叉排序树 建立一个空二叉排序树，输入一串数据（以-9999 结尾），输出前序和中序遍历。 其中：输入数据均为整数，输入时以空格分开。 编一C 程序，它能把读入的整数依次插入到一个初始为空的二叉排序树中，一直读到-9999 为止。 再从该二叉排序树中删除读入的第三个整数，之后输出该二叉排序树的前序序列、中序序列及叶 结点 的个数。 （输入时，两 个相 邻的整数用 空格隔 开）。 */ #include #include typedef int KeyType;//关键字 类型 typedef struct node { KeyType key;//关键字 项 struct node *lchild, *rchild;//左 右 孩 子 指 针 }BSTNode; typedef BSTNode *BSTree; void InsertBST(BSTree *root, KeyType key) { BSTNode *f, *p = *root; while(p) { if(p->key == key) { return; } f = p; p = (key < p->key) ? p->lchild : p->rchild; } p = (BSTNode *)malloc(sizeof(BSTNode)); p->key = key; p->lchild = p->rchild = NULL; if(*root == NULL)//树为空 { *root = p; } else if(f->key > key) { f->lchild = p; } else { f->rchild = p; } } BSTree CreateBST() { BSTree root = NULL; KeyType key; printf("开始创建二叉排序树:"); scanf("%d", &key); while(key) { InsertBST(&root, key); scanf("%d", &key); } return root; } //前序遍历 void PreOrder(BSTree T) { if(T) { printf("%d ", T->key); PreOrder(T->lchild); PreOrder(T->rchild); } } //中序遍历 void InOrder(BSTree T) { if(T) { InOrder(T->lchild); printf("%d ", T->key); InOrder(T->rchild); } } //后序遍历 void PostOrder(BSTree T) { if(T) { PostOrder(T->lchild); PostOrder(T->rchild); printf("%d ", T->key); } } void main() { BSTree T = CreateBST(); printf("前序遍历:"); PreOrder(T); printf("中序遍历:"); InOrder(T); printf("后序遍历:"); PostOrder(T); printf("¥n"); system("pause"); } /*
