vlambda博客
学习文章列表

「好好学习，天天向上」

本文已收录至我的Github仓库「DayDayUP」：github.com/RobodLee/DayDayUP，欢迎Star

5.1 树的基本概念

5.1.1 树的定义

树是n个节点的有限集。n=0时，称为「空树」。任何一个非空树应该满足：

• 有且仅有一个「根结点」

• 当n > 1时，其余结点可分为m（m > 0）个「互不相交的有限集合」T1, T2, … , Tm，其中每个集合本身又是一棵树，并且称为根结点的「子树」

5.1.2 树的概念

• 「双亲结点」（父节点）：结点上面一层用线连起来的节点。比如结点G的父节点是C。

• 「孩子结点」：结点下面一层用线连起来的结点，比如结点D的孩子结点为H、I、J。

• 「叶子节点」：结点的度为0的结点，也就是没有孩子结点的结点，图中叶子节点为K、L、F、G、M、I、J。

• 「结点的层次」：从上往下数在第几行，比如「根节点」在第1层，结点「E」在第3层。

• 「结点的高度」：从下往上数。

• 「结点的深度」：从上往下数。

• 「树的高度」（深度）：总共多少层，图中的数高度为4。

• 「结点的度」：有几个孩子节点，比如图中结点H的度为0。

• 「树的度」：树中结点的最大度数，图中结点D的度最大，为3，所以树的度也为3。

• 「路径」：一个结点到另一个结点的路线，「只能是从上往下」，比如A→K的路径为A→B→E→K。

• 「路径长度」：路径上所经过的边的个数，比如A→K路径长度为3。

• 「有序树和无序树」：树中结点的各子树从左到右是有次序的，不能互换，称为有序树。反之称为无序树。

5.1.3 树的性质

1. 结点数 = 总度数+1

   结点的度为结点有几个孩子结点，由于没有哪一个结点的子节点是根结点，所以总度数不包含根结点。所以结点数为总度数+1。

   

   上图中A的度为3，B的度为2，C的度为1.....总度数为3+2+1+3+2+1=12。

   结点数为13=12+1。

2. 度为m的树、m叉树 的区别

   度为m的树	m叉树
   各结点的度的最大值	每个结点最多只能有m个孩子的树
   任意结点的度 ≤ m（最多m个孩子）	任意结点的度 ≤ m（最多m个孩子）
   至少有一个结点度 = m（有m个孩子）	允许所有结点的度都 ＜ m
   一定是非空树，至少有m+1个结点	可以是空树

   

3. 度为 m 的树第 i 层至多有 m^(i-1) 个结点（i≥1）,m叉树第 i 层至多有 m^(i-1) 个结点（i≥1）

   

4. 高度为h的m叉树至多有 (m^h -1)/(m-1) 个结点

   

5. 高度为h的m叉树至少有 h 个结点；高度为h、度为m的树至少有 h+m-1 个结点

   

6. 具有n个结点的m叉树的最小高度为logm(n(m - 1) + 1)

   

5.2二叉树的概念

5.2.1 基本概念

二叉树是n（n≥0）个结点的有限集合：

• 或者为「空二叉树」，即n = 0。

• 或者由一个「根结点」和两个互不相交的被称为根的「左子树」和「右子树」组成。「左子树和右子树又分别是一棵二叉树」。

• 每个结点「至多」只有两棵子树。

• 左右子树不能颠倒（二叉树是「有序树」）

5.2.2 几个特殊的二叉树

• 满二叉树：一棵高度为h，且含有2^h - 1个结点的二叉树

  

• 只有最后一层有叶子结点

• 不存在度为 1 的结点

• 按层序从 1 开始编号，结点 i 的左孩子为 2i，右孩子为 2i+1；结点 i 的父节点为i/2（如果有的话）

• 完全二叉树：当且仅当其每个结点都与高度为h的满二叉树中编号为1～n的结点一一对应时，称为完全二叉树

  

• 只有最后两层可能有叶子结点

• 最多只有一个度为1的结点

• 按层序从 1 开始编号，结点 i 的左孩子为 2i，右孩子为 2i+1；结点 i 的父节点为i/2（如果有的话）

• i≤ (n/2) 为分支结点， i> (n/2) 为叶子结点

• 如果某结点只有一个孩子，那么一定是左孩子

• 二叉排序树(可用于元素的排序和搜索)：一棵二叉树或者是空二叉树，或者是具有如下性质的二叉树

  

• 「左子树」上所有结点的「关键字」均「小于根结点」的关键字

• 「右子树」上所有结点的「关键字」均「大于根结点」的关键字

