Naico智库
面试八股文
软件架构
算法与数据结构
读书笔记

05. 树

基本概念

树的定义（在任意非空树中）

  • 必有一个称为根的结点。
  • 当 n>1（结点树）时，其余结点可分为 m（m>0）个互不相交的有限集 T1，T2······T_m。
  • 其中每一个集合本身又是一颗树，称为根的子树。

特点

  • 非空树中至少有一个根结点。
  • 树中各子树是互不相交的集合。
  • 任意结点都可以有零个或多个直接后继结点，但至多只有一个直接前趋结点。
  • 叶结点无后继，根结点无前趋。

关键词

  • 结点：树中的元素，包括数据项及若干指向其子树的分支。
  • 结点的度：结点拥有的子树数。
  • 树的度：一个树中最大的结点的度。
  • 叶子结点：度为 0 的结点，也叫终端结点。
  • 分支结点：度不为 0 的结点，也叫非终端结点。
  • 内部结点：除根结点外的分支结点。
  • 孩子结点：结点子树的根，称为该结点的孩子。
  • 双亲结点：孩子结点的上层结点，称为该结点的双亲。
  • 兄弟结点：同一双亲的孩子之间互称为兄弟。
  • 堂兄弟结点：其双亲在同一层的结点互称为堂兄弟。
  • 树的层次：从根结点算起，根为第一层，它的孩子为第二层······
  • 树的深度：树中结点的最大层次数。
  • 有序树和无序树：如果将树中结点的各子树看成从左至右有次序的(即不能互换)，则称该树为有序树，否则称无序树。有序树最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。
  • 森林：m(m>=0)颗互不相交的树的集合。
  • 祖先：结点的祖先是从根到该结点所经分支上的所有结点。
  • 子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。

基本操作

初始化、求根、求双亲、求孩子结点、求右兄弟、建树、插入子树操作、删除子树操作、遍历操作、清除操作。

应用场景

决策树、二叉排序树、句法依存树······

二叉树

基础概念

  • 每个结点至多有两棵子树。
  • 不存在度大于 2 的结点。
  • 子树有左右之分，次序不能任意颠倒。
  • 二叉树不是一种特殊的树，只是一种特殊的树形结构。

满二叉树

  • 深度为 k 的满二叉树，有 2^k - 1 个结点。

$$ 2^0 + ……+2^{k-1} = 2^k-1 $$

  • 2^k - 1，是深度为 k 的二叉树所具有的最大结点个数。
  • 每层上的结点数都达到最大值。
  • 只有度为 0 和度为 2 的结点。
  • 每个结点均有两棵高度相同的子树。
  • 叶子结点都在树的最下一层。

判断一个树是否是完全二叉树：

思路：从上到下，右到左扫描，第一个度小于 2 的之后的每一个结点都必须是叶子结点。

foreach node in one_layer begin: if node 有两个孩子，则 continue; if node 无左孩子但有右孩子，则 return False; if (node 有一个左孩子)||(node 是叶子),则: foreachafnode in NODES(node 之后的结点集) if afnode 不是叶子,则 return False; endforeach return Ture;

完全二叉树

  • 对比满二叉树，次序是一样的，最后一层只缺少右边的若干结点。
  • 叶子结点只可能在最大的两层上出现。
  • 对任意结点，若其右子树的深度为 L，则其左子树的深度必为 L 或 L+1。
  • 除最后一层外，每一层的结点数均达到最大值。

性质

  • 二叉树的第 i 层至多有 2^{i-1}个结点（i>=1）。
  • 深度为 k 的二叉树，至多有 2^k - 1 个结点。
  • 对任意二叉树 T，如果其终端结点数为 n0，度为 2 的结点数为 n2，则 n0 = n2 + 1。
  • 具有 n 个结点的完全二叉树的深度为[log_2 n ] + 1。
  • 对于有 n 个结点的完全二叉树的结点按层序编号（从第一层到最后一层，每层从左到右），则对任一结点（1<= i <=n），有：
    • 如果 i=1，则结点 i 是根结点，无双亲，否则，其双亲结点是[i/2]
    • 如果 2i>n，则结点 i 无左孩子（结点 i 为叶子），否则其左孩子是节点 2i。
    • 如果 2i + 1>n，则结点 i 无右孩子，否则右左孩子是节点 2i。

存储

顺序存储

将任意二叉树修补为完全二叉树，用顺序表对元素进行存储，原二叉树空缺的结点，其顺序表相应单元置空：

链式存储

结点有三个域：数据域、指向左、右子树的指针域：

struct btnode{
    char c;
    btnode* lchild;
    btnode* rchild;
    btnode(char c):
        c(c),lchild(NULL),rchild(NULL){

        }
};

基本操作

创建二叉树：

