数据结构 二叉排序树

题目:二叉排序树的实现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()即为二叉树查询函数。

数据结构之⼆叉树（BinaryTree）⽬录导读 ⼆叉树是⼀种很常见的数据结构，但要注意的是，⼆叉树并不是树的特殊情况，⼆叉树与树是两种不⼀样的数据结构。

⽬录 ⼀、⼆叉树的定义 ⼆、⼆叉树为何不是特殊的树 三、⼆叉树的五种基本形态 四、⼆叉树相关术语 五、⼆叉树的主要性质（6个） 六、⼆叉树的存储结构（2种） 七、⼆叉树的遍历算法（4种） ⼋、⼆叉树的基本应⽤：⼆叉排序树、平衡⼆叉树、赫夫曼树及赫夫曼编码⼀、⼆叉树的定义 如果你知道树的定义（有限个结点组成的具有层次关系的集合），那么就很好理解⼆叉树了。

定义：⼆叉树是n(n≥0)个结点的有限集，⼆叉树是每个结点最多有两个⼦树的树结构，它由⼀个根结点及左⼦树和右⼦树组成。

（这⾥的左⼦树和右⼦树也是⼆叉树）。

值得注意的是，⼆叉树和“度⾄多为2的有序树”⼏乎⼀样，但，⼆叉树不是树的特殊情形。

具体分析如下⼆、⼆叉树为何不是特殊的树 1、⼆叉树与⽆序树不同 ⼆叉树的⼦树有左右之分，不能颠倒。

⽆序树的⼦树⽆左右之分。

2、⼆叉树与有序树也不同（关键） 当有序树有两个⼦树时，确实可以看做⼀颗⼆叉树，但当只有⼀个⼦树时，就没有了左右之分，如图所⽰：三、⼆叉树的五种基本状态四、⼆叉树相关术语是满⼆叉树；⽽国际定义为，不存在度为1的结点，即结点的度要么为2要么为0，这样的⼆叉树就称为满⼆叉树。

这两种概念完全不同，既然在国内，我们就默认第⼀种定义就好）。

完全⼆叉树：如果将⼀颗深度为K的⼆叉树按从上到下、从左到右的顺序进⾏编号，如果各结点的编号与深度为K的满⼆叉树相同位置的编号完全对应，那么这就是⼀颗完全⼆叉树。

如图所⽰：五、⼆叉树的主要性质 ⼆叉树的性质是基于它的结构⽽得来的，这些性质不必死记，使⽤到再查询或者⾃⼰根据⼆叉树结构进⾏推理即可。

性质1：⾮空⼆叉树的叶⼦结点数等于双分⽀结点数加1。

证明：设⼆叉树的叶⼦结点数为X，单分⽀结点数为Y，双分⽀结点数为Z。

二叉排序树操作一、设计步骤1）分析课程设计题目的要求2）写出详细设计说明3）编写程序代码，调试程序使其能正确运行4）设计完成的软件要便于操作和使用5）设计完成后提交课程设计报告（一）程序功能：1）创建二叉排序树2）输出二叉排序树3）在二叉排序树中插入新结点4）在二叉排序树中删除给定的值5）在二叉排序树中查找所给定的值（二）函数功能：1） struct BiTnode 定义二叉链表结点类型包含结点的信息2） class BT 二叉排序树类，以实现二叉排序树的相关操作3） InitBitree() 构造函数，使根节点指向空4) ~BT () 析构函数，释放结点空间5) void InsertBST(&t,key) 实现二叉排序树的插入功能6) int SearchBST(t,key) 实现二叉排序树的查找功能7) int DelBST(&t,key) 实现二叉排序树的删除功能8) void InorderBiTree (t) 实现二叉排序树的排序（输出功能）9) int main() 主函数，用来完成对二叉排序树类中各个函数的测试二、设计理论分析方法（一）二叉排序树定义首先，我们应该明确所谓二叉排序树是指满足下列条件的二叉树：（1）左子树上的所有结点值均小于根结点值；（2）右子数上的所有结点值均不小于根结点值；（3）左、右子数也满足上述两个条件。

根据对上述的理解和分析，我们就可以先创建出一个二叉链表结点的结构体类型（struct BiTNode）和一个二叉排序树类（class BT），以及类中的构造函数、析构函数和其他实现相关功能的函数。

