二叉树的基本操作及打印

　　二叉树是数据结构中的重要内容之一，这里把自己做的一个练习题目写出来，方便回顾和交流。程序使用C语言实现，使用的IDE是Visual Studio 2010。

要求：

随机生成N个整数，N>20，建立二叉排序树；以树的形式输出建立好的二叉排序树删除第十个输入的数据，并以树的形式输出以后的二叉排序树

---

1、建立并生成二叉树

首先，定义一个二叉树的结构体：

//定义二叉排序树节点结构 typedef struct BiTNode { char data; //存储数据 struct BiTNode *lchild, *rchild; //左右孩子指针 }BiTNode, *BiTree; BiTree T; //定义二叉排序树T

插入操作：

因为生成二叉树需要调用，插入函数就先写在这里。

void Insert(BiTree &BST,BiTNode *s) { BiTree t; t = SearchBST(BST, s->data); //若s的关键字不在T中出现，则插入 if (!t) { if (BST == NULL) BST = s; //空树时作为根节点 else if (s->data<BST->data) Insert(BST->lchild, s); //将s插入T的左子树 else Insert(BST->rchild, s); //将s插入T的右子树 } }

生成二叉排序树：

采用头插法，即从根部开始调用Insert()函数实现。

BiTree Create(int n, int *num) { //建立n个关键字的二叉排序树 //用Insert函数插入，再返回根结点T int i; BiTree s; T = NULL; //空树 for (i = 0; i<n; i++) { s = (BiTree)malloc(sizeof(BiTNode)); s->data = num[i]; s->lchild = NULL; s->rchild = NULL; Insert(T, s); //插入 } return T; }

---

2、二叉树基本操作

查找操作：

//查找二叉树中元素 BiTree SearchBST(BiTree BST, int key) { //在根指针T中递归查找关键字等于key的数据元素 //如果如果成功返回该元素结点的指针，否则返回空指针 BiTree s; if (BST == NULL) return NULL; if (BST->data == key) s = BST; else if (BST->data>key) //key小于当前节点的关键字，则查找左子树 s = SearchBST(BST->lchild, key); else s = SearchBST(BST->rchild, key); return s; }

二叉树遍历：

//前序遍历二叉树 void prorder(BiTree &BT) { if (BT != NULL) { printf("= ", BT->data); //访问结点 prorder(BT->lchild); prorder(BT->rchild); } }

删除二叉排序树中的节点:

//从二叉树中删除任意结点，其关键字为x int DeleteBT(BiTree *BT,int key) { if(!*BT) return 0;//不存在关键字等于key的数据元素 else { if(key==(*BT)->data) return Delete(BT); else if(key<(*BT)->data) return DeleteBT(&(*BT)->lchild,key); else return DeleteBT(&(*BT)->rchild,key); } } //删除结点 int Delete(BiTree *p) { BiTree q,s; if((*p)->rchild==NULL) //没有右孩子 { q=*p; *p=(*p)->lchild; free(q); } else if((*p)->lchild==NULL) //没有左孩子 { q=*p; *p=(*p)->rchild; free(q); } else //左右子树均不为空 { q=*p; s=(*p)->lchild; while(s->rchild) { q=s; s=s->rchild; } (*p)->data=s->data; //s指向被删除结点的直接前驱 if(q!=*p) q->rchild=s->lchild; //重建q的右子树 else q->lchild=s->lchild; //重建q的左子树 free(s); } return 1; }

---

3、打印树形

//以树的形式输出二叉排序树 void Paint(BiTree BT,int x,int y,int g) { char c[3]; int right = 0, left = 0; if (BT) { setcolor(WHITE); circle(x, y, 10); Sleep(ms); //将相应数字转化为字符 c[0] = BT->data / 10 + 48; c[1] = BT->data % 10 + 48; c[2] = '\0'; outtextxy(x-7, y-6, c); Sleep(ms); if (BT->lchild != NULL) { if (x>g) left = (x - g) / 2 + g; if (x<g) left = (x - g) / 2 + x; line(x - 3, y, left, y + 50); Sleep(ms); } if (BT->rchild != NULL) { if(BT->lchild!=NULL)right=2*x-left; else { if(x<g) right =(x+g)/2; else right=x+40; } line(x + 3, y, right, y + 50); Sleep(ms); } Paint(BT->lchild, left, y + 50, x); Paint(BT->rchild, right, y + 50, x); } } //前序遍历二叉树 void prorder(BiTree &BT) { if (BT!= NULL) { printf("= ", BT->data); //访问结点 prorder(BT->lchild); prorder(BT->rchild); } }

4、数组操作

为了存储和管理输入数据，增加两个与数组相关的函数

//产生n个不重复的随机数 void Createnum(int n, int *num) { int vol, i, j, flag; //产生随机数，存储在num数组中 for (i = 0; i<n; i++) { vol = rand() % 100; flag = 1; //判断生成的数是否重复 for (j = 0; j < i; j++) { if (vol == num[j]){ flag = 0; break; } } if (flag) num[i] = vol; else --i; } //生成100以内的整数 } //将数组中的数输出 void show_num(int n, int *num) { int i; for (i = 0; i<n; i++) { printf("= ", num[i]); if ((i + 1) % 5 == 0) printf("\n"); } //输出生成的25个整数 }

5、主函数

void main() { int x, y, g; int i, a, b, c; int num[100]; //输入n上限为100 int gdriver, gmode; x = 320, y = 30, g = 0; gdriver = DETECT; while (1) { //创建二叉排序树 printf("随机生成多少数? "); scanf_s("%d", &b); srand(time(NULL)); //设置随机数种子 Createnum(b, num); printf("所有随机数为：\n"); show_num(b, num); printf("\n按任意键开始生成二叉排序树 "); getchar(); T = Create(b, num); if (T != NULL) printf("生成成功！"); else { printf("生成失败！"); break; } printf("\n前序遍历结果：（ENTER）"); getchar(); prorder(T); //打印树形 printf("\n按任意键开始打印树形"); getchar(); // BGI 格式的初始化图形设备，长*宽，flag initgraph(800, 550, 0); setbkcolor(0); //设置背景颜色 cleardevice(); //清屏 Paint(T, x, y, g); getchar(); closegraph(); //关闭窗口 //删除过后打印树形 printf("请输入要删除的数的序号： "); scanf_s("%d", &a); DeleteBT(&T, num[a - 1]); initgraph(800, 550, 0); setbkcolor(0); //设置背景颜色 cleardevice(); //清屏 Paint(T, x, y, g); getchar(); getchar(); closegraph(); //关闭窗口 printf("前序遍历结果：（ENTER）"); getchar(); prorder(T); printf("是否继续？"); scanf_s("%d", &c); if (!c) break; system("cls"); } system("pause"); }

6、运行结果

　　生成二叉树并打印出树的形状：

　　删除节点，输入序号是10，也就是上面输出数组的第十个元素，注意，这里的标号是从1开始的，所以删除了值为64的节点。

　　输出新的前序遍历结果，可以观察到与刚开始结果的变化，最后键入1重新开始，键入0结束。

注意事项

　　由于画图操作中用到一些以前Dos界面上的函数，在VS2010等新版的环境中不支持（虽然我试了老版本的VC++等也不支持，但百度上是么说的）。这里需要安装一个EasyX的插件，这里附上下载链接：http://download.csdn.net/detail/qq_28292827/9686820