Rookie's blog

Chapter 5 树

Chapter 5 树

树状结构

  • 非线性结构
  • 层次和从属关系
  • 树（第五章）和优先级队列（第六章）

树的定义

树的递归定义

树是n个集合的有限集合T，它或者是空集，或者满足：

  1. 有一个被称为根(root)的节点
  2. 其余的节点可以分为m个互不相交的子集T1,T2⋯TnT_1,T_2 \cdots T_n，其中每个子集也是一棵树，称为子树(subtree)

树的术语

  • 根节点，叶节点（末端节点，无分叉），内部节点
  • 节点的度和树的度
    • 节点的度：一个节点的直接后继的数目
    • 树的度：树中所有节点的度的最大值
  • 逻辑关系：子节点，父节点，兄弟节点，祖先节点，子孙节点
  • 结点所处层次
  • 树的高度
  • 有序树和无序树
    • 有序树：将一棵树的节点看成自左向右有序
    • 无序树：无序，节点顺序无关
  • 森林：M棵互不相交的树的集合称为森林

树的运算

  • 建树
  • 清空
  • 判空
  • 树节点
  • 找父节点
  • 找字节点
  • 删除
  • 遍历

树的抽象类

二叉树

二叉树的定义

二叉树或是空集，或由一个根节点和两个左右子树组成，而其左右子树又都是二叉树。

  • 二叉树是有序树，必须严格区分左右子树。

满二叉树

如果一棵二叉树中的任意一层的结点个数都达到了最大值，那么这棵树为满二叉树

一个kk层的满二叉树，具有2k−12^k -1个节点

完全二叉树

最底层可以不满，其他层都满，且最底层从左到右依次存放

完全二叉树相当于满二叉树最底层自右向左去掉若干个节点

二叉树的性质

  • 具有nn个节点的完全二叉树的高度kk为

k=[log⁡2n]+1k = [\log_2{n}] + 1

  • 对于完全二叉树，（假设起始编号为0）节点i的左子树节点编号为2i2i，右子树节点编号为2i+12i+1
  • 对于完全二叉树，（假设其实编号为0）节点ii的父节点编号为[i2][\dfrac{i}{2}]
  • 对于一棵非空二叉树，如果叶节点数为n0n_0，度数为2的节点为n2n_2，则有n0=n2+1n_0 = n_2 + 1

证明：连接数从发出者来说，可以写成2n2+n12n_2+n_1，从接收者来说，可以写成n0+n1+n2−1n_0 + n_1 + n_2 -1

2n2+n1=n0+n1+n2−1  ⟹  n0=n2+12n_2+n_1 = n_0 + n_1 + n_2 -1 \implies n_0 = n_2 + 1

二叉树的基本运算

  • 建树create()
  • 清空clear()
  • 判空IsEmpty()
  • 找根节点root()
  • 找父节点parent()
  • 找左孩子lchild()
  • 找右孩子rchile()
  • 删除左子树delLeft()
  • 删除右子树delRight()
  • 遍历traverse()

二叉树的遍历

  • 二叉树是有分叉的，因此在分叉处必须确定下一个要访问的节点：是根节点，左节点还是右节点
  • 据此，有三种遍历方法：前序，中序，后序
  • 还有层次遍历方法

前序遍历

  • 访问根节点
  • 如果左子树非空，前序遍历左子树
  • 如果右子树非空，前序遍历右子树

中序遍历

  • 如果左子树非空，中序遍历左子树
  • 访问根节点
  • 如果右子树非空，中序遍历右子树

后序遍历

  • 如果左子树非空，后序遍历左子树
  • 如果右子树非空，后序遍历右子树
  • 访问根节点

层次遍历

  • 从上到下按层遍历

例子

中序恰好为投影序

从遍历结果确定二叉树

前序+中序 可唯一确定一棵二叉树
  • 先用前序确定当前所在树的根
  • 用中序确定哪些节点在左子树，哪些在右子树
  • 对左子树，右子树分别重复上述操作（递归），直到确定所有节点