（二）插入函数（void InsertBST(&t,key)）首先定义一个与BiTNode<k> *BT同一类型的结点p，并为其申请空间，使p->data=key,p->lchild和p->rchild=NULL。

二叉排序树的构造方法二叉排序树又称二叉查找树，是一种经典的数据结构，它具有快速的插入、删除和查找等操作。

在实际应用中，二叉排序树被广泛地使用，因此了解二叉排序树的构造方法至关重要。

本文将介绍二叉排序树的构造方法，帮助读者深入理解这一数据结构。

一、二叉排序树基本概念二叉排序树是一种二叉树，每个节点包含一个值，并且满足以下性质：1. 左子树上所有节点的值均小于其父节点的值；2. 右子树上所有节点的值均大于其父节点的值；3. 左右子树也分别为二叉排序树。

根据上述性质，可以得出二叉排序树的中序遍历结果为有序序列。

这一特点使得二叉排序树成为一种非常有效的数据结构，用于快速查找和排序。

二、二叉排序树的构造方法在构造二叉排序树时，一般采用递归或循环遍历的方法。

下面将分别介绍这两种构造方法。

1. 递归构造方法递归构造方法是一种常见且直观的构造二叉排序树的方式。

其基本原理为，将新节点插入到当前节点的左子树或右子树上，直至找到合适的位置。

具体流程如下所示：（1）若二叉排序树为空，直接将新节点作为根节点插入；（2）若新节点值小于当前节点值，则递归地将其插入到左子树上；（3）若新节点值大于当前节点值，则递归地将其插入到右子树上。

通过递归构造方法，可以很方便地构造出一棵满足二叉排序树性质的树。

2. 循环构造方法循环构造方法是另一种构造二叉排序树的方式，通过使用迭代的方式，逐步构建二叉排序树。

其基本思路为：（1）从根节点开始，若树为空，则直接将新节点插入为根节点；（2）若树不为空，则利用循环遍历的方式，找到新节点应插入的位置，直至找到合适的叶子节点；（3）将新节点插入到找到的叶子节点的左子树或右子树上。

循环构造方法相对于递归构造方法，更加迭代化，适合于对二叉排序树进行迭代构造和遍历。

三、二叉排序树构造方法的实现在实际编程中，可以通过使用递归或循环的方式，实现二叉排序树的构造。

下面将简要介绍二叉排序树构造方法的实现过程。

1. 递归实现递归实现二叉排序树的构造方法一般通过编写递归函数，不断地将新节点插入到当前节点的左子树或右子树上。

介绍二叉排序树的结构和特点二叉排序树，也称为二叉搜索树或二叉查找树，是一种特殊的二叉树结构，其主要特点是左子树上的节点都小于根节点，右子树上的节点都大于根节点。

在二叉排序树中，每个节点都存储着一个关键字，而且所有的关键字都不相同。

二叉排序树的结构如下：1.根节点：二叉排序树的根节点是整个树的起始点，其关键字是最大的。

2.左子树：根节点的左子树包含着小于根节点关键字的所有节点，且左子树本身也是一个二叉排序树。

3.右子树：根节点的右子树包含着大于根节点关键字的所有节点，且右子树本身也是一个二叉排序树。

二叉排序树的特点如下：1.有序性：二叉排序树的最重要特点是有序性。

由于左子树上的节点都小于根节点，右子树上的节点都大于根节点，所以通过中序遍历二叉排序树，可以得到一个有序的序列。

2.快速查找：由于二叉排序树是有序的，所以可以利用二叉排序树进行快速查找操作。

对于给定的关键字，可以通过比较关键字与当前节点的大小关系，逐步缩小查找范围，最终找到目标节点。

3.快速插入和删除：由于二叉排序树的有序性，插入和删除操作比较简单高效。

插入操作可以通过比较关键字的大小关系，找到合适的位置进行插入。

删除操作可以根据不同情况，分为三种情况处理：删除节点没有子节点、删除节点只有一个子节点和删除节点有两个子节点。

4.可以用于排序：由于二叉排序树的有序性，可以利用二叉排序树对一组数据进行排序。

将数据依次插入二叉排序树中，然后再通过中序遍历得到有序序列。

二叉排序树的优缺点如下：1.优点：(1)快速查找：通过二叉排序树可以提供快速的查找操作，时间复杂度为O(log n)。

