下载文档原格式
题目:二叉排序树的实现1 内容和要求1）编程实现二叉排序树，包括生成、插入，删除；2）对二叉排序树进展先根、中根、和后根非递归遍历；3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。
4）分别用二叉排序树和数组去存储一个班(50 人以上)的成员信息(至少包括学号、姓名、成绩3 项),比照查找效率，并说明在什么情况下二叉排序树效率高,为什么?2 解决方案和关键代码2.1 解决方案：先实现二叉排序树的生成、插入、删除，编写DisplayBST函数把遍历结果用树的形状表示出来。
前中后根遍历需要用到栈的数据构造，分模块编写栈与遍历代码。
要求比照二叉排序树和数组的查找效率，首先建立一个数组存储一个班的成员信息，分别用二叉树和数组查找，利用clock〔〕函数记录查找时间来比照查找效率。
2.2关键代码树的根本构造定义及根本函数typedef struct{KeyType key;} ElemType;typedef struct BiTNode//定义链表{ElemType data;struct BiTNode *lchild, *rchild;}BiTNode, *BiTree, *SElemType;//销毁树int DestroyBiTree(BiTree &T){if (T != NULL)free(T);return 0;}//清空树int ClearBiTree(BiTree &T){if (T != NULL){T->lchild = NULL;T->rchild = NULL;T = NULL;}return 0;}//查找关键字,指针p返回int SearchBST(BiTree T, KeyType key, BiTree f, BiTree &p) {if (!T){p = f;return FALSE;}else if EQ(key, T->data.key){p = T;return TRUE;}else if LT(key, T->data.key)return SearchBST(T->lchild, key, T, p);elsereturn SearchBST(T->rchild, key, T, p);}二叉树的生成、插入，删除生成void CreateBST(BiTree &BT, BiTree p){int i;ElemType k;printf("请输入元素值以创立排序二叉树:\n");scanf_s("%d", &k.key);for (i = 0; k.key != NULL; i++){//判断是否重复if (!SearchBST(BT, k.key, NULL, p)){InsertBST(BT, k);scanf_s("%d", &k.key);}else{printf("输入数据重复！\n");return;}}}插入int InsertBST(BiTree &T, ElemType e){BiTree s, p;if (!SearchBST(T, e.key, NULL, p)){s = (BiTree)malloc(sizeof(BiTNode));s->data = e;s->lchild = s->rchild = NULL;if (!p)T = s;else if LT(e.key, p->data.key)p->lchild = s;elsep->rchild = s;return TRUE;}else return FALSE;}删除//某个节点元素的删除int DeleteEle(BiTree &p){BiTree q, s;if (!p->rchild) //右子树为空{q = p;p = p->lchild;free(q);}else if (!p->lchild) //左子树为空{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;if (q != p)q->rchild = s->lchild;elseq->lchild = s->lchild;delete s;}return TRUE;}//整棵树的删除int DeleteBST(BiTree &T, KeyType key) //实现二叉排序树的删除操作{if (!T){return FALSE;}else{if (EQ(key, T->data.key)) //是否相等return DeleteEle(T);else if (LT(key, T->data.key)) //是否小于return DeleteBST(T->lchild, key);elsereturn DeleteBST(T->rchild, key);}return 0;}二叉树的前中后根遍历栈的定义typedef struct{SElemType *base;SElemType *top;int stacksize;}SqStack;int InitStack(SqStack &S) //构造空栈{S.base = (SElemType*)malloc(STACK_INIT_SIZE *sizeof(SElemType));if (!S.base) exit(OVERFLOW);S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK;}//InitStackint Push(SqStack &S, SElemType e) //插入元素e为新栈顶{if (S.top - S.base >= S.stacksize){S.base = (SElemType*)realloc(S.base, (S.stacksize + STACKINCREMENT)*sizeof(SElemType));if (!S.base) exit(OVERFLOW);S.top = S.base + S.stacksize;S.stacksize += STACKINCREMENT;}*S.top++ = e;return OK;}//Pushint Pop(SqStack &S, SElemType &e) //删除栈顶,应用e返回其值{if (S.top == S.base) return ERROR;e = *--S.top;return OK;}//Popint StackEmpty(SqStack S) //判断是否为空栈{if (S.base == S.top) return TRUE;return FALSE;}先根遍历int PreOrderTraverse(BiTree T, int(*Visit)(ElemType e)) {SqStack S;BiTree p;InitStack(S);p = T;while (p || !StackEmpty(S)){if (p){Push(S, p);if (!Visit(p->data)) return ERROR;p = p->lchild;}else{Pop(S, p);p = p->rchild;}}return OK;}中根遍历int InOrderTraverse(BiTree T, int(*Visit)(ElemType e)) {SqStack S;BiTree p;InitStack(S);p = T;while (p || !StackEmpty(S)){if (p){Push(S, p);p = p->lchild;}else{Pop(S, p);if (!Visit(p->data)) return ERROR;p = p->rchild;}}return OK;}后根遍历int PostOrderTraverse(BiTree T, int(*Visit)(ElemType e)) {SqStack S, SS;BiTree p;InitStack(S);InitStack(SS);p = T;while (p || !StackEmpty(S)){if (p){Push(S, p);Push(SS, p);p = p->rchild;}else{if (!StackEmpty(S)){Pop(S, p);p = p->lchild;}}}while (!StackEmpty(SS)){Pop(SS, p);if (!Visit(p->data)) return ERROR;}return OK;}利用数组存储一个班学生信息ElemType a[] = { 51, "陈继真", 88,82, "黄景元", 89,53, "贾成", 88,44, "呼颜", 90,25, "鲁修德", 88,56, "须成", 88,47, "孙祥", 87, 38, "柏有患", 89, 9, " 革高", 89, 10, "考鬲", 87, 31, "李燧", 86, 12, "夏祥", 89, 53, "余惠", 84, 4, "鲁芝", 90, 75, "黄丙庆", 88, 16, "李应", 89, 87, "杨志", 86, 18, "李逵", 89, 9, "阮小五", 85, 20, "史进", 88, 21, "秦明", 88, 82, "杨雄", 89, 23, "刘唐", 85, 64, "武松", 88, 25, "李俊", 88, 86, "卢俊义", 88, 27, "华荣", 87, 28, "杨胜", 88, 29, "林冲", 89, 70, "李跃", 85, 31, "蓝虎", 90, 32, "宋禄", 84, 73, "鲁智深", 89, 34, "关斌", 90, 55, "龚成", 87, 36, "黄乌", 87, 57, "孔道灵", 87, 38, "张焕", 84, 59, "李信", 88, 30, "徐山", 83, 41, "秦祥", 85, 42, "葛公", 85, 23, "武衍公", 87, 94, "范斌", 83, 45, "黄乌", 60, 67, "叶景昌", 99, 7, "焦龙", 89, 78, "星姚烨", 85, 49, "孙吉", 90, 60, "陈梦庚", 95,};数组查询函数void ArraySearch(ElemType a[], int key, int length){int i;for (i = 0; i <= length; i++){if (key == a[i].key){cout << "学号：" << a[i].key << " 姓名：" << a[i].name << " 成绩：" << a[i].grade << endl;break;}}}二叉树查询函数上文二叉树根本函数中的SearchBST()即为二叉树查询函数。
数据结构（⼆⼗四）⼆叉树的链式存储结构（⼆叉链表） ⼀、⼆叉树每个结点最多有两个孩⼦，所以为它设计⼀个数据域和两个指针域，称这样的链表叫做⼆叉链表。
⼆、结点结构包括：lchild左孩⼦指针域、data数据域和rchild右孩⼦指针域。
三、⼆叉链表的C语⾔代码实现：#include "string.h"#include "stdio.h"#include "stdlib.h"#include "io.h"#include "math.h"#include "time.h"#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define MAXSIZE 100 /* 存储空间初始分配量 */typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 *//* ⽤于构造⼆叉树********************************** */int index=1;typedef char String[24]; /* 0号单元存放串的长度 */String str;Status StrAssign(String T,char *chars){int i;if(strlen(chars)>MAXSIZE)return ERROR;else{T[0]=strlen(chars);for(i=1;i<=T[0];i++)T[i]=*(chars+i-1);return OK;}}/* ************************************************ */typedef char TElemType;TElemType Nil=''; /* 字符型以空格符为空 */Status visit(TElemType e){printf("%c ",e);return OK;}typedef struct BiTNode /* 结点结构 */{TElemType data; /* 结点数据 */struct BiTNode *lchild,*rchild; /* 左右孩⼦指针 */}BiTNode,*BiTree;/* 构造空⼆叉树T */Status InitBiTree(BiTree *T){*T=NULL;return OK;}/* 初始条件: ⼆叉树T存在。
二叉排序树（Binary Sort Tree）是一种特殊的二叉树，它或左子树或右子树为完全二叉树。
由于二叉排序树的特点，其每个节点的值均大于其左子树中的所有节点的值，且小于其右子树中的所有节点的值。
以下是一个简单的二叉排序树的C语言实现，包括插入、查找和删除操作。
```c#include <stdio.h>#include <stdlib.h>typedef struct Node {int data;struct Node *left;struct Node *right;} Node;// 创建一个新的节点Node* createNode(int data) {Node* newNode = (Node*)malloc(sizeof(Node));if (!newNode) {printf("内存分配失败\n");return NULL;}newNode->data = data;newNode->left = newNode->right = NULL;return newNode;}// 在二叉排序树中插入一个新的节点Node* insert(Node* root, int data) {if (!root) { // 如果树为空，创建新节点并返回根节点root = createNode(data);} else if (data <= root->data) { // 如果插入的数据小于当前节点的值，则在左子树中插入root->left = insert(root->left, data);} else { // 如果插入的数据大于当前节点的值，则在右子树中插入root->right = insert(root->right, data);}return root; // 返回插入后的根节点}// 在二叉排序树中查找一个值是否存在int search(Node* root, int data) {if (!root) { // 如果树为空，返回0表示未找到return 0;} else if (root->data == data) { // 如果找到，返回1表示找到return 1;} else if (data < root->data) { // 如果插入的数据小于当前节点的值，在左子树中查找return search(root->left, data);} else { // 如果插入的数据大于当前节点的值，在右子树中查找return search(root->right, data);}}// 在二叉排序树中删除一个节点，并返回被删除的节点指针（如果存在）Node* deleteNode(Node* root, int data) {if (!root) return NULL; // 如果树为空，直接返回NULL（空树）if (data < root->data) { // 如果要删除的值小于当前节点的值，则在左子树中查找并删除root->left = deleteNode(root->left, data);} else if (data > root->data) { // 如果要删除的值大于当前节点的值，则在右子树中查找并删除root->right = deleteNode(root->right, data);} else { // 如果要删除的节点就是当前节点，根据情况选择删除方式（左子树或右子树）if (root->left == NULL) { // 如果左子树为空，直接删除当前节点（只有根节点时）Node *temp = root; // 临时保存当前节点，用于释放内存后替换原节点指针为NULLfree(temp); // 释放内存空间后将原指针设为NULL} else if (root->right == NULL) { // 如果右子树为空，直接删除当前节点（只有一个节点时）Node *temp = root->left; // 临时保存左子树的根节点，用于替换原节点指针为左子树的根节点指针（此时原节点为空）free(root); // 释放原节点的内存空间后将原指针设为NULL（此时原节点为空）root = temp; // 将原指针设为新的根节点指针（此时原节点为空）} else { // 如果左右子树都存在，则找到右子树中的最小节点（即要被替换的节点），替换原节点指针为最小节点的指针（此时原节点为空）并删除最小节点（通过递归实现）Node *temp = root->right; // 临时保存右子树的根节点指针（即要被替换的节点）root->data = temp->data; // 将原节点的数据。
二叉树的顺序存储及基本操作二叉树的顺序存储是将树中的节点按照完全二叉树从上到下、从左到右的顺序依次存储到一个一维数组中，采用这种方式存储的二叉树也被称为完全二叉树。
一、在使用顺序存储方式时，可以使用以下公式来计算一个节点的左右子节点和父节点：
1. 左子节点：2i+1（i为父节点的在数组中的下标）
2. 右子节点：2i+2
3. 父节点：(i-1)/2（i为子节点在数组中的下标）
二、基本操作：
1. 创建二叉树：按照上述公式将节点存储到数组中。
2. 遍历二叉树：可采用递归或非递归方式，进行前序、中序、后序、层次遍历。
3. 插入节点：先将节点插入到数组末尾，然后通过比较节点和其父节点的大小，进行上浮操作直到满足二叉树的性质。
4. 删除节点：先将待删除节点和最后一个节点交换位置，然后通过比较交换后的节点和其父节点的大小，进行下沉操作直到满足二
叉树的性质。
5. 查找节点：根据节点值进行查找，可采用递归或非递归方式。
6. 修改节点：根据节点值进行查找，然后进行修改操作。
二叉树的先序,中序,后序遍历c语言
二叉树是常见的数据结构，具有广泛的应用场景，例如搜索树、哈夫曼树等。
其中比较重要的一点就是对二叉树的遍历。
二叉树遍历有三种方式：先序遍历、中序遍历、后序遍历。
接下来，我将通过C语言来详细介绍这三种遍历方式。
一、先序遍历（Preorder Traversal）
先序遍历是指根节点->左子树->右子树的遍历方式。
C语言中的先序遍历算法如下：
```
void preorderTraversal(Node *node) {
if (node != NULL) {
printf("%d ", node->data); // 打印节点值
preorderTraversal(node->left); // 递归遍历左子树
preorderTraversal(node->right); // 递归遍历右子树
}
}
```
先序遍历的实现通过递归调用实现，当节点为空即遍历完成时返回。
总结：
以上三种遍历方式是二叉树遍历中最基本的方法，它们都是基于递归实现的。
通过学习这三种遍历方式，可以更好地理解二叉树的结构特点，提高数据结构算法的学习效果。
c语言二叉树的先序,中序,后序遍历1、先序遍历先序遍历可以想象为，一个小人从一棵二叉树根节点为起点，沿着二叉树外沿，逆时针走一圈回到根节点，路上遇到的元素顺序，就是先序遍历的结果先序遍历结果为：A B D H I E J C F K G2、中序遍历中序遍历可以看成，二叉树每个节点，垂直方向投影下来（可以理解为每个节点从最左边开始垂直掉到地上），然后从左往右数，得出的结果便是中序遍历的结果中遍历结果为：H D I B E J A F K C G3、后序遍历后序遍历就像是剪葡萄，我们要把一串葡萄剪成一颗一颗的。
还记得我上面提到先序遍历绕圈的路线么？（不记得翻上面理解）就是围着树的外围绕一圈，如果发现一剪刀就能剪下的葡萄（必须是一颗葡萄）（也就是葡萄要一个一个掉下来，不能一口气掉超过1个这样），就把它剪下来，组成的就是后序遍历了。
后序遍历中，根节点默认最后面后序遍历结果：H I D J E B K F G C A4、口诀先序遍历：先根再左再右中序遍历：先左再根再右后序遍历：先左再右再根这里的根，指的是每个分叉子树（左右子树的根节点）根节点，并不只是最开始头顶的根节点，需要灵活思考理解5、代码展示#include<stdio.h>#include<stdlib.h>typedef struct Tree{int data; // 存放数据域struct Tree *lchild; // 遍历左子树指针struct Tree *rchild; // 遍历右子树指针}Tree,*BitTree;BitTree CreateLink(){int data;int temp;BitTree T;scanf("%d",&data); // 输入数据temp=getchar(); // 吸收空格if(data == -1){ // 输入-1 代表此节点下子树不存数据，也就是不继续递归创建return NULL;}else{T = (BitTree)malloc(sizeof(Tree)); // 分配内存空间T->data = data; // 把当前输入的数据存入当前节点指针的数据域中printf("请输入%d的左子树: ",data);T->lchild = CreateLink(); // 开始递归创建左子树printf("请输入%d的右子树: ",data);T->rchild = CreateLink(); // 开始到上一级节点的右边递归创建左右子树return T; // 返回根节点}}// 先序遍历void ShowXianXu(BitTree T) // 先序遍历二叉树{if(T==NULL) //递归中遇到NULL，返回上一层节点{return;}printf("%d ",T->data);ShowXianXu(T->lchild); // 递归遍历左子树ShowXianXu(T->rchild); // 递归遍历右子树}// 中序遍历void ShowZhongXu(BitTree T) // 先序遍历二叉树{if(T==NULL) //递归中遇到NULL，返回上一层节点{return;}ShowZhongXu(T->lchild); // 递归遍历左子树printf("%d ",T->data);ShowZhongXu(T->rchild); // 递归遍历右子树}// 后序遍历void ShowHouXu(BitTree T) // 后序遍历二叉树{if(T==NULL) //递归中遇到NULL，返回上一层节点{return;}ShowHouXu(T->lchild); // 递归遍历左子树ShowHouXu(T->rchild); // 递归遍历右子树printf("%d ",T->data);}int main(){BitTree S;printf("请输入第一个节点的数据:\n");S = CreateLink(); // 接受创建二叉树完成的根节点printf("先序遍历结果: \n");ShowXianXu(S); // 先序遍历二叉树printf("\n中序遍历结果: \n");ShowZhongXu(S); // 中序遍历二叉树printf("\n后序遍历结果: \n");ShowHouXu(S); // 后序遍历二叉树return 0;}。
c语言将二叉树填充为完全二叉树的方法要将二叉树填充为完全二叉树，需要按照层次遍历方式进行操作。
下面是使用C语言来实现这个过程的方法：#include <stdio.h>#include <stdlib.h>#define MAX_SIZE 100// 二叉树节点结构体typedef struct Node {int data; // 当前节点的数据struct Node* left; // 左子节点指针struct Node* right; // 右子节点指针} Node;// 辅助队列结构体typedef struct Queue {Node* data[MAX_SIZE];int front, rear;} Queue;// 创建新节点Node* createNode(int data) {Node* newNode = (Node*)malloc(sizeof(Node)); newNode->data = data;newNode->left = NULL;newNode->right = NULL;return newNode;}// 插入节点Node* insertNode(Node* root, int data) {if (root == NULL) {return createNode(data);}Queue queue;queue.front = -1;queue.rear = -1;queue.data[++queue.rear] = root;while (queue.front != queue.rear) {Node* temp = queue.data[++queue.front];if (temp->left) {queue.data[++queue.rear] = temp->left; } else {temp->left = createNode(data);return root;}if (temp->right) {queue.data[++queue.rear] = temp->right; } else {temp->right = createNode(data);return root;}}return root;}// 中序遍历打印二叉树void inorderTraversal(Node* root) {if (root == NULL) {return;}inorderTraversal(root->left);printf("%d ", root->data);inorderTraversal(root->right);}int main() {Node* root = createNode(1);// 假设以下数据为二叉树的节点数据int data[] = {2, 3, 4, 5, 6, 7};int dataSize = sizeof(data) / sizeof(data[0]);for (int i = 0; i < dataSize; i++) {root = insertNode(root, data[i]);}printf("填充完全二叉树后的中序遍历结果：");inorderTraversal(root);return 0;}通过以上代码，我们可以将给定的二叉树填充为完全二叉树，并通过中序遍历方式打印出填充完后的结果。
二叉树 c语言在计算机科学领域中，树型数据结构是一种非常重要的数据结构，在实际开发中也得到了广泛的应用。
其中，二叉树又是一种非常常见的树型结构。
二叉树在很多情况下都能够提供更好的算法效率，同时也易于理解和实现，因此我们可以通过通过学习和掌握二叉树的特点以及优点，来更好的应用到实际开发中。
一、二叉树的定义二叉树是一种树型结构，树型结构是由节点构成的。
二叉树与一般的树型结构不同，它的每个节点最多只有两个子节点，分别称为左子树和右子树。
它们可以为空或者不为空，其子节点的数量时不固定且没有任何限制的。
二叉树的定义如下：（1）空树是树的一种特殊的状态。
我们可以把它称为二叉树；（2）若不是空树，那么它就是由一个称为根节点（root）的元素和左右两棵分别称为左子树（left subtree）和右子树（right subtree）的二叉树组成。
二、二叉树的特性（1）每个节点最多只有两个子节点，分别称为左子节点和右子节点；（2）左子树和右子树是二叉树；（3）二叉树没有重复的节点。
三、二叉树的应用二叉树是一种非常实用的数据结构，因为它可以模拟很多实际生活中的情况。
例如，我们可以利用二叉树来对某些数据进行分类和排序。
在二叉树的基础上，我们还可以构造二叉堆、哈夫曼树等更高级的数据结构。
除此之外，二叉树还可以应用到程序设计中。
例如，我们可以构造一个二叉树来表示某个程序的控制流，这个程序在执行时可以沿着二叉树的各个节点进行分支和选择，实现不同的功能。
此外，我们还可以利用二叉树来加快某些算法的执行效率，比如二分查找算法等。
四、二叉树的遍历方式对于二叉树的遍历，有三种基本方式，即前序遍历、中序遍历、后序遍历。
它们的遍历顺序不同，因此也得到了不同的称呼。
下面我们来简要介绍一下这三种遍历方式的特点和应用。
（1）前序遍历前序遍历是指首先访问树的根节点，然后按照从左到右的顺序依次遍历左子树和右子树。
前序遍历的应用非常广泛，可以用于生成表达式树、构造二叉树等等。