后序+中序 可唯一确定一棵二叉树
前序+后序 无法确定

反例：

前序+层次 无法确定
中序+层次 可以
后序+层次 无法确定

二叉树实现

二叉树的抽象类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template<class T>
class bTree {
public:
    virtual void clear() = 0;
    virtual bool isEmpty() const = 0;
    virtual T Root(T flag) const = 0;
    virtual T parent(const T &x,  T flag) const = 0; 
    virtual T lchild (const T &x, T flag) const = 0;
    virtual T rchild (const T &x, T flag) const = 0;
    virtual void delLeft(const T &x) = 0;
    virtual void delRight(const T &x) = 0;
    virtual void preOrder() const = 0;
    virtual void midOrder() const = 0;
    virtual void postOrder() const= 0;
    virtual void levelOrder() const = 0;
};

二叉树的顺序存储

对于完全二叉树而言，可以根据编号性质确定父子关系

对于普通二叉树，修补成完全二叉树进行存储

  • 顺序存储适用于完全二叉树或接近于完全二叉树形状的情况
  • 最好是形状静态（操作过程中树的结构不会有大的变化）的情况
  • 如果形状与完全二叉树相差太多，会有很多空间浪费，树的结构变化会有较大开销

二叉树的链接存储

标准形式（二叉列表）：data数据字段，left左节点指针，right右节点指针

广义标准形式/扩展形式（三叉列表）：二叉列表+一个parent父节点指针

二叉树链接存储时属性为：root根节点指针

二叉树类的定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
template<class T>
class binaryTree : public bTree<T> {
 	friend void printTree(const binaryTree &t, T flag);
private:
    struct Node {                          //二叉树的结点类
        Node  *left , *right ;   
        T data;   
        Node() : left(NULL), right(NULL) {}
        Node(T item, Node *L = NULL, Node * R =NULL ):  data(item), left(L), right(R) {}
        ~Node() {} 
    };
    Node *root; 
public:
    binaryTree() : root(NULL) {}//创建空树
    binaryTree(T x) { root = new Node(x); }//创建只有根节点的树
    ~binaryTree();
    void clear() ;
    bool isEmpty() const;
    T Root(T flag) const;
    T lchild(const T &x, T flag) const;
    T rchild(const T &x, T flag) const; 
    void delLeft(const T &x) ;
    void delRight(const T &x);
    void preOrder() const;
    void midOrder() const;
    void postOrder() const;
    void levelOrder() const;
    void createTree(T flag);//创建树
    T parent(const T &x, T flag) const { return flag; }
private:
    Node *find(const T &x, Node *t ) const;
    void clear(Node *&t);
    void preOrder(Node *t)  const;
    void midOrder(Node *t) const;
    void postOrder(Node *t)  const;
};

注意：
前序，中序，后序遍历在private函数中进行具体实现，然后进行用一个public函数包装private函数

二叉树的递归实现

简单的基本运算：isEmpty()，Root()

1
2
3
4
5
6
7
8
9
10
11
12
template<class T>
bool binaryTree<T>::isEmpty() const {
    return root == NULL;
}

template<class T>
T binaryTree<T>::Root(T flag) const {
    if (root == NULL)
        return flag;
    else
        return root->data;
}

前序遍历：preOrder()

思路：（记得判空）如果输入的节点指针为空，直接返回

然后就是正常的前序遍历思路：

  1. 先访问该节点自身的data
  2. 访问左子树
  3. 访问右子树

中序遍历，后续遍历是类似的，就不赘述了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template<class T>
void binaryTree<T>::preOrder(binaryTree<T>::Node *t)  const
{   
    if (t == NULL) return;
    cout << t->data << ' ';
    preOrder(t->left);
    preOrder(t->right);
}
 
