2025-12-14 数据结构整理-(树和堆)

前序遍历,中序遍历,后序遍历,层序遍历

依次为根左右,左根右,左右根,逐层遍历

在递归里打印的顺序也是如此
以前序遍历为例

template <class Type> void BinaryTree<Type>::
PreOrder ( BinTreeNode <Type> *current ) {
    if ( current != NULL ) {
        cout << current→data;
        PreOrder ( current→leftChild );
        PreOrder ( current→rightChild );
    }
}

根据前序和中序画二叉树

线索化二叉树 (Threaded Binary Tree)

简单说来就是空的左指针指向对应遍历顺序的前驱,若自己是第一个节点则为 nullptr,右指针指向对应遍历顺序的后驱,若自己为最后一个节点则为 nullptr.

但我觉得这种不太会考算法,最多考我画画图,所以 pass 掉.

最大堆和最小堆

向下调整算法

调整顺序:自下而上,从右往左,其实就是从尾部节点开始倒着遍历

//最小堆的向下调整算法
template <class Type>
void MinHeap<Type> :: FilterDown ( int start, int
EndOfHeap ) {
    int i = start, j = 2*i+1;
    // j 是 i 的左子女
    Type temp = heap[i];
    while ( j <= EndOfHeap ) {
        if ( j < EndOfHeap && heap[j] > heap[j+1] ) j++; //两子女中选小者
        if ( temp <= heap[j] ) break; //不需要调整
        else { heap[i] = heap[j]; i = j; j = 2*j+1; }
        //相当于把start一直通过swap向下调整到最优位置
    }
    heap[i] = temp;
}

同理可推得最大堆的向下调整算法

void MaxHeap<Type> :: FilterDown(int start,int EndOfHeap){
    int i=start,j=2*i+1;
    Type temp = heap[i];
    while(j<=EndOfHeap){
        if(j<EndofHeap&&heap[j]<heap[j+1]) j++;//两子女选大者
        if(temp>=hep[j]) break;
        else{
            heap[i]=heap[j];
            i=j;
            j=2*j+1;
        }
    }
    heap[i]=temp;
}

插入与向上调整算法

简单说来就是插入到堆的末尾,然后向上逐层调整

//插入
template <class Type>
int MinHeap<Type> :: Insert ( const Type &x ) {
//在堆中插入新元素 x
if ( CurrentSize == MaxHeapSize ) //堆满
{ cout << "堆已满" << endl; return 0; }
heap[CurrentSize] = x;
 //插在表尾
FilterUp (CurrentSize);
 //向上调整为堆
CurrentSize++;
 //堆元素增一
return 1;
}

//调整
template <class Type>
void MinHeap<Type> :: FilterUp ( int start ) {
//从 start 开始,向上直到0,调整堆
    int j = start, i = (j-1)/2; // i 是 j 的父结点
    Type temp = heap[j];
    while ( j > 0 ) {
        if ( heap[i] <= temp ) break;
        else { heap[j] = heap[i]; j = i; i = (i -1)/2; }
    }
    heap[j] = temp;
}

堆的删除

通过把顶端和堆末尾元素交换来把顶端删除

template <class Type>
int MinHeap <Type> :: RemoveMin (Type &x){
    if ( !CurrentSize ){   
        cout << “ 堆已空 " << endl;
        return 0;
    }
    x = heap[0];
    //删除最小元素
    heap[0] = heap[CurrentSize-1];
    CurrentSize--;
    FilterDown ( 0, CurrentSize-1 ); // start, EndOfHeap
    //从0号位置开始自顶向下调整为堆
    return 1;
    }
}

左孩子右兄弟表示法

为了将多叉树转换成二叉树,从上往下遍历,左指针指向第一个孩子,右指针指向同层右边的兄弟
同理,将二叉树转换成多叉树,也是从上往下遍历,根据左右指针重新画图

森林与二叉树的转换

森林转化成二叉树

• 核心转换规则：左孩子右兄弟表示法
• 先将每棵树转二叉树（左孩子右兄弟），再将二叉树按右子节点连接
  用人话说就是把根节点都看成是兄弟就可以了
