下载文档原格式
数据结构与算法—二叉排序树详解前言前面介绍学习的大多是线性表相关的内容，把指针搞懂后其实也没有什么难度。
规则相对是简单的。
再数据结构中树、图才是数据结构标志性产物，(线性表大多都现成api可以使用),因为树的难度相比线性表大一些并且树的拓展性很强，你所知道的树、二叉树、二叉排序树，AVL树，线索二叉树、红黑树、B数、线段树等等高级数据结构。
然而二叉排序树是所有的基础，所以彻底搞懂二叉排序树也是非常重要的。
树参考王道数据结构二叉树也是树的一种，而二叉排序树又是二叉树的一种。
•树是递归的，将树的任何一个节点以及节点下的节点都能组合成一个新的树。
并且很多操作基于递归完成。
•根节点：最上面的那个节点(root)，根节点没有前驱节点，只有子节点（0个或多个都可以）•层数：一般认为根节点是第1层(有的也说第0层)。
而树的高度就是层数最高(上图层数开始为1)节点的层数•节点关系:父节点：就是链接该节点的上一层节点,孩子节点:和父节点对应，上下关系。
而祖先节点是父节点的父节点(或者祖先）节点。
兄弟节点：拥有同一个父节点的节点们！•度：节点的度就是节点拥有孩子节点的个数(是孩子不是子孙).而树的度(最大)节点的度。
同时，如果度大于0就成为分支节点,度等于0就成为叶子节点（没有子孙）。
相关性质：•树的节点数=所有节点度数 1.•度为m的树第i层最多有mi-1个节点。
(i>=1)•高度而h的m叉树最多（mh-1）/(m-1)个节点(等比数列求和) •n个节点的m叉树最小高度[logm(n(m-1) 1)]二叉树二叉树是一树的一种，但应用比较多，所以需要深入学习。
二叉树的每个节点最多只有两个节点。
二叉树与度为2的树的区别：•一：度为2的的树必须有三个节点以上，二叉树可以为空。
•二：二叉树的度不一定为2：比如说斜树。
•三：二叉树有左右节点区分，而度为2的树没有左右节点的区分。
几种特殊二叉树：•满二叉树。
高度为n的满二叉树有2n-1个节点•完全二叉树：上面一层全部满，最下一层从左到右顺序排列•二叉排序树：树按照一定规则插入排序(本文详解)。
数据结构—树二叉树前序遍历、中序遍历、后序遍历【图解实现】AI研习图书馆，发现不一样的精彩世界数据结构二叉树的遍历一、树在谈二叉树的知识点之前，我们首先来看一下树和图的基本概念。
树：不包含回路的连通无向图，树是一种简单的非线性结构。
由于树有一个不包含回路的特点，因此树被赋予了许多特性，如下所示：1、一棵树中任意的两个结点有且仅有唯一的一条路径连通2、一棵树如果有n个结点，那么它一定恰好有n-1条边3、在一棵树中加上一条边，将会构成一个回路4、一棵树中有且仅有一个没有前驱的结点，即为根结点通常情况下，我们在对树进行讨论的时候，将一棵树中的每个点称为结点:根结点：没有父结点的结点叶结点：没有子结点的结点内部结点：一个结点既不是根结点也不是叶结点每个结点有一个深度的概念，例如上图左边的树，4号结点深度是3。
二、二叉树1. 基本概念二叉树是一种非线性结构，二叉树是由递归定义的，其结点有左右子树之分。
2. 二叉树的存储结构二叉树一般采用链式存储结构，存储结点由数据域和指针域组成，二叉树的链式存储结构也称为二叉链表。
指针域：左指针域和右指针域特点：1、每个结点最多有两颗子树2、左子树和右子树是有顺序的，次序不能颠倒3、即使某个结点只有一颗子树，也要区分左右子树4、二叉树可为空，空的二叉树没有结点，非空二叉树有且仅有一个根节点二叉树中有两种比较特殊的二叉树：满二叉树、完全二叉树，对于满二叉树和完全二叉树可以按照层次进行顺序存储。
满二叉树：二叉树中每个内部结点都存在左子树和右子树满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。
满二叉树的严格定义：一颗深度为h且具有2h-1个结点的二叉树。
完全二叉树：解释一：如果一颗二叉树除了最右边位置上有一个或几个叶结点缺少外，其他都是丰满的，那么这样的二叉树就是完全二叉树。
解释二：除第h层外，其他各层（1到h-1）的结点数都达到最大个数，第h层从右向左连续缺若干结点，则这个二叉树就是完全二叉树。
介绍二叉排序树的结构和特点二叉排序树，也称为二叉搜索树或二叉查找树，是一种特殊的二叉树结构，其主要特点是左子树上的节点都小于根节点，右子树上的节点都大于根节点。
在二叉排序树中，每个节点都存储着一个关键字，而且所有的关键字都不相同。
二叉排序树的结构如下：1.根节点：二叉排序树的根节点是整个树的起始点，其关键字是最大的。
2.左子树：根节点的左子树包含着小于根节点关键字的所有节点，且左子树本身也是一个二叉排序树。
3.右子树：根节点的右子树包含着大于根节点关键字的所有节点，且右子树本身也是一个二叉排序树。
二叉排序树的特点如下：1.有序性：二叉排序树的最重要特点是有序性。
由于左子树上的节点都小于根节点，右子树上的节点都大于根节点，所以通过中序遍历二叉排序树，可以得到一个有序的序列。
2.快速查找：由于二叉排序树是有序的，所以可以利用二叉排序树进行快速查找操作。
对于给定的关键字，可以通过比较关键字与当前节点的大小关系，逐步缩小查找范围，最终找到目标节点。
3.快速插入和删除：由于二叉排序树的有序性，插入和删除操作比较简单高效。
插入操作可以通过比较关键字的大小关系，找到合适的位置进行插入。
删除操作可以根据不同情况，分为三种情况处理：删除节点没有子节点、删除节点只有一个子节点和删除节点有两个子节点。
4.可以用于排序：由于二叉排序树的有序性，可以利用二叉排序树对一组数据进行排序。
将数据依次插入二叉排序树中，然后再通过中序遍历得到有序序列。
二叉排序树的优缺点如下：1.优点：(1)快速查找：通过二叉排序树可以提供快速的查找操作，时间复杂度为O(log n)。
(2)快速插入和删除：由于二叉排序树的有序性，插入和删除操作比较简单高效。
(3)可以用于排序：通过二叉排序树可以对一组数据进行排序，时间复杂度为O(nlog n)。
2.缺点：(1)受数据分布影响：如果数据分布不均匀，可能导致二叉排序树的高度增加，从而降低了查找效率。
(2)不适合大规模数据：对于大规模数据，二叉排序树可能会导致树的高度过高，从而影响了查找效率。
数据结构之树和⼆叉树⼀树1 什么是树树状图是⼀种，它是由n（n>=1）个有限节点组成⼀个具有层次关系的。
把它叫做“树”是因为它看起来像⼀棵倒挂的树，也就是说它是根朝上，⽽叶朝下的。
它具有以下的特点：每个节点有零个或多个⼦节点；没有⽗节点的节点称为根节点；每⼀个⾮根节点有且只有⼀个⽗节点；除了根节点外，每个⼦节点可以分为多个不相交的⼦树；树（tree）是包含n（n>0）个结点的有穷集，其中：（1）每个元素称为结点（node）；（2）有⼀个特定的结点被称为根结点或树根（root）。
（3）除根结点之外的其余数据元素被分为m（m≥0）个互不相交的集合T1，T2，……Tm-1，其中每⼀个集合Ti（1<=i<=m）本⾝也是⼀棵树，被称作原树的⼦树（subtree）。
2 相关术语节点的度：⼀个节点含有的⼦树的个数称为该节点的度；叶节点或终端节点：度为0的节点称为叶节点；⾮终端节点或分⽀节点：度不为0的节点；双亲节点或⽗节点：若⼀个节点含有⼦节点，则这个节点称为其⼦节点的⽗节点；孩⼦节点或⼦节点：⼀个节点含有的⼦树的根节点称为该节点的⼦节点；兄弟节点：具有相同⽗节点的节点互称为兄弟节点；树的度：⼀棵树中，最⼤的节点的度称为树的度；节点的层次：从根开始定义起，根为第1层，根的⼦节点为第2层，以此类推；树的⾼度或深度：树中节点的最⼤层次；堂兄弟节点：双亲在同⼀层的节点互为堂兄弟；节点的祖先：从根到该节点所经分⽀上的所有节点；⼦孙：以某节点为根的⼦树中任⼀节点都称为该节点的⼦孙。
森林：由m（m>=0）棵互不相交的树的集合称为森林；3 树模拟⽂件系统⽰例class Node:def__init__(self, name, type='dir'): = nameself.type = type # "dir" or "file"self.children = []self.parent = Nonedef__repr__(self):return class FileSystemTree:def__init__(self):self.root = Node("/")self.now = self.root # 当前⽬录def mkdir(self, name):# name已/结尾的⽂件夹if name[-1] != "/":name += "/"node = Node(name)self.now.children.append(node)node.parent = self.nowdef ls(self):return self.now.childrendef cd(self, name):if name[-1] != "/":name += "/"if name == "../":self.now = self.now.parentreturnfor child in self.now.children:if == name:self.now = childreturnraise ValueError("invalid dir")tree = FileSystemTree()tree.mkdir("var/")tree.mkdir("bin/")tree.mkdir("usr/")print(tree.root.children)print(tree.ls())tree.cd('bin/')tree.mkdir('python/')print(tree.ls())tree.cd("../")print(tree.ls())⼆、⼆叉树⼆叉树的链式存储：将⼆叉树的节点定义为⼀个对象，节点之间通过类似链表的链接⽅式来连接* 度不超过2的树* 每个节点最多有两个孩⼦节点* 两个孩⼦节点被区分为左孩⼦节点和右孩⼦节点满⼆叉树：⼀个⼆叉树如果每⼀个层的节点数达到最⼤值,则这个⼆叉树就是满⼆叉树完全⼆叉树：叶节点只能出现在最下层和次下层，并且最下⾯⼀层的节点都集中在该层最左边的若⼲位置的⼆叉树⼆叉树的遍历⽅式：前序遍历： EACBDGF中序遍历： ABCDEGF后序遍历： BDCAFGE层次遍历： EAGCFBDfrom collections import dequeclass BiTreeNode:def__init__(self, data):self.data = dataself.lchild = Noneself.rchild = Nonedef level_order(root):queue = deque()queue.append(root)while len(queue) > 0: # 只要栈不空node = queue.popleft()print(node.data, end=',')if node.lchild:queue.append(node.lchild)if node.rchild:queue.append(node.rchild)root = BiTreeNode(100)root.lchild = BiTreeNode(30)root.rchild = BiTreeNode(102)level_order(root)三⼆叉搜索树⼆叉搜索树是⼀棵⼆叉树且满⾜性质：设X是⼆叉树的⼀个节点。
数据结构二叉排序树二叉排序树（Binary Search Tree）是一种特殊的二叉树，又称二叉查找树或二叉搜索树。
它的左子树上所有结点的值均小于它的根结点的值，右子树上所有结点的值均大于它的根结点的值。
并且左、右子树也分别是二叉排序树。
二叉排序树的实现，通常使用链式存储结构。
每个节点包含三个数据成员：key，left和right。
key为节点的关键字，left和right分别表示左右孩子节点的指针。
二叉排序树的查找过程是从根节点开始，比较要查找的关键字和根节点的关键字的大小，如果相等，则找到所需节点；如果比根节点小，则在左子树中继续查找；如果比根节点大，则在右子树中继续查找，直到找到所需节点或者指针为空。
二叉排序树的插入过程是先进行查找操作，找到插入的位置后，在该位置插入新节点。
插入一个新的节点会改变原有的结构，需要不断地调整二叉排序树，使之重新满足二叉排序树定义的性质。
二叉排序树的删除过程比较复杂，需要考虑多种情况。
如果要删除的节点是叶子节点，直接删除即可；如果要删除的节点只有一个子节点，将其子节点替换成该节点即可；如果要删除的节点有两个子节点，需要找到其右子树中的最小节点或者左子树中的最大节点作为替代节点。
二叉排序树的优缺点：优点：1. 查找、插入、删除元素的操作复杂度均为O(log n)，比线性查找的复杂度O(n)要快。
2. 适用于查找、排序、统计和检索大量元素的应用场景，例如字典、电话簿等。
3. 在存储元素的过程中，可以任意添加或删除元素，不会导致其他元素的位序改变。
4. 这种数据结构利用了树的优点，非常适合用于内存有限的情况下。
缺点：1. 当元素的排序规则不合理时，二叉排序树可能导致树的深度较大，从而影响操作效率。
2. 二叉排序树的构造过程是顺序插入的，可能会造成树的不平衡，进而影响操作效率。
3. 二叉排序树对于相同元素的重复插入会导致树的深度增大，从而影响操作效率。
总结：二叉排序树是一种优秀的数据结构，用于排序和查找元素的操作。
数据结构---二叉排序树二叉排序树（Binary Sort Tree）又称二叉查找树，亦称二叉搜索树。
它或者是一棵空树；或者是具有下列性质的二叉树：（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；（3）左、右子树也分别为二叉排序树；一、查找：步骤：若根结点的关键字值等于查找的关键字，成功。
否则，若小于根结点的关键字值，递归查左子树。
若大于根结点的关键字值，递归查右子树。
若子树为空，查找不成功。
平均情况分析（在成功查找两种的情况下）：在一般情况下，设 P（n，i）且它的左子树的结点个数为 i 时的平均查找长度。
如图的结点个数为 n = 6 且 i = 3; 则 P（n,i）= P（6, 3） = [ 1+ ( P(3) + 1) * 3 + ( P(2) + 1) * 2 ] / 6= [ 1+ ( 5/3 + 1) * 3 + ( 3/2 + 1) * 2 ] / 6注意：这里 P(3)、P(2) 是具有 3 个结点、2 个结点的二叉分类树的平均查找长度。
在一般情况，P（i）为具有 i 个结点二叉分类树的平均查找长度。
P(3) = （1+2+2）/ 3 = 5/3P(2) = （1+2）/ 2 = 3/2∴ P（n,i）= [ 1+ ( P(i) + 1) * i + ( P(n-i-1) + 1) * (n-i-1) ] / n ∴ P（n）= P（n,i）/ n <= 2(1+I/n)lnn因为2(1+I/n)lnn≈1.38logn 故P(n)=O(logn)二、插入删除与次优二叉树相对，二叉排序树是一种动态树表。
其特点是：树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的节点时再进行插入。
新插入的结点一定是一个新添加的叶子节点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。
数据结构53：⼆叉排序树（⼆叉查找树）前⼏节介绍的都是有关静态查找表的相关知识，从本节开始介绍另外⼀种查找表——动态查找表。
动态查找表中做查找操作时，若查找成功可以对其进⾏删除；如果查找失败，即表中⽆该关键字，可以将该关键字插⼊到表中。
动态查找表的表⽰⽅式有多种，本节介绍⼀种使⽤树结构表⽰动态查找表的实现⽅法——⼆叉排序树（⼜称为“⼆叉查找树”）。
什么是⼆叉排序树？⼆叉排序树要么是空⼆叉树，要么具有如下特点：⼆叉排序树中，如果其根结点有左⼦树，那么左⼦树上所有结点的值都⼩于根结点的值；⼆叉排序树中，如果其根结点有右⼦树，那么右⼦树上所有结点的值都⼤⼩根结点的值；⼆叉排序树的左右⼦树也要求都是⼆叉排序树；例如，图 1 就是⼀个⼆叉排序树：图 1 ⼆叉排序树使⽤⼆叉排序树查找关键字⼆叉排序树中查找某关键字时，查找过程类似于次优⼆叉树，在⼆叉排序树不为空树的前提下，⾸先将被查找值同树的根结点进⾏⽐较，会有 3 种不同的结果：如果相等，查找成功；如果⽐较结果为根结点的关键字值较⼤，则说明该关键字可能存在其左⼦树中；如果⽐较结果为根结点的关键字值较⼩，则说明该关键字可能存在其右⼦树中；实现函数为：（运⽤递归的⽅法）BiTree SearchBST(BiTree T, KeyType key){// 如果递归过程中 T 为空，则查找结果，返回NULL；或者查找成功，返回指向该关键字的指针if (!T || key==T->data) {return T;} else if(key<T->data) {// 递归遍历其左孩⼦return SearchBST(T->lchild, key);} else {// 递归遍历其右孩⼦return SearchBST(T->rchild, key);}}⼆叉排序树中插⼊关键字⼆叉排序树本⾝是动态查找表的⼀种表⽰形式，有时会在查找过程中插⼊或者删除表中元素，当因为查找失败⽽需要插⼊数据元素时，该数据元素的插⼊位置⼀定位于⼆叉排序树的叶⼦结点，并且⼀定是查找失败时访问的最后⼀个结点的左孩⼦或者右孩⼦。
