二叉排序树算法

9
第９章
第三节
二、二叉排序树(插入)

查找
动态查找表
二叉排序树是一种动态查找表


当树中不存在查找的结点时，作插入操作
新插入的结点一定是叶子结点（只需改动一个 结点的指针） 该叶子结点是查找不成功时路径上访问的最后 一个结点的左孩子或右孩子(新结点值小于或 大于该结点值) 10

第９章
第三节
查找
19
在二叉排序树中查找关 键字值等于37,88,94
3
第９章
第三节
查找
动态查找表
二、二叉排序树(查找函数)中结点结构定义 二叉排序树通常采用二叉链表的形式进行存 储，其结点结构定义如下：
typedef struct BiNode { int data; BiNode *lChild, *rChild; }BiNode,*BitTree;
4
第９章
第三节
查找
动态查找表
2、二叉排序树的定义 定义二叉排序树所有用到的变量 BitTree root; int
//查找是否成功（1--成功，0--不成功） //查找位置（表示在BisCount层中的第几个位置
BisSuccess;
int
int
BisPos;
BisCount;
//查找次数（相当于树的层数）
7
第９章
第三节
查找
动态查找表
二、二叉排序树(查找函数)
else { BisSuccess = 0; root=GetNode(k);//查找不成功，插入新的结点}
} BiNode * GetNode(int k) { BiNode *s; s = new BiNode; s->data = k; s->lChild = NULL; s->rChild = NULL; return(s);}

②若*p结点只有左子树，或只有右子树，则可将*p的左子 树或右子树直接改为其双亲结点*f的左子树，即： f->1child=p->1child(或f->1child=p->rchild); free(p)； *f
F *p P P1
*f
F
*f
F *p P
*f
F
Pr
P1
Pr
③若*p既有左子树，又有右子树。则：
-1 0
47
-1
47
47
0
31 69
69
25
0
47
0
25
0
47
-1 0
31
0
69
0
40
69
40
69
0
25 76
40
76
(a)
AL、BL、BR 都是空树
(b) AL、BL、BR 都是非空树
LR型调整操作示意图
2
A
-1
0
C
AR C BL CL CR AR
0 0
B BL CL S
B
A
CR
(a) 插入结点*s后失去平衡
31
0 0 -1
31
0 1
28
0
25
0 0
47
0
25
-1
47
0
25
0
31
0
16 0
28
16
28
0
16 30
30
47
(c) LR(R)型调整
RL型调整操作示意图
A B C A BR CR B BR
AL
C
AL
CL CR

9.6.2 哈希函数的构造方法
构造哈希函数的目标：
哈希地址尽可能均匀分布在表空间上——均 匀性好； 哈希地址计算尽量简单。
考虑因素：
函数的复杂度； 关键字长度与表长的关系； 关键字分布情况； 元素的查找频率。
一、直接地址法 取关键字或关键字的某个线性函数值为哈希地址 即： H(key) = key 或： H(key) = a* key + b 其中，a， b为常数。 例：1949年后出生的人口调查表，关键字是年份 年份 1949 1950 1951 … 人数 … … … …
9.4 二叉排序树
1．定义：
二叉排序树(二叉搜索树或二叉查找树) 或者是一棵空树；或者是具有如下特性的二叉树
(1) 若它的左子树不空，则左子树上所有结点的 值均小于根结点的值；
(2) 若它的右子树不空，则右子树上所有结点 的值均大于等于根结点的值； (3) 它的左、右子树也都分别是二叉排序树。
例如:
H(key)
通常设定一个一维数组空间存储记录集合，则 H(key)指示数组中的下标。
称这个一维数组为哈希(Hash)表或散列表。 称映射函数 H 为哈希函数。 H(key)为哈希地址
例：假定一个线性表为： A = (18，75，60，43，54，90，46) 假定选取的哈希函数为
hash3(key) = key % 13
H(key) = key + (-1948) 此法仅适合于： 地址集合的大小 = = 关键字集合的大小
二、数字分析法
假设关键字集合中的每个关键字都是由 s 位数 字组成 (u1, u2, …, us)，分析关键字集中的全体， 并从中提取分布均匀的若干位或它们的组合作为 地址。 例如：有若干记录，关键字为 8 位十进制数， 假设哈希表的表长为100, 对关键字进行分析， 取随机性较好的两位十进制数作为哈希地址。