思路：

  • 按先序序列建立二叉链表。
  • abd···ef··g··（要求会画图）
    • 建立根结点
    • 先序建立左子树
    • 先序建立右子树
int x = 0;
// char str[] = {'-', '+', 'a', '#', '#', '*', 'b', '#', '#', '-', 'c', '#', '#', 'd', '#', '#', '/', 'e', '#', '#', 'f', '#', '#',};
btnode* creatTree(char *str){
    cout << x << "," << str[x] << "; ";
    if(x >= 23 || str[x] == '#'){
        x += 1;
        return NULL;
    }
    btnode* cur_node = new btnode(str[x]);//建立当前树的根接节点
    x += 1;
    cur_node->lchild = creatTree(str);
    cur_node->rchild = creatTree(str);
 
    return cur_node;
}
计算叶子数：
  • 若树空，return 0；
  • 若树 t 只有唯一的根，则 return 1
  • 否则
    • 求该二叉树的左子树的叶子数 m。
    • 求该二叉树的右子树的叶子数 n。
    • return m+n;
int countLeaf(btnode *T){
    if(T == NULL){
        return 0;
    }
    if(T->lchild == NULL && T->rchild == NULL){
        return 1;
    }
    int m = countLeaf(T->lchild);
    int n = countLeaf(T->rchild);
    return m+n;
}
计算树的深度：
  • 若树为空，return 0;
  • 否则
    • 计算左子树的高度 m
    • 计算右子树的高度 n
    • return（m>n）？m+1:n+1
int high(btnode *T){
    if(T == NULL){
        return 0;
    }else{
        int m = high(T->lchild) + 1;
        int n = high(T->rchild) + 1;
        if(m > n){
            return m;
        }else{
            return n;
        }
    }
}
带括号的中缀表达式：
//仿照中序遍历，只是区分左右子树
void infixExpression(btnode *T){
    if(T != NULL){
        if(T->lchild != NULL)cout << "(";
        
        infixExpression(T->lchild);
        cout << T->c;
        infixExpression(T->rchild);
        
        if(T->rchild != NULL)cout << ")";
    }
}

遍历

先序遍历（根左右）：
void preorder(btnode *T){
    if(T != NULL){
        cout << T->c << ", ";
        preorder(T->lchild);
        preorder(T->rchild);
    }else{
        cout << "#, ";//输出占位符，保持结构
    }
}
中序遍历（左根右）：
void inorder(btnode *T){
    if(T != NULL){
        inorder(T->lchild);
        cout << T->c << ", ";
        inorder(T->rchild);
    }else{
        cout << "#, ";//输出占位符，保持结构
    }
}
后序遍历（左右根）：
void postorder(btnode *T){
    if(T != NULL){
        postorder(T->lchild);
        postorder(T->rchild);
        cout << T->c << ", ";
    }else{
        cout << "#, ";//输出占位符，保持结构
    }
}
主函数：
int main(){
    cout << "Create Tree" << endl;
    char str[] = {'-', '+', 'a', '#', '#', '*', 'b', '#', '#', '-', 'c', '#', '#', 'd', '#', '#', '/', 'e', '#', '#', 'f', '#', '#',};
    btnode* bt_tree = creatTree(str);
    //遍历
    cout << endl << endl << "preorder,inorder,postorder:" << endl;
    preorder(bt_tree);
    cout << endl;
    inorder(bt_tree);
    cout << endl;
    postorder(bt_tree);
    //计算叶子数
    cout << endl << endl;
    int x = countLeaf(bt_tree);
    cout << "coutLeaf:" << x << endl;
    //计算树深
    cout << endl << "high=" << high(bt_tree) << endl;
    //中缀表达式
    cout << endl << "infixExpression:" << endl;
    infixExpression(bt_tree);
    return 0;
}
输出：
Create Tree
0,-; 1,+; 2,a; 3,#; 4,#; 5,*; 6,b; 7,#; 8,#; 9,-; 10,c; 11,#; 12,#; 13,d; 14,#; 15,#; 16,/; 17,e; 18,#; 19,#; 20,f; 21,#; 22,#; 

preorder,inorder,postorder:
-, +, a, #, #, *, b, #, #, -, c, #, #, d, #, #, /, e, #, #, f, #, #,
#, a, #, +, #, b, #, *, #, c, #, -, #, d, #, -, #, e, #, /, #, f, #,
#, #, a, #, #, b, #, #, c, #, #, d, -, *, +, #, #, e, #, #, f, /, -, 

coutLeaf:6

high=5

infixExpression:
((a+(b*(c-d)))-(e/f))
层序遍历：

思路：利用队列