• 左子树和右子树又各是一棵二叉排序树

• 平衡二叉树(搜索效率高)：树上任一结点的左子树和右子树的深度之差不超过1。

  

5.2.3 性质

二叉树的性质

1. 设非空二叉树中度为0、1和2的结点个数分别为n0、n1和n2，则 n0 = n2 + 1（即叶子结点比二分支结点多一个）

   

2. 二叉树第 i 层至多有 2^(i-1) 个结点（i≥1），m叉树第 i 层至多有 m^(i-1) 个结点（i≥1）

   

3. 高度为h的二叉树至多有 2^ℎ − 1个结点（满二叉树）,高度为h的m叉树至多有 (m^h -1)/(m-1) 个结点

   

完全二叉树的性质

1. 具有n个（n > 0）结点的完全二叉树的高度h为 ⌈log₂(n + 1)⌉ 或 ⌊log₂n⌋+1

   

2. 对于完全二叉树，可以由结点数 n 推出度为0、1和2的结点个数为n0、n1和n2

   

5.2.4 二叉树的存储结构

顺序存储

struct TreeNode {
    ElemType value; //结点中的数据元素
    bool isEmpty;   //结点是否为空
};

链式存储

typedef struct BiTNode {
    ElemType data;                      //数据域
    struct BiTNode *lChild, *rChild;    //左右孩子指针
} BiTNode, *BiTree;

5.3二叉树的遍历

二叉树的遍历是指按某条搜索路径访问树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。

5.3.1 二叉树的先中后序遍历

根据对根结点、左子树、右子树的访问顺序不同，分为「先序遍历」、「中序遍历」和「后序遍历」。

• 先序遍历

1. 「访问根结点」

2. 先序遍历左子树

3. 先序遍历右子树

• 中序遍历

1. 中序遍历左子树

2. 「访问根结点」

3. 中序遍历右子树

• 后序遍历

1. 后续遍历左子树

2. 后序遍历右子树

3. 「访问根结点」

#define MaxSize 100
#define ElemType char

#include <iostream>

using namespace std;

//顺序存储
struct TreeNode {
    ElemType value; //结点中的数据元素
    bool isEmpty;   //结点是否为空
};

//链式存储
typedef struct BiTNode {
    ElemType data;                      //数据域
    struct BiTNode *lChild, *rChild;    //左右孩子指针
} BiTNode, *BiTree;

//前序遍历
void PreOrder(BiTree tree) {
    if (tree != nullptr) {
        cout << tree->data << " ";
        PreOrder(tree->lChild);
        PreOrder(tree->rChild);
    }
}

//中序遍历
void InOrder(BiTree tree) {
    if (tree != nullptr) {
        InOrder(tree->lChild);
        cout << tree->data << " ";
        InOrder(tree->rChild);
    }
}

//后序遍历
void PostOrder(BiTree tree) {
    if (tree != nullptr) {
        PostOrder(tree->lChild);
        PostOrder(tree->rChild);
        cout << tree->data << " ";
    }
}

//求树的深度
int treeDepth(BiTree tree) {
    if (tree == nullptr) {
        return 0;
    } else {
        int l = treeDepth(tree->lChild);
        int r = treeDepth(tree->rChild);
        return l > r ? l + 1 : r + 1;
    }
}

5.3.2 二叉树的层次遍历

层次遍历按照「自上至下」，「从左向右」的顺序依次将对结点进行访问。

• 算法思想

1. 初始化一个辅助队列

2. 根结点入队

3. 若队列非空，则队头结点出队，访问该结点，并将其左、右孩子插入队尾（如果有的话）

4. 重复第3步直至队列为空

#define ElemType char
#define MaxSize 10
#include <iostream>
using namespace std;

typedef struct BiTNode {
    ElemType data;                      //数据域
    struct BiTNode *lChild, *rChild;    //左右孩子指针
} BiTNode, *BiTree;

typedef struct {
    BiTNode data[MaxSize];
    int front, rear;
} SqQueue;

//初始化队列
void InitQueue(SqQueue &queue) {
    queue.front = 0;
    queue.rear = 0;
}

//判断队列是否为空
bool QueueEmpty(SqQueue queue) {
    return queue.front == queue.rear;
}

//入队
bool EnQueue(SqQueue &queue, BiTNode x) {
    if ((queue.rear + 1) % MaxSize == queue.front) {
        return false;   //队满
    }
    queue.data[queue.rear] = x;
    queue.rear = (queue.rear + 1) % MaxSize;    //队尾指针后移一位
    return true;
}