template<class T>
void binaryTree<T>::preOrder()  const
{   
    cout << "\n前序遍历：";
    preOrder(root);
}

中序遍历：midOrder()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<class T>
void binaryTree<T>::midOrder(binaryTree<T>::Node* t) const {
    if (t == NULL)
        return;
    midOrder(t->left);
    cout << t->data << ' ';
    midOrder(t->right);
}

template<class T>
void binaryTree<T>::midOrder() const {
    cout << "\n中序遍历：";
    midOrder(root);
}

后续遍历：postOrder()

1
2
3
4
5
6
7
8
9
10
11
12
13
template<class T>
void binaryTree<T>::postOrder(binaryTree<T>::Node* t) const {
    if (t == NULL)
        return;
    postOrder(t->left);
    postOrder(t->right);
    cout << t->data << ' ';
}
template<class T>
void binaryTree<T>::postOrder() const {
    cout << "\n后序遍历：";
    postOrder(root);
}

练习：节点个数size()

1
2
3
4
5
6
7
8
9
10
11
12
template<class T>
int size(Node * t) const
{
    if(t == NULL) return 0;
    return size(t->left) + size(t->right) + 1;
}

template<class T>
int size() const
{
    return size(root);
}

树的高度height()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<class T>
int binaryTree<T>::height(binaryTree<T>::Node *t)  const
{	   
    if (t == NULL) return 0;
    int lt=height(t->left);
    int rt=height(t->right);
    return 1+((lt>rt)?lt:rt);			  
}			  
 
template<class T>
int binaryTree<T>::height()  const
{   
    return height(root);
}

清空树clear()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template<class T>
void binaryTree<T>::clear(binaryTree<T>::Node *&t)
{
    if (t == NULL)  return;
    clear(t->left);
    clear(t->right);
    delete t;
    t = NULL;
}

template<class T>
void binaryTree<T>::clear()
{
    clear(root);
}

析构

1
2
3
4
5
template <class T>
binaryTree<T>::~binaryTree()
{
    clear(root);
}

层次遍历

  • 利用队列
  • 步骤：若队列非空，一直循环
    • pop取出队首节点
    • 访问该节点自身数据
    • 若左子树非空，左子树入队
    • 若右子树非空，右子树入队
1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<class T>
void binaryTree<T>::levelOrder() const
{
    linkQueue< Node * > que;
    Node *tmp; 
    cout << "\n层次遍历：";
    que.enQueue(root);	 
    while (!que.isEmpty()) {
        tmp = que.deQueue();
        cout << tmp->data << ' ';
        if (tmp->left) que.enQueue(tmp->left);
        if (tmp->right) que.enQueue(tmp->right);
    }
}

遍历查找find(x)

1
2
3
4
5
6
7
8
9
10
template <class T>
struct binaryTree<T>::Node *binaryTree<T>::
       find(const T &x, binaryTree<T>::Node *t) const
{
    Node *tmp;
    if (t == NULL) return NULL;
    if (t->data == x) return t;
    if (tmp = find(x, t->left) ) return tmp;
    else return find(x, t->right);
}

需要使用find()的一些基本操作

delLeft(), delRight(), lchild(x), rchild(x)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
template<class T>
void binaryTree<T>::delLeft(const T& x) {
    Node* tmp = find(x, root);
    if (tmp == NULL)
        return;
    clear(tmp->left);
}

template<class T>
void binaryTree<T>::delRight(const T& x) {
    Node* tmp = find(x, root);
    if (tmp == NULL)
        return;
    clear(tmp->right);
}

template<class T>
T binaryTree<T>::lchild(const T& x, T flag) const {
    Node* tmp = find(x, root);
    if (tmp == NULL || tmp->left == NULL)
        return flag;
    return tmp->left->data;
}

template<class T>
T binaryTree<T>::rchild(const T& x, T flag) const {
    Node* tmp = find(x, root);
    if (tmp == NULL || tmp->right == NULL)
        return flag;
    return tmp->right->data;
}