(2)快速插入和删除：由于二叉排序树的有序性，插入和删除操作比较简单高效。

(3)可以用于排序：通过二叉排序树可以对一组数据进行排序，时间复杂度为O(nlog n)。

2.缺点：(1)受数据分布影响：如果数据分布不均匀，可能导致二叉排序树的高度增加，从而降低了查找效率。

(2)不适合大规模数据：对于大规模数据，二叉排序树可能会导致树的高度过高，从而影响了查找效率。

二叉排序树查找的递归算法介绍二叉排序树（Binary Search Tree），也称二叉查找树、有序二叉树或排序二叉树，是一种常用的数据结构。

它具有以下特点：•每个节点都包含一个键值和对应的数据。

•左子树中的所有节点的键值都小于根节点的键值。

•右子树中的所有节点的键值都大于根节点的键值。

•左右子树也分别是二叉排序树。

二叉排序树支持高效的查找、插入和删除操作，其中查找操作是利用递归实现的。

本文将详细介绍二叉排序树查找的递归算法。

二叉排序树的定义二叉排序树的定义如下：class TreeNode:def __init__(self, key, data):self.key = keyself.data = dataself.left = Noneself.right = Noneclass BinarySearchTree:def __init__(self):self.root = None在二叉排序树中，每个节点都是一个TreeNode对象，包含键值key和对应的数据data。

left和right分别指向左子树和右子树的根节点。

树的根节点由BinarySearchTree对象的root属性表示。

二叉排序树查找的递归算法二叉排序树的查找操作是利用递归实现的，其具体算法如下：1.如果待查找的键值等于当前节点的键值，返回当前节点的数据。

2.如果待查找的键值小于当前节点的键值，递归在左子树中查找。

3.如果待查找的键值大于当前节点的键值，递归在右子树中查找。

4.如果在左子树或右子树中找不到对应的键值，则返回空。

下面是二叉排序树查找的递归算法的代码实现：def search_recursive(node, key):if node is None or node.key == key:return node.dataelif key < node.key:return search_recursive(node.left, key)else:return search_recursive(node.right, key)在上述代码中，node表示当前节点，key表示待查找的键值。

以二叉树或树作为表的组织形式，称为树表，它是一类动态查找表，不仅适合于数据查找，也适合于表插入和删除操作。

常见的树表：二叉排序树平衡二叉树B-树B+树9.3.1 二叉排序树二叉排序树（简称BST）又称二叉查找（搜索）树，其定义为：二叉排序树或者是空树，或者是满足如下性质（BST性质）的二叉树：❶若它的左子树非空，则左子树上所有节点值（指关键字值）均小于根节点值；❷若它的右子树非空，则右子树上所有节点值均大于根节点值；❸左、右子树本身又各是一棵二叉排序树。

注意：二叉排序树中没有相同关键字的节点。

二叉树结构满足BST性质：节点值约束二叉排序树503080209010854035252388例如:是二叉排序树。

66不试一试二叉排序树的中序遍历序列有什么特点？二叉排序树的节点类型如下：typedef struct node{KeyType key;//关键字项InfoType data;//其他数据域struct node*lchild,*rchild;//左右孩子指针}BSTNode;二叉排序树可看做是一个有序表，所以在二叉排序树上进行查找，和二分查找类似，也是一个逐步缩小查找范围的过程。

1、二叉排序树上的查找Nk< bt->keybtk> bt->key 每一层只和一个节点进行关键字比较！∧∧p查找到p所指节点若k<p->data，并且p->lchild=NULL，查找失败。

若k>p->data，并且p->rchild=NULL，查找失败。

查找失败的情况加上外部节点一个外部节点对应某内部节点的一个NULL指针递归查找算法SearchBST()如下（在二叉排序树bt上查找关键字为k的记录，成功时返回该节点指针，否则返回NULL）：BSTNode*SearchBST(BSTNode*bt,KeyType k){if(bt==NULL||bt->key==k)//递归出口return bt;if(k<bt->key)return SearchBST(bt->lchild,k);//在左子树中递归查找elsereturn SearchBST(bt->rchild,k);//在右子树中递归查找}在二叉排序树中插入一个关键字为k的新节点，要保证插入后仍满足BST性质。