这样的话沿着根节点的右指针一直遍历拆分下去就可以找到这个森林的原始结构了
  二叉树转换为森林
• 先按右子节点拆分二叉树，再将每棵二叉树还原为原树（逆左孩子右兄弟）

Huffman编码

例题

假定用于通信的电文仅由 8个字母 c1, c2, c3, c4, c5, c6, c7, c8 组成, 各字母在电文中出现的频率
分别为 5, 25, 3, 6, 10, 11, 36, 4。试为这 8 个字母设计不等长 Huffman编码, 并给出该电文的总码数。

答案：257

点击查看流程图

并查集

稍微接触过一点算法的人都知道要怎么写吧

int find(int a){
    if(f[a]==a){
        return a;
    }
    return f[a]=find(f[a]);
}
void unite(int a,int b){
    int fa=find(a),fb=find(b);
    if(fa!=fb){
        f[fb]=fa;
    }
    else return;
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        f[i]=i;
    }
    for(int i=1;i<=m;i++){
        int s,t;
        cin>>s>>t;
        unite(s,t);
    }
    return 0;
}

都用数组来存结点数了却没用数组存母节点吗,有点意思,为了不想让人轻易看懂真的是煞费苦心,我觉得这种代码要是考了就有点sm了,之后有时间我再瞅两眼,没时间就算了.

【例1】请给出下列操作序列的运算结果，其中M是合并，F是查找：M(1,2),M(3,4),M(3,5),M(1,7),M(3,6),M(8,9),M(1,8),M(3,10),M(3,11),M(3,12),M(3,13),M(14,15),M(16,17),M(14,16),M(1,3),M(1,14)
根据树的高度执行合并（高度高的树作为根节点）：
1)画出并查集森林的构造过程。
2)画出存储该并查集的数组。

BST(二叉搜索树,Binary Search Tree)

由于中序遍历是左根右,因此对BST进行中序遍历可以得到从小到大的顺序

很好奇教材上为什么都要故意用些七扭八歪的代码来写数据结构,光这样也就算了,顶多看的时候费力一点,问题是原理都不讲清楚,那就有点过分了.

BST的插入和删除

插入很好理解,递归遇到空节点时直接插入就可以了,
删除需要分为三类

1. 无子女,这个时候直接删除
2. 一个子女,把子女跟自己调换
3. 双子女,寻找作用跟他相同的节点来替换,才不会破坏原二叉树,可以找到中序遍历下的上一个节点或者下一个节点

template <class Type>
void BST<Type>::Remove(const Type& x, BstNode<Type>*& ptr) {
    if (!ptr) return;

    if (x < ptr->data) {
        Remove(x, ptr->leftChild);
    } else if (x > ptr->data) {
        Remove(x, ptr->rightChild);
    } else { // 找到要删除的结点
        if (ptr->leftChild && ptr->rightChild) {
            BstNode<Type>* t = Min(ptr->rightChild);
            ptr->data = t->data;
            Remove(t->data, ptr->rightChild);
        } else {
            BstNode<Type>* t = ptr;
            ptr = (ptr->leftChild) ? ptr->leftChild : ptr->rightChild;
            delete t;
            //一次考虑到无子女和一个子女两种情况
        }
    }
}

例题

编写算法在二叉排序树上找出任意两个不同结点的最近公共祖先。

BiTNode* LCA_BST(BiTNode* root, int p, int q) {
    if (root == p||root ==q)
        return root;

    if (p < root->key && q < root->key)
        return LCA_BST(root->lchild, p, q);
    else if (p > root->key && q > root->key)
        return LCA_BST(root->rchild, p, q);
    else
        return root;
}

AVL树

一棵AVL树或者是空树，或者是具有下列性质的二叉搜索树：它的左子树和右子树都是AVL树，且左子树和右子树的高度之差的绝对值不超过1.

有n个节点的AVL树高度不超过1.44log2​n,这可以由斐波那契数列推出来,只要让右子树一直比左子树高度加一就可以.(后面有例题)

template <class Type>
struct AVLNode {
    Type data;
    int height;
    AVLNode* left;
    AVLNode* right;
    AVLNode(const Type& x)
        : data(x), height(1), left(nullptr), right(nullptr) {}
};

