1.哈夫曼树的权值要是正数，这是根据408考题得出的结论
2.对于一个BST或者AVT，它的查找长度在查找失败的情况下是到达虚拟的查找失败结点的父节点的长度
如图：若查找第一个失败的虚拟结点，那么查找长度是3，不是4
image.png
3.判断关键字路径是否符合二叉排序树的要求，可以做出路径图，然后比较是否是满足要求的路径（左右子树和根节点的大小）
4.平衡二叉树最后插入的结点不一定是叶子结点，因为可能会进行平衡调整
5.度为m的哈夫曼树，任何一个结点的度只能是0或者m
6.一个二叉排序树最好的方向是接近一个二分查找的判定树
7.大根堆的特点:根节点的关键字大于等于左右子树的关键字；大根堆是完全二叉树
几个算法题代码
/*判断一棵树是否是二叉排序树*/
算法思想：使用二叉树中序遍历的思想，每次记录前一个结点的指针，
若满足后面访问的结点关键值大于前一个访问的结点的关键字值
失分点：没有处理相同关键值的情况，T->key<=pre->key
bool IsBST(BiTree T, BSTNode *pre)
{
if (T) {
if (!IsBST(T->lchild, pre))
return false;
/*pre在访问第一个结点之前为NULL，然后依次记录每个访问的结点指针*/
if (pre != NULL && T->key < pre->key)
return false;
else
pre = T;
if (!IsBST(T->rchild, pre))
return false;
}
return true;
}
参考方法：
KeyType predt = -32767;
使用全局变量记录pre,但是不是那么的合适似乎
bool JudgeBST(BiTree bt)
{
int b1, b2;
if (bt == NULL)
return true;
else {
b1 = JudgeBST(bt->lchild);
if (b1 == 0)
return false;
if (predt >= bt->data)
return false;
b2 = JudgeBST(bt->rchild);
if (b1 == 0)
return false;
return true;
}
}
int level(BiTree bt, BSTNode *p)
{
int dep = 1;
while (p->key != bt->key) {
dep++;
if (p->key < bt->key)
bt = bt->lchild;
else
bt = bt->rchild;
}
return dep;
}
参考方法：
int level(BiTree bt, BSTNode *p)
{
int n = 0;
BiTree t = bt;
if (bt != NULL) {
n++;
while (t->data != p->data) {
if (p->data < t->data)
t = t->lchild;
else
t = t->rchild;
n++;
}
}
return n;
}
bool IsAVT(BiTree bt, int &h)
{
if (bt) {
int h1 = 0, h2 = 0;
if (!IsAVT(bt->lchild)) //判断左子树是不是平衡树
return false;
if (!IsAVT(bt->rchild)) //判断右子树是不是平衡树
return false;
if (h1 - h2 >= 2 || h2 - h1 >= 2) //判断当前树是不是平衡树
return false;
}
return true;
}
参考方法：
采用前序遍历的递归算法(我修改了代码风格，便于阅读)
void Judeg_AVT(BiTree bt, int &balance, int &h)
{
int bl, br, hl, hr;
if (bt == NULL) {
balance = 1;
h = 0;
}
else if(bt->lchild==NULL && bt->rchild==NULL) {
balance = 1;
h = 1;
}
else {
Judeg_AVT(bt->lchild,bl,hl);
Judeg_AVT(bt->rchild,br,hr);
if (h1 > h2)
h = h1 + 1;
else
h = h2 + 1;
if (h1 - h2 <= 1 || h2 - h1 <= 1)
h = hl & hr;
else
h = 0;
}
}
参考方法：
KeyType MinKey(BiTree bt)
{
while (bt->lchild != NULL)
bt = bt->lchild;
return bt->data;
}
KeyType MaxKey(BiTree bt)
{
while (bt->rchild != NULL)
bt = bt->rchild;
return bt->data;
}
算法思想：
1.使用正常的中序遍历，>=k结果保存到栈中，然后输出
2.使用RNL的遍历次序，这样可以先输出最大值，然后最小值
void print(BiTree bt, KeyType k)
{
if (bt) {
print(bt->rchild)
if (bt->key >= k) {
visit(bt->key);
print(bt->lchild);
}
}
}
参考方法：
它给出的两种方法就是我给出的两种思路，哈哈哈哈
BSTNode* SearchK(BiTree bt, int k)
{
if (bt){
if (bt->lchild) {
if (bt->lchild->count >= k)
return SearchK(bt->lchild,k);
else if (bt->lchild->count + 1 == k)
return bt;
else
return SearchK(bt->rchild,k-bt->lchild->count-1);
}
else {
if (k == 1)
return bt;
else
return SearchK(bt->rchild,k-1);
}
}
return NULL;
}
参考方法：
BSTNode* Search_Small(BiTree bt, int k)
{
if (k < 1 || k>bt->count) /*这个我忘了啊*/
return NULL;
if (bt->lchild == NULL) {
if (k == 1)
return bt;
else
return Search_Small(bt->rchild,k-1);
}
else {
if (bt->lchild->count == k - 1)
return bt;
else if (bt->lchild->count > k - 1)
return Search_Small(bt->lchild, k);
else
return Search_Small(bt->rchild,k-1-bt->lchild->count);
}
}
