二叉搜索树和二叉判定树的关系是什么_二叉搜索树和二叉判定树的关系是什么意思

二叉树的基本概念以及应用（遍历、堆、哈夫曼树、二叉判定树、二叉搜索树、二叉平衡树）
　　完全二叉树

　　在完全二叉树中，只有最下面两层的结点的度可以小于2，最下面一层的叶子结点编号连续集中在靠左的位置上。

　　满二叉树

　　  一棵深度为𝑘，并且有2^𝑘−1个节点的二叉树，为满二叉树。

　　二叉树的性质

　　在非空二叉树的第i层上最多有个2^(𝑖−1)节点
深度为𝑘的二叉树最多有2^𝑘−1个节点
具有n个节点的完全二叉树的深度k=⌊log_2 (n) ⌋+1=⌈log_2 (n+1) ⌉

　　二叉树的遍历

　　先序遍历：若二叉树为空，则空操作返回；否则①先访问根结点；②然后先序遍历左子树；③先序遍历右子树。
中序遍历：若二叉树为空，则空操作返回；否则①中序遍历根结点的左子树；②接着访问根结点；③中序遍历根结点的右子树。
后序遍历：若二叉树为空，则空操作返回；否则①后序遍历根结点的左子树；②后序遍历根结点的右子树；③最后访问根结点。
层次遍历：先访问第一层的结点，再对第二层的所有结点从左往右依次访问，直到访问完最后一层的所有结点。

　　（注意：先序、中序、后序都是递归实现即可，层次遍历类似于广度优先搜索，需要使用队列结构） 

　　由“先序+中序”或者“后序+中序”的遍历结果可以得到唯一的一颗二叉树。 

先/后序确定当前根节点：先序序列的第一个元素为根节点，后序序列的最后一个元素为根节点；
中序遍历结果确定左右子树的节点范围：在中序序列中找到根节点所在位置，前面的是左子树，后面的是右子树

　　struct Node///结点
{
int data;
int lc, rc;
}node[maxn*2]; ///还要算上内部节点的开销，所以开两倍maxn

int tot;///统计已经建立的顶点数量
int create(int len, int pre_st, int in_st) ///递归建树
{
if (len == 0)
return -1;
int me = tot++;
node[me].data = pre[pre_st];///先序序列第一个元素为根结点
for (int left = 0; left < len; ++left)
{
if (in[in_st+left] == pre[pre_st])
{
node[me].lc = create(left, pre_st + 1, in_st);///建左子树
node[me].rc = create(len – left – 1, pre_st + left + 1, in_st + left + 1);
return me;
}
}
}

vector<int>post;
void postorder(int root) ///后序遍历
{
if(root!=-1)
{
postorder(node[root].lc);
postorder(node[root].rc);
post.push_back(node[root].data);
}
}

　　 堆

　　  二叉堆是完全二叉树。二叉堆满足二个特性：1．父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值。2．每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。一般都用数组来表示堆，i结点的父结点下标就为(i-1)/2。它的左右子结点下标分别为2i+1和2i+2。

插入元素

　　目前数组所存元素0->n-1，新插入的元素都将插入到n位置上，然后再从(n-1)/2父结点开始从下至上调整最大堆。 

　　void Insert_heap(int a[], int i)
{
for (int j = (i – 1) / 2; (j >= 0 && i != 0)&& a[i] > a[j]; i = j, j = (i – 1) / 2)
Swap(a[i], a[j]);
}///(i-1)/2表示父结点

 删除元素

　　 对堆的删除都是取出堆顶元素（最大、最小元素），此时先将n-1位置上的元素放到堆顶0号位置，再对0->n-2这样的堆进行从上至下的调整。

　　///从i节点开始调整，n为节点总数。从0开始计算i节点的子节点为 2*i+1, 2*i+2
void AdjustDown(int a[], int i, int n)
{
int j, temp;

temp = a[i];
j = 2 * i + 1;///左孩子
while (j < n)
{
if (j + 1 < n && a[j + 1] > a[j]) //在左右孩子中找最大的
j++;

if (a[j] <= temp)///最大的孩子也比父节点小
break;

a[i] = a[j]; //把较大的子结点往上移动,替换它的父结点
i = j;
j = 2 * i + 1;
}
a[i] = temp;
}
//在最大堆中删除数
void Delete_heap(int a[], int n)
{
Swap(a[0], a[n – 1]);
AdjustDown(a, 0, n – 1);
}

　　哈夫曼树

　　概念：

扩充二叉树：只存在度为0和2的结点组成的二叉树；
结点间的路径长度：树中一个结点到另一个结点所包括的边的数目；
树的内路径长度：从根到所有非叶子结点的路径长度之和；
树的外路径长度：从根到所有叶子结点的路径长度之和；
树的路径长度之和：从根到树 的所有结点的路径长度之和；
结点的带权路径长度：从根到该结点的路径长度与该结点的权值乘积；
树的带权路径长度WPL：树中所有叶子结点的带权路径长度之和
定理：设I和E分别是一棵扩充二叉树的内路径长度和外路径长度，n是树中非叶子结点的数目，则E=I+2n

