二叉树

树

Part I	Part II
二叉树	哈夫曼树

二叉树

二叉树的定义

typedef struct BiNode
{
    ElemType data;
    BiNode *lchild, *rchild;
} *BiTree;

二叉树的先序遍历 DLR

bool PreOrderTraverse(BiTree &T)
{
    if(T == nullptr)
    {
        return true;
    }
    //访问根结点
    visit(T);
    //递归遍历左孩子
    PreOrderTraverse(T->lchild);
    //递归遍历右孩子
    PreOrderTraverse(T->rchild);
    return true;
}

如何理解这个算法？通过画图，描述函数的调用时机，其实还是比较简单

以这个三结点的二叉树为例

三结点二叉树

算法执行过程

二叉树的中序遍历 LDR

bool InOrderTraverse(BiTree &T)
{
    if (T == nullptr)
    {
        return true;
    }
    //第一步：访问左孩子
    InOrderTraverse(T->lchild);
    //第二步：访问根结点
    visit(T);
    //第三步：访问右孩子
    InOrderTraverse(T->rchild);
    return true;
}

二叉树的后序遍历 LRD

bool PostOrderTraverse(BiTree &T)
{
    if (T == nullptr)
    {
        return true;
    }
    //第一步：访问左孩子
    PostOrderTraverse(T->lchild);
    //第二步：访问右孩子
    PostOrderTraverse(T->rchild);
    //第三步：访问根结点
    visit(T);
    return true;
}

三种算法的时间复杂度：O(n)，空间复杂度：O(n)

三种算法的思想都是DFS（深度优先算法）

二叉树的中序遍历——非递归算法

void LDR(BiTree &T)
{
    //第一步：创建一个栈，用于保存二叉树的结点
    SqStack S;
    InitSqStack(S);
    BiTree p = T;
    while( p || !IsEmpty(S))
    {
        if(p)
        {
            //根结点进栈，遍历左子树
            Push(S, p);
            p = p->lchild;
        }
        else
        {
            //根结点出栈，输出根结点，遍历右子树
            Pop(S, p);
            visit(p);
            p = p->rchild;
        }
    }
}

二叉树的层次遍历算法

void LevelOrder(BiTree &S)
{
    /*
    算法设计思路：
    1.将根结点入队
    2.队列不为空时循环，从队列中出列一个元素，访问它，并作以下步骤：
        2.1 如果该元素的左孩子不为空，让该元素的左孩子入队
        2.2 如果该元素的右孩子不为空，让该元素的右孩子入队
    */
    SqQueue Q;
    InitSqQueue(Q); //初始化队列

    BiTree p;
    PushQueue(Q, S); //根结点指针进入队列
    while (!QueueEmpty(Q)) //队不为空，则循环
    {
        //将根结点出队
        DeQueue(Q, p);
        //访问根结点
        cout << p->data << endl;
        //if判断，是否能将根结点的左右孩子进队
        if (p->lchild != nullptr)
        {
            PushQueue(Q, p->lchild); //有左孩子时将其进队
        }
        if (p->rchild != nullptr)
        {
            PushQueue(Q, p->rchild); //有右孩子时将其进队
        }
    }
}

二叉树的建立（DLR先序遍历，递归算法）

bool CreatBiTree(BiTree &T)
{
    ElemType input;
    cin >> input;
    if(input == -1)//建立空结点的标志为 -1（这个自己设定一个就好）
        return false;
    T = new BiNode;
    //D
    T->data = input;
    //L
    CreatBiTree(T->lchild);
    //R
    CreatBiTree(T->rchild);
    return true;
}

二叉树的复制

bool CopyBiTree(const BiTree& T, BiTree& NewT)
{
    if (T == nullptr) { //如果是空树返回0
        return false;
    }
    NewT = new BiNode; //申请新结点空间
    //D
    NewT->data = T->data; //复制根结点
    //L
    CopyBiTree(T->lchild, NewT->lchild); //递归复制左子树
    //R
    CopyBiTree(T->rchild, NewT->rchild); //递归复制右子树
    return true;
}

求二叉树的深度

int Depth(BiTree &T)
{
    if(T == nullptr)
    {
        return 0;
    }
    int m = Depth(T->lchild);
    int n = Depth(T->rchild);
    if(m>n) //二叉树的深度为m与n的较大者加1
        return m+1;
    else
        return n+1;
}

​ 如何理解这个算法？

在我看来，二叉树的深度计算算法，是把二叉树的递归调用运用的淋漓尽致

首先，二叉树 = 根结点+左子树+右子树；右子树=根结点+左子树+右子树；左子树=根结点+左子树+右子树。。。如此循环反复，因此，我们对二叉树模型进行运算，只需要像剥洋葱一样，一层一层把二叉树剖开，把一个复杂二叉树的运算求解问题，分解成一个个的单结点二叉树（叶子结点）问题的累加，就会比较方便

这个深度计算算法，就是这个思想。用递归函数一层层分解二叉树，递归的到叶子结点。例如，当我们第一个叶子结点的的左孩子和右孩子都是空时，叶子结点的m和n都等于0，再通过一个if判断语句，让m和n中的较大值加1。也即叶子结点返回1，这个返回值就放在叶子结点的双亲的m中，再去看这个双亲的右孩子，循环反复，最后就能得到二叉树的深度。

求二叉树的结点数

int CountNode(BiTree &T)
{
    if (T == nullptr)
    {
        return 0;
    }
    // //L
    // int m = CountNode(T->lchild);
    // //R
    // int n = CountNode(T->rchild);
    // //
    // return m + n + 1;
    //更加简单的语句
    //结点个数为：左子树的结点个数+右子树的结点个数+1
    return CountNode(T->lchild) + CountNode(T->rchild) + 1;
}