二叉排序树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。

就维护表的有序性而言，二叉排序树无须移 动结点，只需修改指针即可完成插入和删 除操作，且其平均的执行时间均为O(lgn)， 因此更有效。二分查找所涉及的有序表是 一个向量，若有插入和删除结点的操作， 则维护表的有序性所花的代价是O(n)。当 有序表是静态查找表时，宜用向量作为其 存储结构，而采用二分查找实现其查找操 作；若有序表里动态查找表，则应选择二 叉排序树作为其存储结构。
if(q->lchild) //*q的左子树非空，找*q的左子 树的最右节点r. {for(q=q->lchild;q->rchild;q=q->rchild); q->rchild=p->rchild; } if(parent->lchild==p)parent->lchild=p>lchild; else parent->rchild=p->lchild; free(p)； /释放*p占用的空间 } //DelBSTNode
下图(a)所示的树，是按如下插入次序构成的： 45，24，55，12，37，53，60，28，40，70 下图(b)所示的树，是按如下插入次序构成的： 12，24，28，37，40，45，53，55，60，70
在二叉排序树上进行查找时的平均查找长度和二叉树的形态 有关： ①在最坏情况下，二叉排序树是通过把一个有序表的n 个结点依次插入而生成的，此时所得的二叉排序树蜕化为 棵深度为n的单支树，它的平均查找长度和单链表上的顺 序查找相同，亦是(n+1)/2。 ②在最好情况下，二叉排序树在生成的过程中，树的形 态比较匀称，最终得到的是一棵形态与二分查找的判定树 相似的二叉排序树，此时它的平均查找长度大约是lgn。 ③插入、删除和查找算法的时间复杂度均为O(lgn)。 (3)二叉排序树和二分查找的比较 就平均时间性能而言，二叉排序树上的查找和二分查找 差不多。