template <class Type>
class AVL {
public:
    void Insert(const Type& x, AVLNode<Type>*& t) {
        if (!t) {
            t = new AVLNode<Type>(x);
            return;
        }

        if (x < t->data) {
            Insert(x, t->left);
            if (height(t->left) - height(t->right) == 2) {
                if (x < t->left->data)
                    t = rotateRight(t);      // LL
                else
                    t = rotateLeftRight(t); // LR
            }
        } else if (x > t->data) {
            Insert(x, t->right);
            if (height(t->right) - height(t->left) == 2) {
                if (x > t->right->data)
                    t = rotateLeft(t);       // RR
                else
                    t = rotateRightLeft(t); // RL
            }
        }

        t->height = max(height(t->left), height(t->right)) + 1;
    }

private:
    int height(AVLNode<Type>* t) {
        return t ? t->height : 0;
    }

    AVLNode<Type>* rotateRight(AVLNode<Type>* k2) {
        AVLNode<Type>* k1 = k2->left;
        k2->left = k1->right;
        k1->right = k2;
        k2->height = max(height(k2->left), height(k2->right)) + 1;
        k1->height = max(height(k1->left), height(k1->right)) + 1;
        return k1;
    }

    AVLNode<Type>* rotateLeft(AVLNode<Type>* k2) {
        AVLNode<Type>* k1 = k2->right;
        k2->right = k1->left;
        k1->left = k2;
        k2->height = max(height(k2->left), height(k2->right)) + 1;
        k1->height = max(height(k1->left), height(k1->right)) + 1;
        return k1;
    }

    AVLNode<Type>* rotateLeftRight(AVLNode<Type>* k3) {
        k3->left = rotateLeft(k3->left);
        return rotateRight(k3);
    }

    AVLNode<Type>* rotateRightLeft(AVLNode<Type>* k3) {
        k3->right = rotateRight(k3->right);
        return rotateLeft(k3);
    }
};

但我真的不想看代码了.下面是我的理解:
记三个节点从上往下依次为a,b,c
则这四种情况分别有

1. a>b>c
2. a<b<c
3. b<c<a
4. a<c<b

• 只需把中间那个节点接上a的原位置就可以保证既满足BST,又能满足高度差为0.
• 第一种情况和第二种情况都只需要把b接到a的位置,然后把结构调整为BST
• 第三种和第四种就需要把c接到a的位置,然后把c的左右孩子按照BST规则接入其他节点

删除算法

template <class Type>
void AVL<Type>::Remove(const Type& x, AVLNode<Type>*& t) {
    if (!t) return;

    if (x < t->data) {
        Remove(x, t->left);
    } else if (x > t->data) {
        Remove(x, t->right);
    } else { // 找到要删除的结点
        if (t->left && t->right) {
            AVLNode<Type>* p = t->right;
            while (p->left) p = p->left;   // 右子树最小结点
            t->data = p->data;
            Remove(t->data, t->right);
        } else {
            AVLNode<Type>* old = t;
            t = t->left ? t->left : t->right;
            delete old;
            return;
        }
    }

    // 更新高度
    t->height = max(height(t->left), height(t->right)) + 1;

    // 重新平衡
    if (height(t->left) - height(t->right) == 2) {
        if (height(t->left->left) >= height(t->left->right))
            t = rotateRight(t);       // LL
        else
            t = rotateLeftRight(t);   // LR
    } else if (height(t->right) - height(t->left) == 2) {
        if (height(t->right->right) >= height(t->right->left))
            t = rotateLeft(t);        // RR
        else
            t = rotateRightLeft(t);   // RL
    }
}

这个要是考了就没天理了,要是给图我倒是能画一画.

例题

高度为5的AVL树最多有多少个节点，最少有多少个节点(叶子节点高度为1)
显然AVL树可以是满二叉树,故直接用满二叉树来算就可以了.
而最少节点只需按照左右子树高度差最多为1来构造即可,构造的时候就很容易发现这是一个递归结构,有以下公式:
f[0]=0,f[1]=1,f[n]=f[n-1]+f[n-2]+1