求二叉树的叶子结点数

//王卓老师的视频范例
int Count0Node(BiTree &T)
{
    //③：递归函数将上一个结点剖分成左右子树，如果结点的孩子为空，那么返回0
    //这里不会出现结点的两个孩子都是空的，因为上一个结点执行这个递归函数的时候就已经判断了这种情况
    //这个语句只是为了以下两种情况而存在的：
    //1. 空树
    //2. 某个分支结点只有一个孩子
    if (T == nullptr)
    {
        return 0;
    }
    //①：其实呢，我们还是可以把这个问题拆分成左子树和右子树的统计问题
    if (T->lchild == nullptr && T->rchild == nullptr)
    {
        //以T为根结点的这棵树，左右孩子都没有，那他就是叶子结点
        return 1;
    }
    //②：如果不是这个情况，就说明这个根结点至少有一个孩子，还要继续剖分这个结点
    return Count0Node(T->lchild) + Count0Node(T->rchild);
}

//我自己写的程序，确实有一点拉胯
/*
参数n：用于统计叶子结点数
参数flag：用于判断某个结点的两个孩子是否都为空
*/
bool Count0Node(BiTree &T, int &n, int &flag)
{
    if (T == nullptr)
    {
        flag = 1; //标志
        return false;
    }
    if (flag == 1)
    {
        ++n;
        flag = 0;
    }
    //L
    Count0Node(T->lchild, n, flag);
    //R
    Count0Node(T->rchild, n, flag);
    return true;
}

---

哈夫曼树

哈夫曼树的定义

typedef struct HNode
{
    int weight;                 //权重
    int parent, lchild, rchild; //每个结点的双亲、左右孩子的数组下标
} * HuffmanTree;

哈夫曼树的初始化

void InitHTree(HuffmanTree& H, const int n)
{
    //哈夫曼树的存储结构为顺序存储
    //由哈夫曼树的构造过程得知，n个权重结点构造出的哈夫曼树具有2*n-1个结点
    //通常哈夫曼树的顺序存储结构下标从1开始计数，因此，如果我们使用数组实现的话
    //那么数组的长度应该是2*n
    H = new HNode[2 * n];
    for (int i = 1; i < 2 * n; ++i) //将2n-1个元素的lchild,rchild,parent置为0
    {
        H[i].parent = H[i].lchild = H[i].rchild = 0;//右结合律
    }
    int input;
    for (int i = 1; i <= n; ++i)
    {
        cin >> input;
        H[i].weight = input; //输入前n个元素的weight值
    }
}

哈夫曼树的构造算法

void CreatHuffman(HuffmanTree &H, const int length)
{
    //第一步：对哈夫曼树进行初始化
    InitHTree(H, length);
    //第二步：找出当前森林中最小的两棵树，创建新树，并让原来的两个树作为新树的孩子
    for (int i = length + 1; i < 2 * length; ++i) //合并产生n-1个结点——构造Huffman树
    {
        int i1 = 0, i2 = 0;
        Select(H, i - 1, i1, i2);//重点是这个Select算法
        H[i].weight = H[i1].weight + H[i2].weight;//i的权值为左右孩子权值之和
        H[i1].parent = H[i2].parent = i; //表示从F中删除s1，s2
        H[i].lchild = i1; //s1，s2分别作为i的左右孩子
        H[i].rchild = i2;
    }
}

Select算法

void Select(HuffmanTree &H, const int n, int &i1, int &i2)
{
    vector<int> vec;
    for (int i = 1; i <= n; ++i)
    {
        if (H[i].parent == 0)
        {
            vec.push_back(i);
        }
    }
    //找出最小的一个
    auto flag1 = vec.begin();
    for (auto it = vec.begin() + 1; it != vec.end(); ++it)
    {
        if (H[*it].weight < H[*flag1].weight)
        {
            flag1 = it;
        }
    }
    i1 = *flag1; //最小的元素下标
    vec.erase(flag1);
    auto flag2 = vec.begin();
    for (auto it = vec.begin() + 1; it != vec.end(); ++it)
    {
        if (H[*it].weight < H[*flag2].weight)
        {
            flag2 = it;
        }
    }
    i2 = *flag2; //第二小的元素的下标
}

哈夫曼编码算法

void HuffmanCode(HuffmanTree &H, const int n)
{
    //第一步：调用函数创建一个顺序存储结构的哈夫曼树，同上的函数一样
    CreatHuffman(H, n);
    //第二步：遍历哈夫曼树中每一个叶子结点，也即哈夫曼数组中的前n个元素
    for (int i = 1; i <= n; ++i)
    {
        int chd = i;
        int par = H[chd].parent;
        //自下而上得到哈夫曼编码，用栈来保存再合适不过了
        SqStack S;
        InitStack(S);
        while (par != 0) //从叶子结点开始向上回溯，直到根结点
        {
            H[par].lchild == chd ? /*左孩子，0进栈*/ Push(S, 0) : /*右孩子，1进栈*/ Push(S, 1);
            //继续向上回溯
            chd = par;
            par = H[chd].parent;
        }
        //出栈//黑框中打印编码
        while (!IsEmpty(S))
        {
            int out;
            Pop(S, out);
            cout << out;
        }
        cout << endl;
    }
}

有注意到一个问题，在严蔚敏版《数据结构》C语言一书中，在哈夫曼树的构造算法中，两个拥有相同双亲的叶子结点，左右位置是可以相互交换的。这会让人产生困惑：由相同的权重结点构造出来的哈夫曼树是不唯一的，那么我通过哈夫曼树的得到编码也是不唯一的，这怎么搞？

本篇完~