#define EH 0 //等高
#define RH -1 //右高
//平衡二叉树的类型
struct AVLNode
{
int data;
int bf; //bf结点的平衡因子,只能够取0，-1，1，为左子树的深度减去右子树的深度
struct AVLNode *lchild,*rchild; //左、右孩子指针
{
AVLNode *rc,*rd;
rc=T->rchild;
switch(rc->bf)
{
case RH:
T->bf=rc->bf=EH;
L_Rotate(T);
break;
case LH:
rd=rc->lchild;
switch(rd->bf)
{
case RH:
T->bf=LH;
rc->bf=EH;
};
2.右旋操作：
void R_Rotate(AVLNode *&p)//LL型算法
{
AVLNode *lc=p->lchild; // lc指向p的左子树根结点
p->lchild=lc->rchild; // lc的右子树挂接为p（之前跟节点）的左子树
lc->rchild=p;
p=lc; // p指向新的根结点
插入和删除：
插入删除是互为镜像的操作。我们可以采用前面对二叉排序树的删除操作来进行。然后，在删除掉结点后，再对平衡树进行平衡化处理。删除之所以删除操作需要的平衡化可能比插入时次数多，就是因为平衡化不会增加子树的高度，但是可能会减少子树的高度，在有有可能使树增高的插入操作中，一次平衡化能抵消掉增高；在有可能使树减低的删除操作中，平衡化可能会带来祖先节点的不平衡。AVL树体现了一种平衡的美感，两种旋转是互为镜像的，插入删除是互为镜像的操作，没理由会有那么大的差别。实际上，平衡化可以统一的这样来操作：

05
13
19
21
37
56
64
75
80
88
92
low mid high 因为r[mid].key<k，所以向右找，令low:=mid+1=4 (3) low=4;high=5;mid=(4+5) div 2=4
05
13
19
low
21
37
56
64
75
80
88
92
mid high
因为r[mid].key=k，查找成功，所查元素在表中的序号为mid 的值
平均查找长度：为确定某元素在表中某位置所进行的比 较次数的期望值。 在长度为n的表中找某一元素，查找成功的平均查找长度:
ASL=∑PiCi
Pi :为查找表中第i个元素的概率 Ci :为查到表中第i个元素时已经进行的比较次数
在顺序查找时， Ci取决于所查元素在表中的位置， Ci =i,设每个元素的查找概率相等，即Pi=1/n,则:
RL型的第一次旋转(顺时针) 以 53 为轴心,把 37 从 53 的左上转到 53 的左下,使得 53 的左 是 37 ;右是 90 ，原 53 的左变成了 37 的右。 RL型的第二次旋转(逆时针)
一般情况下，假设由于二叉排序树上插入结点而失去 平衡的最小子树的根结点指针为a（即a是离插入结点最 近,且平衡因子绝对值超过1的祖先结点），则失去平衡 后进行调整的规律可归纳为下列四种情况: ⒈RR型平衡旋转: a -2 b -1 h-1 a1
2.查找关键字k=85 的情况 (1) low=1;high=11;mid=(1+11) / 2=6
05
13
19
21

实现二叉树的各种基本运算的算法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表示待查找的键值。

NODE *t; char x; {if(t==NULL)
return(NULL); else
{if(t->data==x) return(t);
if(x<(t->data) return(search(t->lchild,x));
else return(search(t->lchild,x)); } }
——这种既查找又插入的过程称为动态查找。 二叉排序树既有类似于折半查找的特性，又采用了链表存储， 它是动态查找表的一种适宜表示。
注：若数据元素的输入顺序不同，则得到的二叉排序树形态 也不同！
讨论1：二叉排序树的插入和查找操作 例：输入待查找的关键字序列=（45，24，53，45，12，24，90）
二叉排序树的建立 对于已给定一待排序的数据序列,通常采用逐步插入结点的方 法来构造二叉排序树,即只要反复调用二叉排序树的插入算法 即可，算法描述为： BiTree *Creat (int n) //建立含有n个结点的二叉排序树 { BiTree *BST= NULL;
for ( int i=1; i<=n; i++) { scanf(“%d”,&x); //输入关键字序列
– 法2：令*s代替*p
将S的左子树成为S的双亲Q的右子树，用S取代p 。 若C无右子树，用C取代p。
例：请从下面的二叉排序树中删除结点P。
F P
法1:
F
P
C
PR
C
PR
CL Q
CL QL
Q SL
S PR
QL S
SL
法2:
F
PS
C
PR
CL Q
QL SL S SL

平衡树——特点：所有结点左右子树深度差≤1排序树——特点：所有结点―左小右大字典树——由字符串构成的二叉排序树判定树——特点：分支查找树（例如12个球如何只称3次便分出轻重）带权树——特点：路径带权值（例如长度）最优树——是带权路径长度最短的树，又称Huffman树，用途之一是通信中的压缩编码。

1.1 二叉排序树：或是一棵空树；或者是具有如下性质的非空二叉树：（1）若左子树不为空，左子树的所有结点的值均小于根的值；（2）若右子树不为空，右子树的所有结点均大于根的值；（3）它的左右子树也分别为二叉排序树。

例：二叉排序树如图9.7：二叉排序树的查找过程和次优二叉树类似，通常采取二叉链表作为二叉排序树的存储结构。

中序遍历二叉排序树可得到一个关键字的有序序列，一个无序序列可以通过构造一棵二叉排序树变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。

每次插入的新的结点都是二叉排序树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。

搜索,插入,删除的复杂度等于树高，期望O(logn),最坏O(n)(数列有序,树退化成线性表).虽然二叉排序树的最坏效率是O(n),但它支持动态查询,且有很多改进版的二叉排序树可以使树高为O(logn),如SBT,AVL,红黑树等.故不失为一种好的动态排序方法.2.2 二叉排序树b中查找在二叉排序树b中查找x的过程为：1. 若b是空树，则搜索失败，否则：2. 若x等于b的根节点的数据域之值，则查找成功；否则：3. 若x小于b的根节点的数据域之值，则搜索左子树；否则：4. 查找右子树。

[cpp]view plaincopyprint?1.Status SearchBST(BiTree T, KeyType key, BiTree f, BiTree &p){2. //在根指针T所指二叉排序樹中递归地查找其关键字等于key的数据元素，若查找成功，3. //则指针p指向该数据元素节点，并返回TRUE，否则指针P指向查找路径上访问的4. //最好一个节点并返回FALSE，指针f指向T的双亲，其初始调用值为NULL5. if(!T){ p=f; return FALSE;} //查找不成功6. else if EQ(key, T->data.key) {P=T; return TRUE;} //查找成功7. else if LT(key,T->data.key)8. return SearchBST(T->lchild, key, T, p); //在左子树继续查找9. else return SearchBST(T->rchild, key, T, p); //在右子树继续查找10.}2.3 在二叉排序树插入结点的算法向一个二叉排序树b中插入一个结点s的算法，过程为：1. 若b是空树，则将s所指结点作为根结点插入，否则：2. 若s->data等于b的根结点的数据域之值，则返回，否则：3. 若s->data小于b的根结点的数据域之值，则把s所指结点插入到左子树中，否则：4. 把s所指结点插入到右子树中。

算法（平衡⼆叉树）科普⼆叉树⼆叉树⼆叉数是每个节点最多有两个⼦树,或者是空树(n=0),或者是由⼀个根节点及两个互不相交的,分别称为左⼦树和右⼦树的⼆叉树组成满⼆叉树有两个⾮空⼦树(⼆叉树中的每个结点恰好有两个孩⼦结点切所有叶⼦结点都在同⼀层)也就是⼀个结点要么是叶结点，要么是有两个⼦结点的中间结点。

深度为k且含有2^k-1个结点的⼆叉树完全⼆叉树从左到右依次填充从根结点开始，依次从左到右填充树结点。

除最后⼀层外，每⼀层上的所有节点都有两个⼦节点，最后⼀层都是叶⼦节点。

平衡⼆叉树AVL树[3,1,2,5,9,7]⾸先科普下⼆叉排序树⼜称⼆叉查找树,议程⼆叉搜索树⼆叉排序树的规则⽐本⾝⼤放右边,⽐本⾝⼩放左边平衡⼆叉数⾸先是⼀个⼆叉排序树左右两个⼦树的⾼度差不⼤于1下⾯图中是平衡的情况下⾯是不平衡的情况引⼊公式(LL)右旋function toateRight(AvlNode){let node=AvlNode.left;//保存左节点 AvlNode.left=node.right;node.right=AvlNode;}(RR)左旋function roateLeft(AvlNode){let node=AvlNode.right;//保存右⼦节点AvlNode.right=node.left;node.left=AvlNode;return node;}左右旋⼤图判断⼆叉树是不是平衡树⼆叉树任意结点的左右⼦树的深度不超过1深度计算定义⼀个初始化的⼆叉树var nodes = {node: 6,left: {node: 5,left: {node: 4},right: {node: 3}},right: {node: 2,right: {node: 1}}}//计算⾼度const treeDepth = (root) => {if (root == null) {return 0;}let left = treeDepth(root.left)let right = treeDepth(root.right)return 1+(left>right?left:right)}//判断深度const isTree=(root)=>{if (root == null) {return true;}let left=treeDepth(root.left)let right=treeDepth(root.right)let diff=left-right;if (diff > 1 || diff < -1) {return false}return isTree(root.left)&&isTree(root.right) }console.log(isTree(nodes))判断⼆叉数是不是搜索⼆叉树//第⼀种 //中序遍历let last=-Infinity;const isValidBST=(root)=>{if (root == null) {return true;}//先从左节点开始if (isValidBST(root.left)) {if (last < root.node) {last=root.node;return isValidBST(root.right)}}return false}console.log(isValidBST(nodes))//第⼆种const isValidBST = root => {if (root == null) {return true}return dfs(root, -Infinity, Infinity)}const dfs = (root, min, max) => {if (root == null) {return true}if (root.node <= min || root.node >= max) {return false}return dfs(root.left, min, root.node) && dfs(root.right, root.node, max)}console.log(isValidBST(nodes))实现⼀个⼆叉树实现了⼆叉树的添加,删除,查找,排序//⼆叉树结点class TreeNode {constructor(n, left, right){this.n = n;this.left = left;this.right = right;}}//⼆叉树class BinaryTree {constructor(){this.length = 0;this.root = null;this.arr = [];}//添加对外⼊⼝，⾸个参数是数组，要求数组⾥都是数字，如果有不是数字则试图转成数字，如果有任何⼀个⽆法强制转成数字，则本操作⽆效 addNode(){let arr = arguments[0];if(arr.length == 0) return false;return this.judgeData('_addNode', arr)}//删除结点deleteNode(){let arr = arguments[0];if(arr.length == 0) return false;return this.judgeData('_deleteNode', arr)}//传值判断，如果全部正确，则全部加⼊叉树judgeData(func, arr){let flag = false;//任何⼀个⽆法转成数字，都会失败if(arr.every(n => !Number.isNaN(n))){let _this = this;arr.map(n => _this[func](n));flag = true;}return flag;}//添加的真实实现_addNode(n){n = Number(n);let current = this.root;let treeNode = new TreeNode(n, null, null);if(this.root === null){this.root = treeNode;}else {current = this.root;while(current){let parent = current;if(n < current.n){current = current.left;if(current === null){parent.left = treeNode;}}else {current = current.right;if(current === null){parent.right = treeNode;}}}}this.length++;return treeNode;}//删除节点的真实实现_deleteNode(n){n = Number(n);if(this.root === null){return;}//查找该节点，删除节点操作⽐较复杂，为排除找不到被删除的节点的情况，简化代码，先保证该节点是存在的，虽然这样做其实重复了⼀次查询了，但⼆叉树的查找效率很⾼，这是可接受的let deleteNode = this.findNode(n);if(!deleteNode){return;}//如果删除的是根节点if(deleteNode === this.root){if(this.root.left === null && this.root.right === null){this.root = null;}else if(this.root.left === null){this.root = this.root.right;}else if(this.root.right === null){this.root = this.root.left;}else {let [replaceNode, replacePNode, rp] = this.findLeftTreeMax(deleteNode);replacePNode[rp] = null;replaceNode.left = this.root.left;replaceNode.right = this.root.right;this.root = replaceNode;}}else {//被删除的⽗节点，⼦节点在⽗节点的位置p，有left,right两种可能let [deleteParent, p] = this.findParentNode(deleteNode);if(deleteNode.left === null && deleteNode.right === null){deleteParent[p] = null;}else if(deleteNode.left === null){deleteParent[p] = deleteNode.right;}else if(deleteNode.right === null){deleteParent[p] = deleteNode.left;}else {//⽤来替换被删除的节点，⽗节点，节点在⽗节点的位置let [replaceNode, replacePNode, rp] = this.findLeftTreeMax(deleteNode);if(replacePNode === deleteNode){deleteParent[p] = replaceNode;}else {deleteParent[p] = replaceNode;replacePNode.right = null;}replacePNode[rp] = null;replaceNode.left = deleteNode.left;replaceNode.right = deleteNode.right;}}this.length--;}//查找findNode(n){let result = null;let current = this.root;while(current){if(n === current.n){result = current;break;}else if(n < current.n){current = current.left;}else {current = current.right;}}return result;}//查找⽗节点findParentNode(node){let [parent, child, p] = [null, null, null];if(this.root !== node){parent = this.root;if(node.n < parent.n){child = parent.left;p = 'left';}else {child = parent.right;p = 'right';}while(child){if(node.n === child.n){break;}else if(node.n < child.n){parent = child;child = parent.left;p = 'left';}else {parent = child;child = parent.right;p = 'right';}}}return [parent, p];}//查找当前有左⼦树的节点的最⼤值的节点M，如有A个节点被删除，M是最接近A点之⼀（还有⼀个是右⼦树节点的最⼩值） findLeftTreeMax(topNode){let [node, parent, p] = [null, null, null];if(this.root === null || topNode.left === null){return [node, parent, p];}parent = topNode;node = topNode.left;p = 'left';while(node.right){parent = node;node = node.right;p = 'right';}return [node, parent, p];}//查找最⼤值maxValue(){if(this.root !== null){return this._findLimit('right');}}//查找最⼩值minValue(){if(this.root !== null){return this._findLimit('left');}}//实现查找特殊值_findLimit(pro){let n = this.root.n;let current = this.root;while(current[pro]){current = current[pro];n = current.n;}return n;}//中序排序,并⽤数组的形式显⽰sortMiddleToArr(){this._sortMiddleToArr(this.root);return this.arr;}//中序⽅法_sortMiddleToArr(node){if(node !== null){this._sortMiddleToArr(node.left);this.arr.push(node.n);this._sortMiddleToArr(node.right);}}//打印⼆叉树对象printNode(){console.log(JSON.parse(JSON.stringify(this.root)));}}//测试var binaryTree = new BinaryTree();binaryTree.addNode([50, 24, 18, 65, 4, 80, 75, 20, 37, 40, 60]);binaryTree.printNode();//{n: 50, left: {…}, right: {…}}console.log(binaryTree.maxValue());//80console.log(binaryTree.minValue());//4console.log(binaryTree.sortMiddleToArr());// [4, 18, 20, 24, 37, 40, 50, 60, 65, 75, 80] binaryTree.deleteNode([50]);binaryTree.printNode();//{n: 40, left: {…}, right: {…}}排序复习function ArrayList() {this.array = [];}ArrayList.prototype = {constructor: ArrayList,insert: function(item) {this.array.push(item);},toString: function() {return this.array.join();},swap: function(index1, index2) {var aux = this.array[index2];this.array[index2] = this.array[index1];this.array[index1] = aux;},//冒泡排序bubbleSort: function() {var length = this.array.length;for (var i = 0; i < length; i++) {for (var j = 0; j < length - 1 - i; j++) {if (this.array[j] > this.array[j + 1]) {this.swap(j, j + 1);}}}},//选择排序selectionSort: function() {var length = this.array.length;var indexMin;for (var i = 0; i < length - 1; i++) {indexMin = i;for (var j = i; j < length; j++) {if (this.array[indexMin] > this.array[j]) {indexMin = j;}}if (indexMin !== i) {this.swap(indexMin, i);}}},//插⼊排序insertionSort: function() {var length = this.array.length;var j;var temp;for (var i = 1; i < length; i++) {temp = this.array[i];j = i;while (j > 0 && this.array[j - 1] > temp) {this.array[j] = this.array[j - 1];j--;}this.array[j] = temp;}},//归并排序mergeSort: function() {function mergeSortRec(array) {var length = array.length;if (length === 1) {return array;}var mid = Math.floor(length / 2);var left = array.slice(0, mid);var right = array.slice(mid, length);return merge(mergeSortRec(left), mergeSortRec(right)); }function merge(left, right) {var result = [];var il = 0;var ir = 0;while (il < left.length && ir < right.length) {if (left[il] < right[ir]) {result.push(left[il++]);} else {result.push(right[ir++]);}}while (il < left.length) {result.push(left[il++]);}while (ir < right.length) {result.push(right[ir++]);}return result;}this.array = mergeSortRec(this.array);},//快速排序quickSort:function(){function sort(array){if (array.length <= 1) {return array;}var pivotIndex = Math.floor(array.length/2);var pivot = array.splice(pivotIndex,1)[0];var left = [];var right = [];for(var i = 0; i < array.length; i++){if (array[i] < pivot) {left.push(array[i]);}else{right.push(array[i]);}}return sort(left).concat([pivot],sort(right));}this.array = sort(this.array);}};...................................................................................................................############################################################################ ###################################################################################。

9
二叉搜索树插入操作
利用插入操作可以构造一棵二叉搜索树 首先给出结点序列: 首先给出结点序列 13、8、23、5、18、37 、 、 、 、 、
Φ13
8 5 5 18
83 18 5 2 37 23 37 37 18
10
template<class T> void BST<T>::insertNodeHelper(const T& el) { BSTNode<T> *p = root, *prev = 0; while (p != 0) { prev = p; if( p->data < el ) p = p->rchild; else p = p->lchild; } if( root == 0 ) root = new BSTNode<T>(el); else if( prev->data < el ) p = prev->rchild = new BSTNode<T>(el); else p = prev->lchild = new BSTNode<T>(el); } //find a place for inserting new node; //插入节点 插入节点
20
课堂练习
4.14 对于3个关键码值A、B、C，有多 少个不同的二叉搜索树？画出相应二叉 树。
21
平衡的二叉搜索树(AVL)
BST受输入顺序影响 受输入顺序影响
最好O(log n) 最好 最坏O(n) 最坏
怎样使得BST始终保持 始终保持O(log n)级的平衡状态？ 级的平衡状态 怎样使得 始终保持 级的平衡状态？ Adelson-Velskii和Landis发明了AVL树 发明了AVL Adelson-Velskii和Landis发明了AVL树

证！
1.3.3 性质三
包含n个结点的二二叉树的高高度至至少为log2(n + 1)；
证明：根据"性质2"可知，高高度为h的二二叉树最多有2{h}–1个结点。反之，对于包含n个节点的二二
叉树的高高度至至少为log2(n + 1)。
1.3.4 性质四
对任何一一颗二二叉树T，如果其终端结点数为n0 ，度为2的结点数为n2 ，则n0 = n2 + 1 证明：因为二二叉树中所有结点的度数均不不大大于2，所以结点总数(记为n)="0度结点数(n0)" + "1度 结点数(n1)" + "2度结点数(n2)"。由此，得到等式一一。(等式一一) n = n0 + n1 + n2
}
还有一一种方方式就是利利用用栈模拟递归过程实现循环先序遍历二二叉树。这种方方式具备扩展性，它模拟 了了递归的过程，将左子子树不不断的压入入栈，直到null，然后处理理栈顶节点的右子子树。
java
public void preOrder(Node root){ if(root==null)return;
2. 叶子子数为2h 3. 第k层的结点数是：2k−1； 4. 总结点数是2k − 1，且总节点数一一定是奇数。
1.4.2 完全二二叉树
定义：一一颗二二叉树中，只有最小小面面两层结点的度可以小小于2，并且最下一一层的叶结点集中在靠左 的若干干位置上。这样现在最下层和次下层，且最小小层的叶子子结点集中在树的左部。显然，一一颗 满二二叉树必定是一一颗完全二二叉树，而而完全二二叉树未必是满二二叉树。
} root = s.pop(); root = root.right;//如果是null，出栈并处理理右子子树 } }

二叉排序树非递归插入算法
二叉排序树非递归插入算法指的是在二叉排序树中插入一个新
节点时，采用非递归的方式进行操作的算法。

其基本思想是从根节点开始找到插入位置，并将新节点插入到相应位置上。

具体实现过程为：先将新节点插入到二叉排序树的最底层，然后从底层向上逐层调整，使得整个树仍然满足二叉排序树的性质。

在插入过程中，需要从根节点开始一直向下查找，直到找到插入位置为止。

如果插入节点的值大于当前节点的值，则向右子树继续查找；如果插入节点的值小于当前节点的值，则向左子树继续查找。

非递归插入算法相对于递归插入算法具有简单、高效、节省空间等优点，因此在实际应用中被广泛采用。

同时，该算法的实现也相对较为简单，适合初学者学习二叉排序树的基本操作。

- 1 -。

树、⼆叉树、查找算法总结树的定义形式化定义树：T={D，R }。

D是包含n个结点的有限集合（n≥0）。

当n=0时为空树，否则关系R满⾜以下条件:l 有且仅有⼀个结点d0∈D，它对于关系R来说没有前驱结点，结点d0称作树的根结点。

l 除根结点外，每个结点有且仅有⼀个前驱结点。

l D中每个结点可以有零个或多个后继结点。

递归定义树是由n（n≥0）个结点组成的有限集合（记为T）。

其中：l 如果n=0，它是⼀棵空树，这是树的特例；l 如果n>0，这n个结点中存在⼀个唯⼀结点作为树的根结点（root），其余结点可分为m （m≥0）个互不相交的有限⼦集T1、T2、…、Tm，⽽每个⼦集本⾝⼜是⼀棵树，称为根结点root的⼦树。

ð 树中所有结点构成⼀种层次关系！树的基本术语度结点的度：⼀个结点的⼦树的个数树的度：各节点的度的最⼤值。

通常将度为m的树成为m次树或m叉树结点分⽀结点：度不为0的结点（也称⾮终端结点）度为1的结点成为单分⽀结点，度为2的结点称为双分⽀结点叶结点：度为0的结点路径与路径长度路径：两个结点di和dj的结点序列（di，di1，di2，…，dj）。

其中<dx，dy>是分⽀。

路径长度：等于路径所通过的结点数⽬减1（即路径上的分⽀数⽬）结点的层次和树⾼度层次：根结点层次为1，它的孩⼦结点层次为2。

以此类推。

树的⾼度（深度）：结点中的最⼤层次；有序树和⽆序树有序树：若树中各结点的⼦树是按照⼀定的次序从左向右安排的，且相对次序是不能随意变换的⽆序树：和上⾯相反森林只要把树的根结点删去就成了森林。

反之，只要给n棵独⽴的树加上⼀个结点，并把这n棵树作为该结点的⼦树，则森林就变成了⼀颗树。

树的性质性质1：树中的结点数等于所有结点的度数之和加1。

证明：树的每个分⽀记为⼀个度，度数和=分⽀和，⽽再给根节点加个分⽀性质2：度为m的树中第i层上⾄多有mi-1个结点（i≥1）。

性质3 ⾼度为h的m次树⾄多有个结点。