建树createTree(x)

  • 使用队列，类似层次遍历的思路
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
template <class T>
void BinaryTree<T>::createTree(T flag)
{ 
    linkQueue< Node * > que;
    Node *tmp;
    T x, ldata, rdata;

    //创建树，输入flag表示空
    cout << "\n输入根结点：";
    cin >> x;
    root = new Node(x);
    que.enQueue(root);	  
    while (!que.isEmpty()) 
    {
        tmp = que.deQueue();
        cout << "\n输入" << tmp->data
                << "的两个儿子(" << flag 
                << "表示空结点)：";
        cin >> ldata >> rdata;
        if (ldata != flag)
            que.enQueue(tmp->left = new Node(ldata));
        if (rdata != flag)
        	que.enQueue(tmp->right = new Node(rdata));
    }
    cout << "create completed!\n";
}

二叉树遍历的非递归实现

前序遍历的非递归实现

  • 使用栈
  • 步骤：若栈非空，一直循环
    • pop一个节点
    • 访问该节点，然后先将右子树压入栈，再将左子树压入栈（记得判断非空）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template<typename T>
void binaryTree<T>::preOrder() const {
    stack<Node*> s;
    Node* current;

    cout << "前序遍历：";
    s.push(root);
    while (!s.empty()) {
        current = s.top();
        s.pop();
        cout << current->data;
        if (current->right != NULL)
            s.push(current->right);
        if (current->left != NULL)
            s.push(current->left);
    }
}

中序遍历的非递归实现

  • 使用栈
  • 注意：每个节点要pop两次
    • 每次pop时要做的操作是不一样的
    • 需要改造node类，使之能够存储pop的次数（加个计数器）
    • 最好新建一个结构体StNode来实现这种计数功能
1
2
3
4
5
struct StNode{
    Node *node;
    int pop_times;
    StNode(Node * N = NULL):node(N),pop_times(0) {}
};
  • 步骤：若栈非空，一直循环
    • 若为第一次pop，根重新入栈，然后将左子树压进栈
    • 若为第二次pop，访问根节点，然后将右子树压进栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
template<typename T>
void binaryTree<T>::midOrder() const {
    stack<StNode> s;
    StNode current;

    cout << "\n中序遍历：";
    s.push(root);
    while (!s.empty()) {
        current = s.top();
        s.pop();
        ++current.pop_times;
        if (current.pop_times == 1) {
            s.push(current);
            if (current.node->left != NULL)
                s.push(StNode(current.node->left));
        } else if (current.pop_times == 2) {
            cout << current.node->data;
            if (current.node->right != NULL)
                s.push(StNode(current.node->right));
        }
    }
}

后序遍历的非递归实现

  • 使用栈，类似中序遍历，node类需要存储pop的次数
  • 每个节点要pop三次
  • 步骤：若栈非空，一直循环
    • 若为第一次pop，根重新入栈，然后将左子树压进栈
    • 若为第二次pop，根重新入栈，然后将右子树压进栈
    • 若为第三次pop，访问根节点
改进方法
  • 每个节点只需pop两次
  • 步骤：若栈非空，一直循环
    • 若为第一次pop，根重新入栈，然后先将右子树压入栈，再将左子树压入栈
    • 若为第二次pop，访问该节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
template<typename T>
void binaryTree<T>::postOrder() const {
    stack<StNode> s;
    StNode current;

    cout << "\n后序遍历：";
    s.push(root);
    while (!s.empty()) {
        current = s.top();
        s.pop();
        ++current.pop_times;
        if (current.pop_times == 1) {
            s.push(current);
            if (current.node->right != NULL)
                s.push(StNode(current.node->right));
            if (current.node->left != NULL)
                s.push(StNode(current.node->left));
        } else if (current.pop_times == 2) {
            cout << current.node->data;
        }
    }
}