//出队
bool DeQueue(SqQueue &queue, BiTNode &x) {
    if (QueueEmpty(queue)) {
        return false;   //队空
    }
    x = queue.data[queue.front];
    queue.front = (queue.front + 1) % MaxSize;  //队头指针后移一位
    return true;
}

//获取队头元素
bool GetHead(SqQueue &queue, BiTNode &x) {
    if (QueueEmpty(queue)) {
        return false;   //队空
    }
    x = queue.data[queue.front];
    return true;
}

//二叉树的层序遍历
void LevelOrder(BiTree tree) {
    SqQueue queue;          //辅助队列
    InitQueue(queue);
    EnQueue(queue, *tree);  //根结点入队
    while (!QueueEmpty(queue)) {    //队头不空则队头结点出队
        BiTNode node;
        DeQueue(queue, node);
        cout << node.data << " ";
        if (node.lChild != nullptr) {   //如果左子树不空，则左子树的根结点入队
            EnQueue(queue, *node.lChild);
        }
        if (node.rChild != nullptr) {   //如果右子树不空，则右子树的根结点入队
            EnQueue(queue, *node.rChild);
        }
    }
}

5.3.3 由遍历序列构造二叉树

通过指定前序+中序、后序+中序、层序+中序三种遍历序列中任意一种，均可以构造出一个二叉树。

以前序+中序序列进行说明：前序序列中，第一个结点肯定是根结点，找到根结点后就可以在中序序列中找到根结点的位置，中序序列中根结点左边的是左子树的中序序列，右边的是右子树的中序序列。假设左子树的中序序列长度为n，那么前序序列中根结点后面的n个元素就是左子树的前序序列，剩下的几个就是右子树的前序序列。采用相同的方式进行递归，就可以构建出左子树与右子树，然后将左右子树与根结点相连。

「后序+中序」、「层序+中序」也是类似的分析方法，这里便不再赘述。

public class BuildTree {

    static class TreeNode {
        final char data;
        TreeNode lChild;
        TreeNode rChild;

        TreeNode(char data) {
            this.data = data;
        }
    }

    //根据 前序+中序序列 构建二叉树
    private TreeNode preAndInfixOrder(String preOrder, String infixOrder) {
        int size = preOrder.length();
        TreeNode root = new TreeNode(preOrder.charAt(0));   //前序序列的第一个节点作为根结点
        int rootIndexInInfixOrder = infixOrder.indexOf(root.data);  //根结点在中序序列中的位置
        int lChildSize = 0;   //左子树元素个数
        if (rootIndexInInfixOrder == 0) {   //中序序列中根结点在第一个位置，说明没有左子树
            root.lChild = null;
        } else {
            String lChildInfixOrder = infixOrder.substring(0, rootIndexInInfixOrder);    //左子树中序序列
            lChildSize = lChildInfixOrder.length();
            String lChildPreOrder = preOrder.substring(1, lChildSize + 1);  //左子树前序序列
            root.lChild = preAndInfixOrder(lChildPreOrder, lChildInfixOrder);
        }
        if (rootIndexInInfixOrder == size - 1) {    //中序序列中根结点在最后一个位置，说明没有右子树
            root.rChild = null;
        } else {
            String rChildInfixOrder = infixOrder.substring(rootIndexInInfixOrder + 1, size);    //右子树中序序列
            String rChildPreOrder = preOrder.substring(lChildSize + 1, size);                   //右子树前序序列
            root.rChild = preAndInfixOrder(rChildPreOrder, rChildInfixOrder);
        }
        return root;
    }

    //根据 后序+中序序列 构建二叉树
    private TreeNode postAndInfixOrder(String postOrder, String infixOrder) {
        int size = postOrder.length();
        TreeNode root = new TreeNode(postOrder.charAt(size - 1));   //后序序列的最后一个结点作为根结点
        int rootIndexInInfixOrder = infixOrder.indexOf(root.data);
        int lChildSize = 0;   //左子树元素个数
        if (rootIndexInInfixOrder == 0) {   //中序序列中根结点在第一个位置，说明没有左子树
            root.lChild = null;
        } else {
            String lChildInfixOrder = infixOrder.substring(0, rootIndexInInfixOrder);    //左子树中序序列
            lChildSize = lChildInfixOrder.length();
            String lChildPostOrder = postOrder.substring(0, lChildSize);                 //左子树后序序列
            root.lChild = postAndInfixOrder(lChildPostOrder, lChildInfixOrder);
        }
        if (rootIndexInInfixOrder == size - 1) {    //中序序列中根结点在最后一个位置，说明没有右子树
            root.rChild = null;
        } else {
            String rChildInfixOrder = infixOrder.substring(rootIndexInInfixOrder + 1, size);        //右子树中序序列
            String rChildPostOrder = postOrder.substring(lChildSize, size - 1);                     //右子树后序序列
            root.rChild = postAndInfixOrder(rChildPostOrder, rChildInfixOrder);
        }
        return root;
    }