//层序遍历二叉树
void printBinTree(btnode* root) {
    queue<btnode*> q;
    btnode* b;

    //树为空
    if (root == NULL) {
        cout << "treeNode is empty!" <<endl;
        return;
    }

    //根节点入队
    q.push(root);

    while (!q.empty()) {

        b = q.front();  //拿到队头，队头出队
        q.pop();
        cout << b->c << ", ";  //打印对头的数据

        //对头的左孩子存在就入队
        if (b->lchild) {
            q.push(b->lchild);
        }

        //对头的右孩子存在就入队
        if (b->rchild) {
            q.push(b->rchild);   
        }
    }
}


int main(){
    cout << "Create Tree" << endl;
    char str[] = {'-', '+', 'a', '#', '#', '*', 'b', '#', '#', '-', 'c', '#', '#', 'd', '#', '#', '/', 'e', '#', '#', 'f', '#', '#',};
    btnode* bt_tree = creatTree(str);   
    cout << endl;
    printBinTree(bt_tree);
    return 0;
}

递归算法的非递归描述

//中序遍历为例
void nonRecInorder(btnode *T){
    btnode * p = T;
    vector<btnode*> st;
    if(T != NULL){
        st.push_back(p);
    }else{
        return;
    }
    p = p->lchild;
    while(1){
        while(p != NULL){//右
            st.push_back(p);//同时压栈
            p = p->lchild;
        }
        if(!st.empty()){
            p = st.back();
            st.pop_back();
            cout << p->c << ", ";//中
            p = p->rchild;//左
        }else{
            return;
        }
    }
}

int main(){
    cout << "Create Tree" << endl;
    char str[] = {'-', '+', 'a', '#', '#', '*', 'b', '#', '#', '-', 'c', '#', '#', 'd', '#', '#', '/', 'e', '#', '#', 'f', '#', '#',};
    btnode* bt_tree = creatTree(str);
    cout << endl;
    nonRecInorder(bt_tree);
    return 0;
}
//计算叶子数的非递归描述
int nonRecCountLeaf(btnode *T){  
  if(T == NULL)
    return 0;
  int num = 0;
  vector <btnode*> st;
  while (T != NULL || !st.empty())
  {
    while (T != NULL)
    {
      cout << "node:" << T->c << endl;//print
      st.push_back(T);
      T = T->lchild;
    }
    if (!st.empty())
    {
      T = st.back();//从空那边回来
      st.pop_back();
      if(T->lchild == NULL && T->rchild == NULL)//判断是否为叶子节点
        num++;
      T = T -> rchild;
    }
  }
  return num;
}


int main(){
    cout << "Create Tree" << endl;
    char str[] = {'-', '+', 'a', '#', '#', '*', 'b', '#', '#', '-', 'c', '#', '#', 'd', '#', '#', '/', 'e', '#', '#', 'f', '#', '#',};
    btnode* bt_tree = creatTree(str);   
    cout << endl;
    int x = nonRecCountLeaf(bt_tree);
    cout << endl << "num:" << x;

    return 0;
}

树

树的表示

双亲表示法：

孩子链法：

转换

孩子兄弟表示法：