二叉树遍历算法的应用

  • 计算二叉树中结点的个数、度为1的结点的个数
  • 判断某个元素是否存在、从上到下/从左到右最早出现在哪里？
    • 从上到下：层次遍历
    • 从左到右：中序遍历
  • 计算某个结点的层次数
    • 前中后遍历非递归实现都可，每个节点拉入栈时，将其层数设置为父亲节点层数+1
    • 当遍历到该节点时，即可获得该节点的层数
  • 计算二叉树高度
    • 前中后遍历非递归实现都可，每个节点拉入栈时，将其层数设置为父亲节点层数+1
    • 设置一个变量maxHeight，在遍历过程中记录遇到的层数的最大值
    • 当遍历完该二叉树时，maxHeight的值（层数最大值）即为二叉树高度
  • 计算某个结点的所有子孙
    • 前序遍历：节点出栈后，这个位置及以后出栈的所有节点
  • 计算某个结点的所有祖先
    • 后序遍历非递归实现中，当一个节点pop出来时，栈中前面的所有元素就是它的祖先集合
  • 删除分支
    • 后序遍历，当删除分支的根入栈时，后面所有出栈的结点都删除，直到分支的根出栈为止
  • 构造二叉树、判断是否为满二叉树/完全二叉树
    • 构造：层次遍历
    • 判满/完全二叉树：层次遍历

**注意：**以下代码是gpt写的，看了一下方法没有问题，可能用了一些STL，理解大致思路就可以

计算二叉树高度/某个节点层次数

c此处以前序遍历为例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <stack>

// 二叉树节点定义
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 计算二叉树高度
int getHeight(TreeNode* root) {
    if (!root) return 0;
  
    std::stack<std::pair<TreeNode*, int>> s;
    s.push({root, 1});
    int maxHeight = 0;
  
    while (!s.empty()) {
        TreeNode* node = s.top().first;
        int height = s.top().second;
        s.pop();
      
        maxHeight = std::max(maxHeight, height);
      
        if (node->right) s.push({node->right, height + 1});
        if (node->left) s.push({node->left, height + 1});
    }
  
    return maxHeight;
}

// 查找特定节点的层数
int getLevel(TreeNode* root, TreeNode* target) {
    if (!root) return 0;
    if (root == target) return 1;
  
    std::stack<std::pair<TreeNode*, int>> s;
    s.push({root, 1});
  
    while (!s.empty()) {
        TreeNode* node = s.top().first;
        int level = s.top().second;
        s.pop();
      
        if (node == target) return level;
      
        if (node->right) s.push({node->right, level + 1});
        if (node->left) s.push({node->left, level + 1});
    }
  
    return 0; // 未找到目标节点
}

int main() {
    // 创建一颗二叉树
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(7);

    // 计算二叉树高度
    int height = getHeight(root);
    std::cout << "二叉树高度: " << height << std::endl;

    // 查找特定节点的层数
    TreeNode* targetNode = root->left->right;
    int level = getLevel(root, targetNode);
    std::cout << "节点 " << targetNode->val << " 所在层数: " << level << std::endl;

    return 0;
}

判断完全二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <queue>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

bool isCompleteTree(TreeNode* root) {
    if (root == nullptr) return true;

    std::queue<TreeNode*> q;
    q.push(root);
    bool hasNullChild = false;

    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();

        if (node->left) {
            if (hasNullChild) return false;
            q.push(node->left);
        } else {
            hasNullChild = true;
        }

        if (node->right) {
            if (hasNullChild) return false;
            q.push(node->right);
        } else {
            hasNullChild = true;
        }
    }

    return true;
}

int main() {
    // 创建一个完全二叉树
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);

    if (isCompleteTree(root)) {
        std::cout << "The tree is a complete binary tree." << std::endl;
    } else {
        std::cout << "The tree is not a complete binary tree." << std::endl;
    }

    return 0;
}

哈夫曼树与哈夫曼编码

