题目：构造一棵二叉排序树并对其进行中序遍历输出；在二叉排序树中查找某一关键字，若存在，显示查找成功；若不存在，将其插入到二叉排序树中，再中序遍历输出
//文件名：BiSortTree.h #pragma once #ifndef _BISORTTREE_H_ #define _BISORTTREE_H_ #include <stdio.h> #include <stdlib.h> #define MAX_SIZE 100 #define EQ(a,b) (!cmp((a),(b))) #define LT(a,b) (cmp((a),(b)) < 0) #define GT(a,b) (cmp((a),(b)) > 0) typedef int TElemType; typedef struct BiTNode { TElemType data; struct BiTNode *lchild, *rchild; }BiTNode, *BiTree; /* 比较函数cmp */ double cmp(double a, double b) { return a - b; } /* 搜索二叉树，返回bool */ bool SearchBST(BiTree T, TElemType key, BiTree f, BiTree & p) { if (!T)//空则返回false, p为双亲节点，方便插入 { p = f; return false; } else if (EQ(key, T->data))//找到结点，返回true，p为当前结点 { p = T; return true; } else if (LT(key, T->data))//小于时，查找左树 { SearchBST(T->lchild, key, T, p); } else//大于，查找又树 { SearchBST(T->rchild, key, T, p); } } /* 结点的插入 函数名：InsertBST 参数：BiTree & T, ELemType temp; */ bool InsertBST(BiTree & T, TElemType temp) { BiTree p; if (SearchBST(T, temp, NULL, p))//先查找是否树中已存在temp return false;//存在则返回false else {//不存在则开始进行插入操作 BiTree s = (BiTree)malloc(sizeof(BiTNode));//建立新节点，将temp放入新节点s中 s->data = temp; s->lchild = s->rchild = NULL; if (!p)//若是空树，直接将新节点s作为树 { T = s; } else if (LT(temp, p->data))//根据大小选择插入左子树还是右子树 {//大于右子树 p->lchild = s; } else {//小于左子树 p->rchild = s; } return true; } } /* 随机生成二叉排序树 函数名：RandCreatBiSortTree 参数：BiTree & T, int time（生成的结点数） */ BiTree RandCreatBiSortTree(BiTree & T, int time) { int temp; printf("生成数为："); for (int i = 0; i < time; i++) { temp = rand() % 50;//设置0到50的随机数 printf("%d ", temp); InsertBST(T, temp); } printf("\n"); return T; } /* 树的中序遍历输出 函数名：InOrderTraversal 参数：BiTree BT */ void InOrderTraversal(BiTree BT) { int top = 0; BiTree stack[MAX_SIZE], T = BT; while (T||top) { if (T) { stack[top++] = T; T = T->lchild; } else { T = stack[--top]; printf("%d ", T->data); T = T->rchild; } } printf("\n"); } #endif // !_BISORTT1REE_H_ //文件名：BiSortTree.cpp // BiSortTree.cpp: 定义控制台应用程序的入口点。 // #include "stdafx.h" #include"BiSortTree.h" #include<stdlib.h> int main() { BiTree T = NULL; RandCreatBiSortTree(T, 10); printf("二叉排序树的中序遍历结果如下：\n"); InOrderTraversal(T); system("pause"); return 0; }