    //根据 层序+中序序列 构建二叉树
    private TreeNode levelAndInfixOrder(String levelOrder, String infixOrder) {
        int size = levelOrder.length();
        TreeNode root = new TreeNode(levelOrder.charAt(0));   //层序序列的第一个结点作为根结点
        int rootIndexInInfixOrder = infixOrder.indexOf(root.data);
        if (rootIndexInInfixOrder == 0) {    //中序序列中根结点在第一个位置，说明没有左子树
            root.lChild = null;
        } else {
            String lChildInfixOrder = infixOrder.substring(0, rootIndexInInfixOrder);    //左子树中序序列
            String lChildLevelOrder = "";   //左子树层序序列
            //遍历层序序列，如果能够在 左子树中序序列 中找到对应的元素，说明该元素属于左子树
            for (int i = 0; i < levelOrder.length(); i++) {
                char c = levelOrder.charAt(i);
                if (lChildInfixOrder.indexOf(c) != -1) {
                    lChildLevelOrder += c;
                }
            }
            root.lChild = levelAndInfixOrder(lChildLevelOrder, lChildInfixOrder);
        }
        if (rootIndexInInfixOrder == size - 1) {    //中序序列中根结点在最后一个位置，说明没有右子树
            root.rChild = null;
        } else {
            String rChildInfixOrder = infixOrder.substring(rootIndexInInfixOrder + 1, size);        //右子树中序序列
            String rChildLevelOrder = "";   //右子树层序序列
            for (int i = 0; i < levelOrder.length(); i++) {
                char c = levelOrder.charAt(i);
                if (rChildInfixOrder.indexOf(c) != -1) {
                    rChildLevelOrder += c;
                }
            }
            root.rChild = levelAndInfixOrder(rChildLevelOrder, rChildInfixOrder);
        }
        return root;
    }
}

5.4 线索二叉树

5.4.1 线索二叉树的基本概念

传统的二叉链表存储仅能「体现父子关系」，不能直接得到结点在遍历中的前驱或后继。在含「n个节点的二叉树」中，有n+1个空指针。所以可以用这些空指针指向其前驱结点和后继节点，若无左子树，令lchild指向其前驱结点，若无右子树，令rchild指向其后继结点。

typedef struct ThreadNode {
    ElemType data;                      //数据域
    struct ThreadNode *lChild, *rChild;    //左右指针
    int lTag, rTag;        //左右线索标志，0表示指针指向孩子节点；1表示指向结点的前驱/后继
} ThreadNode, *ThreadTree;

5.4.2 二叉树的线索化

二叉树的线索化就是将结点中的空指针域指向其前驱结点或后继结点。在遍历的过程中一边遍历一边进行线索化，其中全局变量 pre 指针指向当前访问结点的前驱结点。

#define ElemType char
#include <iostream>
using namespace std;

//结点
typedef struct ThreadNode {
    ElemType data;                      //数据域
    struct ThreadNode *lChild, *rChild;    //左右指针
    int lTag, rTag;        //左右线索标志，0表示指针指向孩子节点；1表示指向结点的前驱/后继
} ThreadNode, *ThreadTree;

ThreadNode *pre = nullptr;

void Visit(ThreadNode *node) {
    if (node->lChild == nullptr) {  //左子树为空，建立前驱线索
        node->lChild = pre;
        node->lTag = 1;
    }
    if (pre != nullptr && pre->rChild == nullptr) {     //前驱结点的右子树为空，为前驱结点建立后驱线索
        pre->rChild = node;
        pre->rTag = 1;
    }
    pre = node;
}

//先序遍历二叉树，一边遍历一边线索化
void PreThread(ThreadTree node) {
    if (node != nullptr) {
        Visit(node);
        //判断是否是孩子结点，如果是线索结点，则不去进行访问，防止死循环
        if (node->lTag == 0) {
            PreThread(node->lChild);
        }
        if (node->rTag == 0) {
            PreThread(node->rChild);
        }
    }
}

//中序遍历二叉树，一边遍历一边线索化
void InThread(ThreadTree node) {
    if (node != nullptr) {
        InThread(node->lChild);
        Visit(node);
        InThread(node->rChild);
    }
}