字符的机内表示

前缀编码

  • 字符只放在叶结点中
  • 字符编码可以有不同的长度
  • 由于字符只放在叶结点中，所以每个字符的编码都不可能是其他字符编码的前缀
  • 前缀编码可被唯一解码
  • 不等长的前缀编码相比等长编码可以更充分的利用空间

哈夫曼树

哈夫曼树是一棵最小代价的二叉树，在这棵树上，所有的字符都包含在叶结点上。

  • 要使得整棵树的代价最小，显然权值大的叶子应当尽量靠近树根，权值小的叶子可以适当离树根远一些。
  • 哈夫曼编码是一种前缀编码

哈夫曼树的结构特点：没有度为1的节点，只有度为0和度为2的节点，且所有字符只存放在叶节点中

想存nn个不同的字符，需要一棵有N=2n−1N = 2n-1个节点的哈夫曼树

哈夫曼编码的生成

  • 每个字符的编码是根结点到该字符的路径
  • 左枝为0，右枝为1，加到编码上就行

哈夫曼树类的实现

  • 为了便于找出一组符号的哈夫曼编码，我们可以定义一个哈夫曼树类。
  • 哈夫曼树类的对象可以接受一组符号以及对应的权值，并返回每个符号对应的哈夫曼编码。因此，哈夫曼树类应该有两个公有的成员函数：
    • 构造函数：接受一组待编码的符号以及它们的权值，构造一棵哈夫曼树。
    • GetCode函数根据保存的哈夫曼树为每个叶结点生成哈夫曼编码。

哈夫曼树的存储

  • 在哈夫曼树中，每个要编码的元素是一个叶结点，其它结点都是度数为2的节点

  • 一旦给定了要编码的元素个数，由n0＝n2+1n_0＝n_2+1可知哈夫曼树的大小为2n−12n-1

  • 哈夫曼树可以用一个大小为2n的数组来存储。

    • 0结点不用，根存放在结点1。
    • 叶结点依次放在n+1到2n的位置
    • 0结点作为结束的判断依据

  • 每个数组元素保存的信息：结点的数据、权值和父结点和左右孩子的位置

  • 哈夫曼树的存储方式不是顺序实现，是一种使用静态存储的链接实现！

    • 一般而言，顺序实现采用静态存储，链接实现采用动态存储。但是哈夫曼树作为一种长度在生成前就可以确定的树，适合采用静态存储+链接实现，可以有效节约空间（哈夫曼树中有很多空节点）。

哈夫曼树的构造（哈夫曼算法）

  1. 给定一个具有n个权值{ w1,w2,………wn }的结点的集合：F = { T1,T2,………Tn }
  2. 初始时，设集合 A = F
  3. 执行 i = 1 至 n -1 的循环，在每次循环时执行以下操作：
    1. 从当前集合中选取权值最小、次最小的两个结点
    2. 以这两个结点作为内部结点 bi 的左右儿子，bi 的权值为其左右儿子权值之和。
    3. 在集合中去除这两个权值最小、次最小的结点，并将内部结点bi 加入其中。这样，在集合A中，结点个数便减少了一个。这样，在经过了n-1 次循环之后，集合A中只剩下了一个结点，这个结点就是根结点。
image-20240611115839055

哈夫曼树类

  • 存储设计
    • 结点的表示：结点的数据、权值和父结点和左右孩子的位置
    • 哈夫曼树的存储：
    • 一个结点数组以及一个整型数据成员，保存数组的大小。
  • 操作
    • 构建一棵哈夫曼树：构造函数实现。
    • 给出结点数据数组，权值数组和数据个数
    • 获取树上结点的哈夫曼编码
    • 返回一个数组，数组的元素由数据和编码两部分组成的