　　哈夫曼树的特点：

哈夫曼树的结点个数不能是偶数（因为扩充二叉树只有度为0和2的结点）；
一棵哈夫曼树的加权路径长度等于其中所有分支结点（不包括叶子结点）的权值之和；
哈夫曼树是带权路径长度最短的扩充二叉树，权值越大的结点离根结点越近

　　构建哈夫曼树：

　　  用给定的权值构建n个左右子树都为空的二叉树，所有结点都包含在F集合中；从F中选择权值最小和次最小的两棵树作为左右子树（规定左子树比右子树小），然后构建新的二叉树，新二叉树的权值为左右子树权值之和，在F中删除左右子树权值，把新生成的结点权值加入其中；然后重复上述操作，直到F中只有一个结点即为根结点。

　　  假设哈夫曼树中有n个叶子结点，则哈夫曼树中总共有2n-1个结点。实际存储时采用一维数组存储，0号存储单元不使用，1->n号单元分别存储叶子结点，n+1->2n-1单元存储哈夫曼树形成过程中的非叶子结点。

　　typedef struct
{
ElementType Data;///结点的数据域
int w; ///结点的权值
int parent,lchild,rchild;
}HFMTNode;

void CreateHFMTNode(HFMTNode Ht[],int N)
{
int i,j,k,lmin,rmin;///lmin和rmin为最小权值的两个结点位置
int min1,min2;///min1和min2为最小两个结点的权值
for(i=1;i<2N;i++)///初始化数组
Ht[i].parent=Ht[i].lchild=Ht[i].rchild[i]=-1;
for(i=N+1;i<2N;i++)///n+1->2n-1的位置存储新生成的非叶子结点
{
min1=min2=MAX;
lmin=rmin=-1;
for(k=1;k<=i-1;k++)///寻找当前最小的两个结点
{
if(Ht[k].parent==-1)///该结点还没被构造二叉树
{
if(Ht[k].w<min1)
{
min2=min1;rmin=lmin;
min1=Ht[k].w;lmin=k;
}
else if(Ht[k].w<min2)
{
min2=Ht[k].w;rmin=k;
}
}
}
Ht[lmin].parent=i;Ht[rmin].parent=i;
Ht[i].w=Ht[lmin].w+Ht[rmin].w;
Ht[i].lchild=lmin;Ht[i].rchild=rmin;
}
}

　　 哈夫曼编码：

　　  给使用频率较高的字符进行较短的编码，是一种可变长编码，同时哈夫曼编码也是一种前缀编码（任何一个字符编码都不是其它字符编码的前缀），可以保证解码不会产生二义性。一边规定左分支为0，右分支为1

　　二叉判定树

　　  二叉判定树是用于描述解决问题的思路。二叉判定树的根结点是有序表中序号为mid=(n+1)/2的记录，左子树是与有序表1->mid-1的范围存储，根结点的右子树是mid+1]-> n相对应的位置。左子树都比根结点小，右子树都比根结点大。（注意：二叉判定树的形态只与表中元素个数n有关，与表中元素的关键字无关）

　　  平均搜索长度：

搜索成功：As(n)=（每层结点数 × 比较次数(层数) / n
搜索失败：Af(n)=（每层外节点数×比较次数(上一层层数)）/（n+1）

　　二叉搜索树

　　  概念：所有结点的关键字的值都不一样，左子树都比根结点小，右子树都比根结点大，而且根结点的左右子树也都是二叉搜索树。

若中序遍历二叉搜索树，会得到一个关键字递增排列的有序序列。
已知一棵二叉搜索树的先序遍历序列，可以唯一确定一棵二叉树。

　　  删除结点：

待删除的结点没有子树：直接删除
待删除的结点仅有一颗子树：用唯一子树覆盖父结点，原本指向被删除结点的指针改为指向被删除结点的子树
待删除的结点有两颗子树：使待删除结点的左子树代替被删除的结点，将被删除结点的右子树放置于被删除结点的左子树的最右边

　　二叉平衡树

　　可以是空树
假如不是空树，任何一个结点的左子树与右子树都是平衡二叉树，并且高度之差的绝对值不超过1
二叉平衡树是建立在二叉搜索树的基础上，为了维护二叉搜索树的高度，设置了平衡因子

　　调整二叉平衡树：

从新插入结点回溯，找到第一个非平衡结点标为s，s向下的子树为r
s-r为LL型：以r为结点向上提；
s-r为LR型：再将r的孩子标为u，以u为根结点，r和s分别为u的孩子（根据左小右大的原则分布）