//中序遍历二叉树，一边遍历一边线索化
void PostThread(ThreadTree node) {
    if (node != nullptr) {
        PostThread(node->lChild);
        PostThread(node->rChild);
        Visit(node);
    }
}

//先序线索化二叉树
void CreatePreThread(ThreadTree tree) {
    pre = nullptr;
    if (tree != nullptr) {
        PreThread(tree);
        if (pre->rChild == nullptr) {
            pre->rTag = 1;  //将最后一个结点的右子树线索标志置为1
        }
    }
}

//中序线索化二叉树
void CreateInfixThread(ThreadTree tree) {
    if (tree != nullptr) {
        InThread(tree);
        if (pre->rChild == nullptr) {
            pre->rTag = 1;  //将最后一个结点的右子树线索标志置为1
        }
    }
}

//后序线索化二叉树
void CreatePostThread(ThreadTree tree) {
    if (tree != nullptr) {
        PostThread(tree);
        if (pre->rChild == nullptr) {
            pre->rTag = 1;  //将最后一个结点的右子树线索标志置为1
        }
    }
}

以「先序遍历线索化进行」说明：

假设现在node为结点E，pre指向结点G。进入Visit函数，由于node.lChild为null，使其指向前驱结点D，再进行判断，由于pre不为null，且pre的rChild为null，使其指向后继结点E。中序遍历线索化和后序遍历线索化都是同样的道理，都是在遍历的同时修改结点空指针域的指向。

在先序遍历时，需要lTag和rTag的值进行判断，判断指针指向的是前驱/后继结点还是子结点。如果不进行判断则会出现死循环的情况 。

例如上面这个二叉树，当Visit结点B时，会将A的rChild指向B，B的lChild指向A。根据先序遍历的顺序，访问完B后就应该去访问A的右孩子结点了，A并没有右孩子结点，但是A的rChild已经指向了B。所以需要进行判断A的rChild是孩子结点还是线索结点，如果不进行判断就会在AB之间死循环。「在访问lChild和rChild时都有可能出现死循环，所以都需要进行判断」。

5.4.3 线索二叉树的遍历

• 中序线索二叉树找 前驱/后继 结点

  

  「如果 rTag==1 ，则直接访问 p→rChild」。否则：

  中序遍历的顺序是 左-根-右，访问完根结点后就该访问根结点的右子树，右子树的中序遍历顺序也是左-根-右，也就是访问右子树的左孩子，以此类推：

  以p为根结点，它的后继节点就是右子树中最左下的一个结点。例如图中A的后继为F。

  

  ---

  「如果lTag==1，则直接访问p→lChild」。否则

  中序遍历中先访问根结点的左子树才去访问根结点，左子树中最后一个被访问的是右孩子，以此类推：

  以p为根结点，它的前驱结点就是p左子树的最右下一个结点。例如图中A的前驱结点是E。

  

• 先序线索二叉树找后继结点

  

  「如果rTag==1，则直接访问p→rChild」。否则：

  由于先序遍历的顺序为根左右，所以以p为根结点，如果它连接有左子树，则后继结点为左子树的根结点（即左孩子）；如果没有左子树，则后继节点为右子树的根结点（即右孩子）。

  

• 后序线索二叉树找前驱结点

  

  「如果lTag==1，则p的前驱结点为p→lChild」。否则：

  由于后序遍历的顺序为左右根。所以以p为根结点，它的前驱结点就是右子树的根结点（即右孩子）；如果未连接有右子树，则前驱结点为左子树的根结点（即左孩子）。

  

#define ElemType char
#include <iostream>
using namespace std;

typedef struct ThreadNode {
    ElemType data;                      //数据域
    struct ThreadNode *lChild, *rChild;    //左右指针
    int lTag, rTag;        //左右线索标志，0表示指针指向孩子节点；1表示指向结点的前驱/后继
} ThreadNode, *ThreadTree;

//找到以P为根的子树中，第一个被中序遍历的结点，即最左下结点
ThreadNode *FirstNodeInfix(ThreadNode *p) {
    while (p->lTag == 0) {
        p = p->lChild;
    }
    return p;
}

//在中序线索二叉树中找到结点p的后继结点
// 右子树最左下一个结点，相当于在右子树中找到第一个被中序遍历的结点
ThreadNode *NextNodeInfix(ThreadNode *p) {
    if (p->rTag == 0) {
        return FirstNodeInfix(p->rChild);
    } else {
        return p->rChild;
    }
}

//对中序线索二叉树进行中序遍历
void InfixOrder(ThreadTree t) {
    for (ThreadNode *p = FirstNodeInfix(t); p != nullptr; p = NextNodeInfix(p)) {
        cout << p->data << " ";
    }
    cout << endl;
}

