完全⼆叉搜索树
完全⼆叉搜索树是两个概念的包含，即完全⼆叉树+⼆叉搜索树。⼆叉搜索树是⼀棵⼆叉树，以根结点为中⼼，根结点左⼦树的所有结点权值均⼩于根结点的权值，根结点右⼦树的所有结点权值均⼤于根结点的权值。
二叉树的基本性质⽽完全⼆叉树指从根结点到倒数第⼆层满⾜完美⼆叉树，最后⼀层可以不完全填充，其叶⼦结点都靠左对齐。
（完美⼆叉树：⼜叫满⼆叉树，指⼀个深度为k(>=-1)且有2^(k+1) - 1个结点的⼆叉树称为完美⼆叉树。）
完全⼆叉树：
完全⼆叉搜索树的要求是按照给定序列建出⼀棵完全⼆叉树，同时这棵完全⼆叉树满⾜⼆叉搜索树的性质。举个例⼦：把0123456789这个序列建⼀棵完全⼆叉搜索树，得到的树应该是这个样⼦的：
接下来是核⼼算法的思路：⾸先我们可以把给定的序列从⼩到⼤排序，例如0123456789。然后我们想，我们最后建成的树是满⾜⼆叉搜索树的性质，即根结点左⼦树的所有结点的权值均⼩于根结点的权值，根结点右⼦树的所有结点的权值均⼤于根结点的权值，所以，如果我们知道这棵树根结点的左⼦树⼀共有n个结点，那么就可以知道根结点的权值是从⼩到⼤排列完后序列中的第n+1位的数字。为什么可以这样做？因为这利⽤到了完全⼆叉树的性质，当给定⼀个确定的k（k是结点数），那么这个完全⼆叉树就是固定不变的了。⽐如棵树：
0-9有是个数，也就是k=10；所以以此序列构建出的完全⼆叉搜索树根结点的左⼦树⼀定含有6个结点。所以根结点的值就是序列中的第7位的数字（也就是“6”）。同时我们也就可以知道“6”之后的数7、8、9是右⼦树的结点的值。
当我们填了第⼀个数根结点的值6之后，就可以递归的处理左右⼦树。因为如果⼀棵⼆叉树是完全⼆叉树的话，那么它的左⼦树和右⼦树也⼀定是完全⼆叉树。所以可以⽤递归处理。
例如填完根结点后，继续看左⼦树，根结点的左⼦树⼀共有6个结点，⼀棵k=6的完全⼆叉树的左⼦树⼀定包含三个结点，所以左⼦树的根节点的值填⼊“3”，同时知道该左⼦树的右结点⼀定包含4和5这两个结点。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。