构造函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
template <class Type>
hfTree<Type>::hfTree(const Type *v, const int *w, int size) 	
{  const int MAX_INT = 32767;
    int min1, min2;    //最小树、次最小树的权值
    int x, y;     //最小树、次最小树的下标

    //置初值 
    length = 2 * size;
    elem = new Node[length];
    for (int i = size; i < length; ++i)
         { elem[i].weight = w[i - size];
            elem[i].data = v[i - size];
           elem[i].parent = elem[i].left = elem[i].right = 0;
         }     
// 构造新的二叉树
 for (i = size - 1; i > 0; --i)
    { min1 = min2 = MAX_INT; x = y = 0;
       for (int j = i + 1; j < length; ++j)
		  if (elem[j].parent == 0) 
		       if (elem[j].weight < min1) 
                          { min2 = min1; min1 = elem[j].weight; 
                             x = y; y = j; }//min1最小值，y最小值下标
                       else if (elem[j].weight < min2)
                               { min2 = elem[j].weight; x = j; } //min2次小值   
         elem[i].weight = min1 + min2;
         elem[i].left = x; elem[i].right = y; elem[i].parent = 0;
         elem[x].parent = i; elem[y].parent = i;
     }
}
获取哈夫曼编码的函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template <class Type>
void hfTree<Type>::getCode(hfCode result[]) 
{ 
    int size = length / 2;  
    int p,s; // s是追溯过程中正在处理的结点，p是s的父结点下标
    for (int i = size; i < length; ++i)
    {
        result[i - size].data = elem[i].data;
        result[i - size].code = "";
        p = elem[i].parent; s = i;
	while (p) {
		if (elem[p].left == s) 
                    result[i - size].code = '0' + result[i - size].code;
		    else result[i - size].code = '1' + result[i - size].code;
		s = p; p = elem[p].parent;
	}
    }  
}

树和森林

树的存储实现

标准形式

树中的每个结点除有数据字段之外，还有K个指针字段；其中K为树的度。

广义标准形式：在标准形式的基础上，再增加指向父亲结点的指针。

image-20240403140745745

孩子链表示法

  • 将每个结点的所有孩子组织成一个链表。

  • 树的结点由两部分组成：

    • 存储数据元素值的数据部分

    • 指向孩子链的指针

    image-20240403141209111

孩子兄弟链表示法（最常用）

实质上是用二叉树表示一棵树。树中的每个结点有数据字段、指向它的第一棵子树树根的指针字段、指向它的兄弟结点的指针字段。

image-20240403141839855 image-20240403142015717

双亲（父节点）表示法

  • 通过指向父结点的指针将树中所有的结点组织在一起

  • 在双亲表示法中，每个结点由两部分组成：

    • 存储数据元素的数据字段

    • 存储父结点位置的父指针字段

  • 这种表示法对求指定结点的祖先的操作很方便，但对求指定结点的子孙则不方便。

树的遍历

树的前序遍历

树的后序遍历

树的层次遍历

从遍历结果确定一个树

前序+后序 可以
  • 由于树的前序+后序等效于对孩子兄弟链表示法的二叉树进行前序+中序遍历，所以可以先用二叉树前序+中序遍历确定孩子兄弟链表示法的二叉树形态
  • 再转换成原来的树
前序+层次 可以
后序+层次 可以

树与二叉树的转化和关系

树可以转化为二叉树：树的孩子兄弟链表示法就是将一棵树表示成二叉树的形态，这样就可以将二叉树中的许多方法用在树的处理中。

树通过孩子兄弟链表示法转化后得到的二叉树的中序遍历与转换前的后序遍历相同

森林

  • 森林通常定义为树的集合或树的序列。
  • 森林的存储：存储一个森林要包括两方面的内容
    • 存储森林中的每一棵树
    • 表示这些树是属于同一个森林。

森林的二叉树存储

  • 森林
  • 将每棵树TiT_i转换成对应的二叉树BiB_i；
  • 将BiB_i作为Bi−1B_{i-1}​根结点的的右子树。
image-20240611121933783 image-20240611121956942
0%