//找到以p为根结点的子树中，最后一个被中序遍历的结点，即最右下结点
ThreadNode *LastNodeInfix(ThreadNode *p) {
    while (p->rTag == 0) {
        p = p->rChild;
    }
    return p;
}

// 在中序线索二叉树中找到结点p的前驱结点
// 左子树最右下结点，相当于在左子树中找到最后一个被中序遍历的节点
ThreadNode *PreNodeInfix(ThreadNode *p) {
    if (p->lTag == 0) {
        return LastNodeInfix(p->lChild);
    } else {
        return p->lChild;
    }
}

// 对中序线索二叉树进行逆向中序遍历
void ReverseInfixOrder(ThreadTree t) {
    for (ThreadNode *p = LastNodeInfix(t); p != nullptr; p = PreNodeInfix(p)) {
        cout << p->data << " ";
    }
    cout << endl;
}

//先序线索二叉树中寻找后继结点
ThreadNode *NextNodePre(ThreadNode *p) {
    if (p->rTag == 1) {
        return p->rChild;
    }
    //有左孩子后继结点就是左孩子，否则就是右孩子
    //这里需要判断lTag是否为0，如果不为0则说明左指针指向的是前驱结点而不是左孩子
    if (p->lChild != nullptr && p->lTag == 0) {
        return p->lChild;
    } else {
        return p->rChild;
    }
}

// 对先序线索二叉树进行先序遍历
void PreOrder(ThreadTree t) {
    for (ThreadNode *p = t; p != nullptr; p = NextNodePre(p)) {
        cout << p->data << " ";
    }
    cout << endl;
}

//后序线索二叉树中寻找前驱结点
ThreadNode *PreNodePost(ThreadNode *p) {
    if (p->lTag == 1) {
        return p->lChild;
    }
    //有右孩子前驱结点就是右孩子，没有右孩子就是左孩子
    if (p->rChild != nullptr && p->rTag == 0) {
        return p->rChild;
    } else {
        return p->lChild;
    }
}

//对后序线索二叉树进行后序逆向遍历
void ReversePostOrder(ThreadTree t) {
    for (ThreadNode *p = t; p != nullptr; p = PreNodePost(p)) {
        cout << p->data << " ";
    }
    cout << endl;
}

5.5树、森林

5.5.1 树的存储结构

• 双亲表示法（顺序存储）

  采用一组连续空间（数组）来存储每个结点，同时在每个结点中增设一个伪指针，「用来指示其双亲结点在数组中的位置」。

  

  typedef struct {        //树的结点的定义
      ElemType data;      //数据元素
      int parent;         //双亲位置域，即父结点在数组中的下标
  } PTNode;
  
  typedef struct {        //树的类型定义
      PTNode nodes[MAX_TREE_SIZE];    //双亲表示
      int n;                          //结点数
  } PTree;
  

• 孩子表示法（顺序+链式存储）

  将「每个结点的孩子都用单链表链接起来形成一个线性结构」。这种方式寻找子女的操作非常直接，而寻找双亲的操作需要遍历n个结点中孩子链表指针域所指向的n个孩子链表。

  

  struct CTNode {
      int child;  //孩子结点在数组中的位置
      CTNode *next;    //下一个孩子
  };
  typedef struct {
      ElemType data;
      CTNode *firstChild;     //第一个孩子
  } CTBox;
  typedef struct {
      CTBox nodes[MAX_TREE_SIZE];
      int n, r;    //结点数和根的位置
  } CTree;
  

• 孩子兄弟表示法（链式存储）

  该方法以二叉链表作为树的存储结构，又称「二叉树表示法」。每个结点包括结点值、指向结点第一个孩子结点的指针、指向结点下一个兄弟结点的指针(沿此指针域可以找到结点的所有兄弟结点)三个部分。

  优点是「可以方便地实现树与二叉树的转换，易于处查找结点的孩子」；缺点是「不能从当前结点查找其双亲结点，只能从头遍历」。

  

  //孩子兄弟表示法
  typedef struct CSNode {
      ElemType data;      //数据域
      CSNode *firstChild, *nextSibling;   //第一个孩子和右兄弟指针（看做左指针和右指针）
  } CSNode, *CSTree;
  

5.5.2 树、森林与二叉树的转换

用孩子兄弟表示法存储森林，森林中各个树的根结点之间视为兄弟关系。

5.5.3 树和森林的遍历

树的遍历