将树转换为二叉树：

  • 加线：在兄弟之间加一连线。
  • 抹线：对每个结点，除其第一孩子外，去除其与其余孩子之间的关系。
  • 旋转：以树的根结点为轴心，将整棵树顺时针转 45`。
  • 树转换为二叉树其右子树一定为空。

二叉树转换为树：

  • 加线：若 p 结点是双亲结点的左孩子则将 p 的右孩子，右孩子的右孩子，······沿分支找到的所有右孩子，都与 p 的双亲连起来。
  • 抹线：抹掉原二叉树中双亲与右孩子之间的连线。
  • 调整：将结点按层次排列，形成树结构。

森林转换为二叉树：将各棵树分别转换成二叉树，将每棵树的根结点用线相连。

哈夫曼树

基础概念

  • 路径：若树中存在某个结点序列 k_1,k_2······k_j。满足 k_i 是 k_{i+1}的双亲，则该结点序列是树上的一条路径。

  • 树的路径长度是指树根到树中每一个结点的路径之和。

  • 完全二叉树的路径长度最短。

  • 结点的权：给树的结点赋以一定意义的数值，称为结点的全权。

  • 结点的带权路径长度：从树根到某个结点的路径长度与该结点的权的积。

  • 树的带权路径长度：树中所有叶子结点的带权路径长度之和。

  • 哈夫曼树的定义：

    • 由 n 个带权叶子结点构成的二叉树具有不同形态。
    • 其中 WPL 最小的二叉树
    • 又叫做最优二叉树，或最佳判定树。

    $$ wpl = \sum_{k=1}^{n}w_kl_k $$

    其中，w_k 是第 i 个叶子结点的权值，l_k 是根到第 i 个叶子结点的路径长度。

创建哈夫曼树与哈夫曼编码

创建：

初始化 n 个权值，到 forest 的前 n 个单元，作为 forest 中 n 个孤立的根结点。

  • 将前 n 个单元的双亲、左、右孩子指针均置为 0。

  • 不妨将下标为 0 的单元留空。

  • foreach pos in(n+1~2n-1) begin 进行 1 次合并，从 froest 中删除两棵树，生成 1 棵新树： 从 forest 的根结点中，选取根结点权值最小、次小的两棵树 p1 和 p2。 合并 forest[p1]和 forest[p2]，生成新根结点 forest[pos] 置 forest[pos].w = forest[p1].w + forest[p2].w 置 forest[p1]和 forest[p2]分别为 forest[pos]的左右孩子。 置 forest[p1]和 forest[p2]的双亲为 forest[pos] endforeach return

**前缀码：**任一字符的编码，不能是其他字符的前缀。

  • 将值作为结点的值，将权重作为边。
  • 构造最优二叉树
  • 将树中每个结点的左分支置为 0，右分支置为 1。
  • 从根到叶子结点的一个标号序列，就是该叶子结点的编码。

原因：没有一片树叶是其他树叶的祖先，所以叶子结点编码不可能是其他叶子结点编码的前缀。

数据处理
data = []
with open("huffmandata.txt", "r", encoding="utf-8") as f:
    data = f.read()
data[1]
'b' 
nums = [0,0,0,0,0]
for i in data:
    if(i == 'a'):
        nums[0] += 1
    if(i == 'b'):
        nums[1] += 1
    if(i == 'c'):
        nums[2] += 1
    if(i == 'd'):
        nums[3] += 1
    if(i == 'e'):
        nums[4] += 1
nums
[398964, 400200, 399318, 400002, 401516] 
weight = [0, 0, 0, 0, 0]
for i in range(5):
    weight[i] = nums[i]/len(data)
weight
[0.199482, 0.2001, 0.199659, 0.200001, 0.200758] 
op = [0, 0.199482, 0.2001, 0.199659, 0.200001, 0.200758, 0, 0, 0, 0, ]
mem = [1,1,1,1,1,1,1,1,1,1,]
len(mem)
10
生成哈夫曼树
op = [0.199482, 0.2001, 0.199659, 0.200001, 0.200758, 0, 0, 0, 0,]
mem = [1,1,1,1,1,1,1,1,1,]  # 标记是否用过
temp = []  # 存储逆序前的哈夫曼树
weizhi = []

n = len(weight)
c = n
for i in range(n, 2*n-1):
    min_1 = 1
    min_1_index = 0
    min_2 = 1
    min_2_index = 0

    for j in range(0, c):
        if(op[j]*mem[j] < min_1):
            min_1 = op[j]
            min_1_index = j
    for j in range(0, c):
        if((op[j]*mem[j] < min_2) & (op[j] != min_1)):
            min_2 = op[j]
            min_2_index = j
    
    # 标记
    mem[min_1_index] = 20  # 这里只要是一个较大的数就行
    mem[min_2_index] = 20
    temp.append(op[min_1_index])
    temp.append(op[min_2_index])
    print(min_1_index,min_2_index)
    if(min_1_index < n):
        weizhi.append(min_1_index)
    if(min_2_index < n):
        weizhi.append(min_2_index)
    op[i] = op[min_1_index] + op[min_2_index]
    c += 1

# print(op)
temp.append(1)
# 逆序
huffmantree = [0,]
for i in range(len(op)-1,-1,-1):
    huffmantree.append(temp[i])

print(weizhi)
huffmantree
0 2 3 1 4 5 6 7 [0, 2, 3, 1, 4] [0, 1, 0.599899, 0.40010100000000004, 0.39914099999999997, 0.200758, 0.2001, 0.200001, 0.199659, 0.199482]
生成最优前缀码
l = len(huffmantree)
# 生成的列表方便逆序生成正确的编码
codes = []
for i in range(l-1, int(l/2)-1, -1):
    # print(i)
    codes.append(-1)
    while(int(i/2) != 0):
        if(i%2 == 1):
            codes.append(1)
        else:
            codes.append(0)
        i = int(i/2)
codes
[-1, 1, 0, 0, -1, 0, 0, 0, -1, 1, 1, -1, 0, 1, -1, 1, 0] 
# 找到对应的位置
element_src = ['a', 'b', 'c', 'd', 'e']
element = ['x','x','x','x','x']
for i in range(0, len(element_src)):
    element[i] = element_src[weizhi[i]]

element
['a', 'c', 'd', 'b', 'e'] 
ele_encode = {}
s = ""
j = 0
for i in range(len(codes)-1,-1,-1):
    if(codes[i] == -1):
        ele_encode[element[j]] = s
        j += 1
        s = ""
    else:
        s += str(codes[i])

ele_encode
{'a': '01', 'c': '10', 'd': '11', 'b': '000', 'e': '001'}
本页内容导航