1.哈夫曼樹的權(quán)值要是正數(shù)，這是根據(jù)408考題得出的結(jié)論
2.對于一個BST或者AVT蟀拷，它的查找長度在查找失敗的情況下是到達(dá)虛擬的查找失敗結(jié)點的父節(jié)點的長度
如圖：若查找第一個失敗的虛擬結(jié)點，那么查找長度是3桂肌，不是4
image.png
3.判斷關(guān)鍵字路徑是否符合二叉排序樹的要求睬棚，可以做出路徑圖抠忘，然后比較是否是滿足要求的路徑（左右子樹和根節(jié)點的大小）
4.平衡二叉樹最后插入的結(jié)點不一定是葉子結(jié)點结耀，因為可能會進(jìn)行平衡調(diào)整
5.度為m的哈夫曼樹留夜，任何一個結(jié)點的度只能是0或者m
6.一個二叉排序樹最好的方向是接近一個二分查找的判定樹
7.大根堆的特點:根節(jié)點的關(guān)鍵字大于等于左右子樹的關(guān)鍵字；大根堆是完全二叉樹
幾個算法題代碼
/*判斷一棵樹是否是二叉排序樹*/
算法思想：使用二叉樹中序遍歷的思想图甜，每次記錄前一個結(jié)點的指針碍粥，
若滿足后面訪問的結(jié)點關(guān)鍵值大于前一個訪問的結(jié)點的關(guān)鍵字值
失分點：沒有處理相同關(guān)鍵值的情況，T->key<=pre->key
bool IsBST(BiTree T, BSTNode *pre)
{
if (T) {
if (!IsBST(T->lchild, pre))
return false;
/*pre在訪問第一個結(jié)點之前為NULL黑毅，然后依次記錄每個訪問的結(jié)點指針*/
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) //判斷當(dāng)前樹是不是平衡樹
return false;
}
return true;
}
參考方法：
采用前序遍歷的遞歸算法(我修改了代碼風(fēng)格嚼摩，便于閱讀)
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結(jié)果保存到棧中，然后輸出
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);
}
}