• 先根遍历

  若树非空，先访问根结点，再依次遍历根结点的每棵子树，遍历子树时仍遵循先根后子树的规则。遍历序列与相应二叉树的先序序列相同。

  void PreOrder(TreeNode *R) {
      if (R != NULL) {
          visit(R);               //访问根结点
          while (R还有下一棵子树T) {
              PreOrder(T);        //先根遍历下一棵子树
          }
      }
  }
  
  

  

• 后根遍历

  若树非空，先依次对每棵子树进行后根遍历，最后再访问根结点，遍历子树时仍遵循先子树后根的规则。遍历序列与相应的二叉树的中序序列相同。也有教材称之为中根遍历。

  void PostOrder(TreeNode *R) {
      if (R != NULL) {
          while (R还有下一棵子树T) {
              PostOrder(T);        //后根遍历下一棵子树
          }
          visit(R);               //访问根结点
      }
  }
  

  

• 层次遍历（用队列实现）

  

1. 若树非空，则根节点入队

2. 若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队

3. 重复2直到队列为空

森林的遍历

• 先序遍历

  按如下规则进行遍历：

  效果等同于依次对各个树进行先根遍历，也等同于对相应二叉树进行先序遍历。

  

1. 访问森林中第一棵树的根结点

2. 先序遍历第一棵树中根结点的子树森林

3. 先序遍历除去第一棵树之后剩余的树构成的森林

• 中序遍历

  按如下规则进行遍历：

  效果等同于依次对各个树进后根遍历，也等同于对相应二叉树进行中序遍历。

  

1. 中序遍历森林中第一棵树的根结点的子树森林

2. 访问第一棵树的根结点

3. 中序遍历除去第一棵树之后剩余的树构成的森林

5.6 树与二叉树的应用

5.6.1 哈夫曼树和哈夫曼编码

概念

• 结点的权：有某种现实含义的数值（如：表示结点的重要性等）。👆图中结点上的数字就是结点的权。

• 结点的带权路径长度：从树的根到该结点的「路径长度」（经过的边数）「与该结点上权值的乘积」。例如图中结点3的路径长度为3，所以该结点的带权路径长度为3*3=9。

• 树的带权路径长度：树中所有「叶结点的带权路径长度之和」（WPL, Weighted Path Length）。上图中WPL=5*3 + 1*3 + 10*3 + 3*3 + 4*1 = 61。

在含有n个带权叶结点的二叉树中，其中「带权路径长度（WPL）最小的二叉树」称为哈夫曼树，也称最优二叉树。

构造哈夫曼树

给定n个权值分别为w1, w2,…, wn的结点，构造哈夫曼树的算法描述如下：

1. 将这「n个结点分别作为n棵仅含一个结点的二叉树」，构成森林「F」。

2. 构造一个新结点，从F中「选取两棵根结点权值最小的树作为新结点的左、右子树」，并且将「新结点的权值置为左、右子树上根结点的权值之和」。

3. 从F中「删除刚才选出的两棵树，同时将新得到的树加入F」中。

4. 「重复步骤2和3」，直至F中只剩下一棵树为止。

public class HuffmanTree {
    
    private int weight;     //权值
    private String info;    //结点信息
    private HuffmanTree lChild;
    private HuffmanTree rChild;

    HuffmanTree(int weight, String info) {
        this.weight = weight;
        this.info = info;
    }

    private HuffmanTree buildHuffmanTree(List<HuffmanTree> nodes) {
        HuffmanTree min1;
        HuffmanTree min2;   //权值最小的两个结点
        while (nodes.size() > 1) {
            int min1Index = 0;
            for (int i = 1; i < nodes.size(); i++) {    //找权值最小的第一个结点的下标
                if (nodes.get(i).weight < nodes.get(min1Index).weight) {
                    min1Index = i;
                }
            }
            min1 = nodes.get(min1Index);
            nodes.remove(min1Index);    //将选中的结点从集合中删除

            int min2Index = 0;
            for (int i = 1; i < nodes.size(); i++) {    //找权值最小的第二个结点的下标
                if (nodes.get(i).weight < nodes.get(min2Index).weight) {
                    min2Index = i;
                }
            }
            min2 = nodes.get(min2Index);
            nodes.remove(min2Index);    //将选中的结点从集合中删除

            HuffmanTree newNode = new HuffmanTree
                    (min1.weight + min2.weight, "");    //构造一个结点，权值为两个选中结点权值之和
            newNode.lChild = min1;
            newNode.rChild = min2;  //将两个结点作为新结点的左右子树
            nodes.add(newNode);     //添加到集合中
        }
        return nodes.get(0);
    }
}

哈夫曼树的「特点」如下：

