下载文档原格式
二叉排序树1．二叉排序树定义二叉排序树（Binary Sort Tree）或者是一棵空树；或者是具有下列性质的二叉树：（1）若左子树不空，则左子树上所有结点的值均小于根结点的值；若右子树不空，则右子树上所有结点的值均大于根结点的值。
（2）左右子树也都是二叉排序树，如图6-2所示。
2．二叉排序树的查找过程由其定义可见，二叉排序树的查找过程为：（1）若查找树为空，查找失败。
（2）查找树非空，将给定值key与查找树的根结点关键码比较。
（3）若相等，查找成功，结束查找过程，否则：①当给值key小于根结点关键码，查找将在以左孩子为根的子树上继续进行，转（1）。
②当给值key大于根结点关键码，查找将在以右孩子为根的子树上继续进行，转（1）。
3．二叉排序树插入操作和构造一棵二叉排序树向二叉排序树中插入一个结点的过程：设待插入结点的关键码为key，为将其插入，先要在二叉排序树中进行查找，若查找成功，按二叉排序树定义，该插入结点已存在，不用插入；查找不成功时，则插入之。
因此，新插入结点一定是作为叶子结点添加上去的。
构造一棵二叉排序树则是逐个插入结点的过程。
对于关键码序列为：｛63，90，70，55，67，42，98，83，10，45，58｝，则构造一棵二叉排序树的过程如图6-3所示。
4．二叉排序树删除操作从二叉排序树中删除一个结点之后，要求其仍能保持二叉排序树的特性。
设待删结点为*p（p为指向待删结点的指针），其双亲结点为*f，删除可以分三种情况，如图6-4所示。
（1）*p结点为叶结点，由于删去叶结点后不影响整棵树的特性，所以，只需将被删结点的双亲结点相应指针域改为空指针，如图6-4（a）所示。
（2）*p结点只有右子树或只有左子树，此时，只需将或替换*f结点的*p子树即可，如图6-4（b）、（c）所示。
（3）*p结点既有左子树又有右子树，可按中序遍历保持有序地进行调整，如图6-4（d）、（e）所示。
设删除*p结点前，中序遍历序列为：① P为F的左子女时有：…，Pi子树，P，Pj，S子树，Pk，Sk子树，…，P2，S2子树，P1，S1子树，F，…。
数据结构之⼆叉树（BinaryTree）⽬录导读 ⼆叉树是⼀种很常见的数据结构，但要注意的是，⼆叉树并不是树的特殊情况，⼆叉树与树是两种不⼀样的数据结构。
⽬录 ⼀、⼆叉树的定义 ⼆、⼆叉树为何不是特殊的树 三、⼆叉树的五种基本形态 四、⼆叉树相关术语 五、⼆叉树的主要性质（6个） 六、⼆叉树的存储结构（2种） 七、⼆叉树的遍历算法（4种） ⼋、⼆叉树的基本应⽤：⼆叉排序树、平衡⼆叉树、赫夫曼树及赫夫曼编码⼀、⼆叉树的定义 如果你知道树的定义（有限个结点组成的具有层次关系的集合），那么就很好理解⼆叉树了。
定义：⼆叉树是n(n≥0)个结点的有限集，⼆叉树是每个结点最多有两个⼦树的树结构，它由⼀个根结点及左⼦树和右⼦树组成。
（这⾥的左⼦树和右⼦树也是⼆叉树）。
值得注意的是，⼆叉树和“度⾄多为2的有序树”⼏乎⼀样，但，⼆叉树不是树的特殊情形。
具体分析如下⼆、⼆叉树为何不是特殊的树 1、⼆叉树与⽆序树不同 ⼆叉树的⼦树有左右之分，不能颠倒。
⽆序树的⼦树⽆左右之分。
2、⼆叉树与有序树也不同（关键） 当有序树有两个⼦树时，确实可以看做⼀颗⼆叉树，但当只有⼀个⼦树时，就没有了左右之分，如图所⽰：三、⼆叉树的五种基本状态四、⼆叉树相关术语是满⼆叉树；⽽国际定义为，不存在度为1的结点，即结点的度要么为2要么为0，这样的⼆叉树就称为满⼆叉树。
这两种概念完全不同，既然在国内，我们就默认第⼀种定义就好）。
完全⼆叉树：如果将⼀颗深度为K的⼆叉树按从上到下、从左到右的顺序进⾏编号，如果各结点的编号与深度为K的满⼆叉树相同位置的编号完全对应，那么这就是⼀颗完全⼆叉树。
如图所⽰：五、⼆叉树的主要性质 ⼆叉树的性质是基于它的结构⽽得来的，这些性质不必死记，使⽤到再查询或者⾃⼰根据⼆叉树结构进⾏推理即可。
性质1：⾮空⼆叉树的叶⼦结点数等于双分⽀结点数加1。
证明：设⼆叉树的叶⼦结点数为X，单分⽀结点数为Y，双分⽀结点数为Z。
实现二叉树的各种基本运算的算法1.二叉树的定义及概述二叉树是一种重要的数据结构，它是由节点组成的序列，每个节点最多有两个子节点。
二叉树的根节点是唯一的，且每个节点都有一个“父节点”，除了根节点外，每个子节点称作“左孩子”和“右孩子”。
二叉树的组成部分是节点，每个节点包括一个数据元素和左右孩子指针。
通过这些指针构成的树形结构，可以便捷地进行数据存储和操作。
本文将介绍二叉树的各种基本运算及实现方法。
2.二叉树的遍历二叉树的遍历分为三种：前序遍历、中序遍历和后序遍历。
前序遍历:按照“根节点-左孩子-右孩子”的顺序遍历二叉树。
中序遍历:按照“左孩子-根节点-右孩子”的顺序遍历二叉树。
后序遍历:按照“左孩子-右孩子-根节点”的顺序遍历二叉树。
3.二叉树的建立二叉树的建立有三种方法：链式存储法、顺序存储法和扩展二叉树。
链式存储法:链式存储法是用链表来表示二叉树的方法，每个节点包括数据域和左右孩子指针域。
链式存储法建立二叉树比较容易，操作起来也比较方便。
顺序存储法:顺序存储法是用数组来表示二叉树的方法，便于存取、操作和查找。
但是顺序存储法的空间利用率不高，只有满二叉树才能利用完全。
扩展二叉树:是指二叉树中所有的空节点都必须存储起来，以构成一颗可以存储不满的二叉树。
由于扩展二叉树浪费了大量的空间，因此很少使用。
4.二叉树的查找二叉树的查找分为两种：层序遍历和二叉排序树的查找。
层序遍历:是一种广度优先搜索的方式来遍历二叉树。
层序遍历可以找到二叉树中从根节点到任意节点的路径，具有较高的效率。
层序遍历可以使用队列来实现。
二叉排序树的查找:是指在一颗二叉排序树中查找某个元素的算法。
二叉排序树(BST)是一颗二叉树，其中每个节点的值都比它的左子节点大，比它的右子节点小。
通过对BST的查找操作，可以将查找的效率高效地进行。
5.二叉树的删除在二叉树中删除节点有两种情况：删除叶子节点和删除非叶子节点。
下面给出二叉树的删除基本操作。
二叉排序树查找的递归算法介绍二叉排序树（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表示待查找的键值。
沈阳航空航天大学课程设计报告课程设计名称：数据结构课程设计课程设计题目：二叉排序树算法院（系）：计算机学院专业：计算机科学与技术班级：04010103学号：2010040101097姓名：郭胜龙指导教师：丁一军此页为任务书目录1 课程设计介绍 (1)1.1课程设计内容 (1)1.2课程设计要求 (1)2 课程设计原理 (2)2.1课设题目粗略分析 (2)2.2原理图介绍 (2)2.2.1 功能模块图 (2)2.2.2 main（主函数） (2)2.2.3 SearchBST（查找） (3)2.2.4 InsertBST（插入） (4)2.2.5 CreatBST（建立） (4)2.2.6 DeleteBST（删除） (4)2.2.7 PreOrder（先序遍历） (5)2.2.8 InOrder（中序遍历） (5)3 数据结构分析 (7)3.1存储结构 (7)3.2算法描述 (7)4 调试与分析 (12)4.1调试过程 (12)4.2程序执行过程 (12)参考文献 (15)附录（关键部分程序清单） (16)沈阳航空航天大学课程设计报告1 课程设计介绍1.1 课程设计内容题目内容:1.构造二叉排序树;2.输出该二叉排序树的先序、中序遍历序列；3.删除该二叉排序树的任意一个结点；4.输出删除后的二叉排序树的先序、中序遍历序列。
1.2课程设计要求题目要求：1.按要求建立不同的二叉排序树；2.数据自定3.独立完成课程设计任务2 课程设计原理2.1课设题目粗略分析根据课设题目要求，拟将整体程序分为七大模块。
以下是七个模块的大体分析：main （）：主函数模块SearchBST （）：查找相应的结点 InsertBST1（）：插入一个新的结点 CreatBST （）：创建一棵二叉排序树 DeleteNode （）：删除结点PreOrder （）对二叉排序树进行先序遍历 InOrder （）对二叉排序树进行中序遍历2.2 原理图介绍2.2.1 功能模块图图2.2.1 功能模块结构图2.2.2 main （主函数）功能：连接各个函数，确定他们的执行顺序和条件。
二叉排序树算法主模块查找模块 插入模块 建立模块 删除模块 先序遍历模块 中序遍历模块图2.2.2主函数流程图2.2.3 SearchBST （查找）功能：查找相应的结点。
图2.2.3 查找操作的流程图开始选择功能Choose=1 建立二叉排序树Choose=2 删除x 结点Choose=3 先序遍历二叉排Choose=0 退出Choose=4 中序遍历二叉排A结束AYY开始T->data==key s=TT->data>keys=SearchBST(T->rchild)s=SearchBST(T->lchild)NN返回s结束2.2.4 InsertBST （插入）功能：插入一个新的结点。
图2.2.4 插入操作的流程图2.2.5 CreatBST （建立）功能：建立一个已知数据的二叉排序树。
图2.2.5 建立操作的流程图2.2.6 DeleteBST （删除）功能：删除值为x 的结点。
YY开始T==NULL T=ss->data>T->datas=InserBST(T->rchild)s=InsertBST(T->lchild)NN结束开始输入结点数n调用插入函数结束开始调用查找函数删除p结点右子树连在左子树上左子树连在p结点的父母节点上结束图2.2.6 删除操作的流程图2.2.7 PreOrder（先序遍历）功能：对二叉排序树进行先序遍历，并输出序列。
开始访问TPreOrder（T->rchild）PreOrder（T->lchild）结束图2.2.7 先序遍历的流程图2.2.8 InOrder（中序遍历）功能：对二叉排序树进行先序遍历，并输出序列。
开始InOrder（T->rchild）访问TInOrder（T->lchild）结束图2.2.8 中序遍历的流程图沈阳航空航天大学课程设计报告错误！未指定书签。
3 数据结构分析3.1 存储结构定义一个链表式的二叉排序树，用链表的方式构造结点，存储二叉排序树中的结点、结点类型和指针类型如下：typedef struct BiTNode{int data;struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;3.2 算法描述1、二叉排序树的查找算法（1）若二叉排序树为空，则查找失败。
（2）否则，将根结点的关键字与待查关键字进行比较，若相等，则查找成功；若根节点关键字大于待查值，则进入左子树重复次步骤，否则，进入右子树进行此步骤；若在查找过程中遇到二叉排序树的叶子节点时，还没有找到待查节点，则查找不成功。
算法如下：BiTree SearchBST1(BiTree T, int key){//在根指针T所指二叉排序树中递归查找关键字等于 key 的数据元素//若成功，返回指向该数据元素结点的指针，否则返回空指针；s为返回 //指针BiTree s;if(T==NULL) return NULL;else if(T->data==key) s=T;else if(T->data>key) //key大于当前结点的关键字，则查找左子树s=SearchBST1(T->lchild,key);else//key小于当前结点的关键字则查找右子树s=SearchBST1(T->rchild,key);return s;}3、二叉排序树的节点插入算法在二叉排序树中插入一个新节点，首先要查找该节点在二叉排序树中是否已经存在。
若二叉排序树中不存在关键字等于x的节点，则插入。
将一个关键字值为x的节点s插入到二叉排序树中，可以用下面的方法：（1）若二叉排序树为空，则关键字为x的节点s成为二叉排序树的根（2）若二叉排序树非空，则将x与二叉排序树根进行比较，如果x的值等于根节点关键值，则停止插入；如果x的根节点值小于根节点关键值，则将x插入左子树；如果x的值大于根节点关键字的值，则将x插入右子树。
在左右两个子树的插入方法与整个二叉排序树相同。
算法如下：void InsertBST1(BiTree &T,BiTNode *s){//在二叉树排序树T中，插入一个结点s的递归算法BiTree t;t=SearchBST1(T,s->data);//若s的关键字不在T中出现，则插入if(!t){if(T==NULL)T=s; //空树时作为根结点else if(s->data<T->data)InsertBST1(T->lchild,s); //将s插入T的左子树 elseInsertBST1(T->rchild,s); //将s插入T的右子树}}3、二叉排序树的节点删除算法在二叉排序树中删除节点，首先要进行查找操作，以确定被删除的节点是否在二叉排序树中若不在，则不做任何操作；否则，假设要删除的节点为*p，节点*p的父节点为*f，并假设*p是*f的左孩子。
根据被删除节点*p有无孩子，删除部分可做以下3中情况讨论：（1）若*p为叶子节点，则可令其父节点*f的左孩子指针域为空，直接将其删除。
（2）若*p节点只有右子树或左子树，则可以将p的左子树或右子树直接改为其双亲节点f的左子树。
（3）若*p既有左子树又有右子树；将节点*s为*p的中序前驱。
首先找到*p 的中序前驱节点*s，然后用节点*s的值代替节点*p的值，再将节点*s删除，节点*s的原左子树改为*s的双亲节点*q的右子树；算法如下：DeleteNode(BiTree &T, int x){//从二叉树排序树T中删除任意结点,其关键字为xBiTree p,q,pParent,pChileNode;p=T; //从根结点开始查找pParent = NULL;// T的双亲为NULLwhile (p)// 开始查找关键字为x的结点p,及双亲pParent{if (x == p->data)break;pParent = p;p = x > p->data ? p->rchild : p->lchild;}if (p==NULL){printf("要删除的结点不存在\n");return false;} // 至此已找到目标结点p// pChileNode = p存在的孩子或NULL,左右都存在时，取左pChileNode = p->lchild!= NULL ? p->lchild : p->rchild;if(p->lchild==NULL||p->lchild==NULL){if (pParent == NULL)T= pChileNode;else{if(p==pParent->lchild)pParent->lchild= pChileNode;elsepParent->rchild = pChileNode;}free(p);//释放空间} // 当2个孩子都存在时else{//pChileNode已指向p->lchildq=p;while (pChileNode->rchild){//在p的左字树中查找中序p的前驱pChileNode，q为其双亲 q=pChileNode;pChileNode = pChileNode->rchild;}p->data=pChileNode->data;//p的前驱pChileNodede 的关键值赋给pif(q!=p) //将删除p转化为删除pChileNodede(最多只有左字树)结点{q->rchild=pChileNode->lchild;//p的左字树有右孩子 }else{q->lchild=pChileNode->lchild;//p的左字树有右孩子 }free(pChileNode);}return true;}4 调试与分析4.1 调试过程在调试程序是主要遇到以下几类问题：1.二叉树的存储结构的选择2.界面函数的调整3.删除的时候二叉树的调整4.2 程序执行过程执行过程如下图：图4.2.1 界面图图4.2.2 建立二叉排序树图4.2.3 先序遍历序列图4.2.4 中序遍历序列图4.2.5 删除结点图4.2.6 删除后的先序遍历序列图4.2.7 删除后的中序遍历序列沈阳航空航天大学课程设计报告错误！未指定书签。
参考文献[1] 殷人昆，等. 数据结构（用面向对象方法与C++描述）[M]. 北京：清华大学出版社，2002.[2] 宁正元，等. 算法与数据结构习题精解和实验指导[M]. 北京：清华大学出版社，2002.[3] 严蔚敏，吴伟民.数据结构[M].北京：清华大学出版社，2007.[4] 张长海，陈娟.C程序设计[M].北京：高等教育出版社，2004.[5] 谭浩强.C程序设计[M].北京：清华大学出版社，2005.附录（关键部分程序清单）#include <stdio.h>#include <malloc.h>#include <stdlib.h>typedef struct BiTNode{int data;struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;/************************查找**************************/BiTree SearchBST1(BiTree T, int key){//在根指针T所指二叉排序树中递归查找关键字等于 key 的数据元素//若成功，返回指向该数据元素结点的指针，否则返回空指针；s为返回 //指针BiTree s;if(T==NULL) return NULL;else if(T->data==key) s=T;else if(T->data>key) //key大于当前结点的关键字，则查找左子树s=SearchBST1(T->lchild,key);else//key小于当前结点的关键字则查找右子树s=SearchBST1(T->rchild,key);return s;}/************************插入**************************/void InsertBST1(BiTree &T,BiTNode *s){//在二叉树排序树T中，插入一个结点s的递归算法BiTree t;t=SearchBST1(T,s->data);//若s的关键字不在T中出现，则插入if(!t){if(T==NULL)T=s; //空树时作为根结点else if(s->data<T->data)InsertBST1(T->lchild,s); //将s插入T的左子树elseInsertBST1(T->rchild,s); //将s插入T的右子树}}/***********************建立****************************/BiTree CreatBST(int n){//建立n个关键字的二叉排序树,//从键盘输入调建立n个关键字依次用InsertBST1（插入函数），//返回根结点TBiTree T,s;int i,key;T=NULL;printf("建树过程：\n");for(i=1;i<=n;i++){printf("插入结点关键值：\n");scanf("%d",&key);s=(BiTree)malloc(sizeof(BiTNode));//开辟存储单元，并对结点赋值s->data=key;s->lchild=NULL; s->rchild=NULL;InsertBST1(T,s); //调用插入算法}return T;}/***********************删除*****************************/ DeleteNode(BiTree &T, int x){//从二叉树排序树T中删除任意结点,其关键字为xBiTree p,q,pParent,pChileNode;p=T; //从根结点开始查找pParent = NULL;// T的双亲为NULLwhile (p)// 开始查找关键字为x的结点p,及双亲pParent{if (x == p->data)break;pParent = p;p = x > p->data ? p->rchild : p->lchild;}if (p==NULL){printf("要删除的结点不存在\n");return false;} // 至此已找到目标结点p// pChileNode = p存在的孩子或NULL,左右都存在时，取左pChileNode = p->lchild!= NULL ? p->lchild : p->rchild;if(p->lchild==NULL||p->lchild==NULL){if (pParent == NULL)T= pChileNode;else{if(p==pParent->lchild)pParent->lchild= pChileNode;elsepParent->rchild = pChileNode;}free(p);//释放空间} // 当2个孩子都存在时else{//pChileNode已指向p->lchildq=p;while (pChileNode->rchild){//在p的左字树中查找中序p的前驱pChileNode，q为其双亲 q=pChileNode;pChileNode = pChileNode->rchild;}p->data=pChileNode->data;//p的前驱pChileNodede 的关键值赋给p if(q!=p) //将删除p转化为删除pChileNodede(最多只有左字树)结点 {q->rchild=pChileNode->lchild;//p的左字树有右孩子 }else{q->lchild=pChileNode->lchild;//p的左字树有右孩子 }free(pChileNode);}return true;}/**********************先序遍历************************/void PreOrder(BiTree T){if(T!=NULL){printf("%3d",T->data);PreOrder(T->lchild);PreOrder(T->rchild);}}/*********************中序遍历**************************/void InOrder(BiTree T){if(T!=NULL){InOrder(T->lchild);printf("%3d",T->data);InOrder(T->rchild);}}/*********************主函数******************************/void main(){int n,x,choose;BiTree T;while(1){printf("\n\n*******************************************\n"); printf("************************************\n");printf("二叉排序树算法\n");printf("************************************\n"); printf("请选择操作:\n");printf("0.退出\n");printf("1.建立一棵二叉排序树\n");printf("2.删除一个任意结点\n");printf("3.先序遍历序列\n");printf("4.中序遍历序列\n");printf("Please choose:");scanf("%d",&choose);switch(choose){case 1:system("cls");printf("输入结点个数n=：\n");scanf("%d",&n);T=CreatBST(n);system("cls");break;case 2:system("cls");printf("输入想要删除的结点x=：\n"); scanf("%d",&x);DeleteNode(T, x);system("cls");break;case 3:system("cls");printf("先序遍历序列：\n");PreOrder(T);printf("\n");break;case 4:system("cls");printf("中序遍历序列：\n");InOrder(T);printf("\n");break;default:exit(0);}}}沈阳航空航天大学课程设计报告课程设计总结：指导教师评语：指导教师(签字)：年月日课程设计成绩。