• 每个「初始结点最终都成为叶结点」，且「权值越小的结点到根结点的路径长度越大」。

• 哈夫曼树的「结点总数为2n − 1」。

• 哈夫曼树中「不存在度为1的结点」。

• 哈夫曼树并「不唯一」，但「WPL必然相同且为最优」。

哈夫曼编码

「固定长度编码」指的是每个字符用相等长度的二进制位表示，「可变长度编码」指的是允许对不同字符用不等长的二进制位表示，若没有一个编码是另一个编码的前缀，则称这样的编码为「前缀编码」。

哈夫曼编码是可变长度编码和前缀编码，由哈夫曼树得到哈夫曼编码：字符集中的每个字符作为一个叶子结点，各个字符出现的频度作为结点的权值，根据构造哈夫曼树的方法构造哈夫曼树，从而得到哈夫曼编码。

5.6.2 并查集

概念及基本操作

并查集（Disjointed Set）是一种简单的「集合」表示。它是逻辑结构，是集合的一种具体实现，只进行“并”和“查”两种基本操作。用「互不相交的树，表示多个集合」，每棵树表示一个集合，采用双亲表示法作为并查集的存储结构。

• Initial(S)：将集合S中的每个元素都初始化为只有一个单元素的子集合。

  

  将数组元素的值都置为-1，表示每个元素都是一棵树的根结点，即每个元素都是一个单独的集合。

  //初始化并查集
  void Initial(int S[]) {
      for (int i = 0; i < SIZE; ++i) {
          S[i] = -1;
      }
  }
  

• Union(S, Root1, Root2)：把集合S中的子集合Root2并入子集合Root1。要求Root1和Root2互不相交，否则不执行合并。

  

  例如要把紫色的集合合并到绿色的集合中，只需要将结点C的父结点设为A，也就是S[2]=0。

  void Union(int S[], int Root1, int Root2) {
      if (Root1 == Root2) {
          return;     //如果是同一个集合，不执行任何操作
      } else {
          S[Root2] = Root1;   //将根Root2连接到另一根Root1下面
      }
  }
  

• Find(S, x)：查找集合S中单元素x所在的子集合，并返回该子集合的根结点。

  

  比如找结点L的所属集合，就是查找L所在的树的根结点。L的父结点是E，E的父结点是B，B的父结点是A，A就是要找的根结点。

  //查操作，找x所属集合（返回x所属根结点）
  int Find(int S[], int x) {
      while (S[x] >= 0) {     //循环寻找x的根
          x = S[x];
      }
      return x;               //根的S[]小于0
  }
  

Union操作的优化

在进行合并的过程中，可能出现树越来越高的情况，树越高，查找操作的时间复杂度就越高。为了降低查找的时间复杂度，可以在「合并的时候尽量不增加树的高度」。方法就是用根结点的绝对值表示树的结点总数，合并时让小树合并到大树。该方法构造的树高不超过⌊log₂n⌋+1，Find操作最坏时间复杂度降低为O(log₂n)。

//优化后的并操作，小树并大树
void Union_Optimize(int S[], int Root1, int Root2) {
    if (Root1 == Root2) {
        return;     //如果是同一个集合，不执行任何操作
//    } else if ( (-S[Root2]) < (-S[Root1]) ) {   //Root2结点数更少
    } else if (S[Root2] > S[Root1]) {   //Root2结点数更少
        S[Root1] += S[Root2];   //累加结点总数
        S[Root2] = Root1;       //小树Root2合并到大树Root1
    } else {    //Root1结点数更少或结点数一样
        S[Root2] += S[Root1];   //累加结点总数
        S[Root1] = Root2;       //小树Root1合并到大树Root2
    }
}

Find操作的优化（压缩路径）

Find操作的目的是为了找到元素所属集合，那么如果树的高度越小，Find操作的时间复杂度不就越小么。压缩路径的核心思想就是尽可能让树变矮，在每次Find操作时，先找根，再将查找路径上的所有元素都直接挂到根结点下，这样在下次查找时就会更快。

//优化后的查操作，压缩路径
int Find_Optimize(int S[], int x) {
    int root = x;
    while (S[root] >= 0) {     //循环寻找x的根
        root = S[root];
    }
    while (x != root) {     //压缩路径
        int t = S[x];       //t指向x的父结点
        S[x] = root;        //x直接挂到根结点下
        x = t;
    }
    return root;               //返回根结点编号
}

本文已收录至我的Github仓库「DayDayUP」：github.com/RobodLee/DayDayUP^[1]，欢迎Star

如果您觉得文章还不错，请给我来个点赞，在看，转发