Chapter5_Tree_an_Binary_Tree

Pomni Lv2
  2024-12-02 14:55:23 2024-12-02 14:55:23 Created   2024-12-03 21:11:11 2024-12-03 21:11:11 Updated      3.8k Words  16 Mins  

树。。。
嗯。。。

（先按照书上的结构，感觉还是挺清晰的hhh。）

5.1 树和二叉树的定义

5.1.1 树的定义

  • 树：n个节点的有限集。
    （1）有且只有一个根节点。
    （2）其余节点互不相交。成为根的子树。

    💡树的结构定义是递归的定义。

  • 树的表示方式
    （1）嵌套集合（图a）
    （2）广义表（图b）
    （3）凹入表示法（图c）

5.1.2 树的基本术语

见书P107-108
（懒得敲）
注：“双亲”改为父亲

5.1.3 二叉树的定义

  • 二叉树:
    （1）有且只有一个根节点
    （2）其余节点分为两个互不相交的子集T1和T2。T1和T2本身又是二叉树。
    💡：二叉树的子树有次序不能颠倒。

5.2 案例引入

1️⃣ 数据压缩

💡哈夫曼编码（详见5.7节）

2️⃣ 二叉树求解表达式的值

  • 叶子节点为运算操作数，根节点为运算符。

5.3 树和二叉树的抽象数据类型定义

5.4 二叉树的性质和存储结构

5.4.1 性质

  • 性质一：第i层至多有2i-1个节点。
  • 性质二：深度为k的二叉树至多有2k-1个节点。
  • 性质三：度为0的节点数为n0，度为2的节点数为n2，则n0=n2+1。

特殊二叉树

  • 满二叉树：深度为k且含有2k-1个节点。

  • 完全二叉树：深度为k，有n个节点，当且仅当每一个节点都与深度为k的满二叉树中1至n的节点一一对应。

    • 特点：
      （1）叶子节点只在最大的两层上出现。
      （2）右分支子孙最大层次为l，左分支子孙最大层次为l或l+1。

  • 性质四：具有n个节点的完全二叉树深度为(\lfloor \log_{2}n \rfloor)+1。

  • 性质五：对一棵有n个节点的完全二叉树，对任一节点i，有：
    （1）i=1，是根节点；i>1，(\lfloor i/2 \rfloor)是其父亲结点。
    （2）节点i，若2i>n，则无左孩子；否则，i的左孩子为2
    i。
    （3）节点i，若2i+1>n，则无左孩子；否则，i的左孩子为2
    i+1。

5.4.2 存储结构

1. 顺序存储结构

  • 完全二叉树：自上而下，自左至右。节点i放入数组中i-1的位置。
  • 一般二叉树：节点i放入数组中i-1的位置。中间不存在的节点用0占位。

🌟顺序存储结构适合完全二叉树。
🚨最坏的情况：深度为k且只有k个节点的单支树，需要2k-1的一维数组。

2. 链式存储结构

  • 二叉链表
    域：数据域和左、右指针域
    空域：n个节点有n+1个空链域（=>线索链表）

    1
    2
    3
    4
    5
    struct BiTNode
    {
        int data;
        BiTNode *lchild, *rchild;
    };

  • 三叉链表
    域：数据域，父亲指针域，左、右指针域
    优势：便于寻找节点x的父亲

5.5 遍历二叉树和线索二叉树

5.5.1 遍历

1.遍历算法

遍历实质：对二叉树进行线性化。

递归遍历

  • 先序遍历：根左右
    1
    2
    3
    4
    5
    6
    7
    8
    9
    void PreOrderTraverse(BiTNode* T)
    {
        if(T)
        {
            cout<<T->data;
            InOrderTraverse(T->lchild);
            InOrderTraverse(T->rchild);
        }
    }
  • 中序遍历：左根右
    1
    2
    3
    4
    5
    6
    7
    8
    9
    void InOrderTraverse(BiTNode* T)
    {
        if(T)
        {
            InOrderTraverse(T->lchild);
            cout<<T->data;
            InOrderTraverse(T->rchild);
        }
    }
  • 后序遍历：左右根
    1
    2
    3
    4
    5
    6
    7
    8
    9
    void InOrderTraverse(BiTNode* T)
    {
        if(T)
        {
            InOrderTraverse(T->lchild);
            InOrderTraverse(T->rchild);
            cout<<T->data;
        }
    }

非递归遍历

递归工作栈：
（1）工作记录：递归调用的语句编号以及指向根节点的指针。栈顶记录的指针非空，则遍历左子树（左子树指针进栈）。
（2）栈顶指针为空，则退回上一层。从左子树返回，则访问根节点。
（3）从右子树返回，则退栈。遍历右子树时不需要保存当前层的根指针，直接修改栈顶指针即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void InOrderTraverse(BiTNode* T)
{
    InitialStack(S); //创建空栈
    BiTNode* p=T;
    BiTNode* q=new BiTNode;

    while(q||!isEmptyStack())
    {
        if(p)
        {
            Push(S,p);
            p=p->lchild;
        }
        else
        {
            Pop(S,q); //左孩子和根节点被弹出
            cout<<q->data;
            p=q->rchild; //遍历右孩子
        }
    }
}

算法时间复杂度：O(n)

  • 层次遍历：从左到右，从上至下。
    🌟非递归结构，借助队列实现

2. 根据遍历序列确定二叉树

先序加中序$\Rightarrow$唯一确定
后序加中序$\Rightarrow$唯一确定

3. 二叉树遍历算法的应用

  • 创建二叉树的存储结构———二叉链表

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    //按照先序遍历算法创建链表

    void CreateBiTree(BiTNode*& T)
    {
        char ch;
        cin>>ch;
        if(ch=='#')
            *T=NULL;
        else 
        {
            T=new BiTNode;
            T->data=ch;
            T->lchild=NULL;
            T->rchild=NULL;
            CreateBiTree(T->lchild);
            CreateBiTree(T->rchild);
        }
    }

  • 复制二叉树：申请新节点空间，复制节点；递归复制左右子树节点。

1
2
3
4
5
6
7
8
9
10
11
12
void CopyTree(BiTNode* T, BiTNode*& NewT)
{
    if(T==NULL)
    {
        NewT=NULL;
        return;
    }
    NewT=new BiTNode;
    NewT->data=T->data;
    CopyTree(T->lchild,NewT->lchild);
    CopyTree(T->rchild,NewT->rchild);
}

  • 计算二叉树的深度

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    int getDepth(BiTNode* T)
    {
        if(T==NULL)
        {
            return 0;
        }

        int left=getDepth(T->lchild);
        int right=getDepth(T->rchild);
        return left>right?left+1:right+1;

    }

  • 统计节点总个数

    1
    2
    3
    4
    5
    6
    7
    int nodesNum(BiTNode* T)
    {
        if(T==NULL)
            return 0;
        
        return nodesNum(T->lchild)+nodesNum(T->rchild)+1;
    }

5.5.2 线索二叉树

1. 基本概念

遍历二叉树是将二叉树节点排列成线性序列，这个线性序列中有且仅有一个直接前驱和直接后继。
n个节点二叉链表必定有n+1个空链域。$\Rightarrow$ 利用空链域存放节点前驱和后继信息。

1
2
3
4
5
6
struct Node
{
    int data;
    int lflag,rflag;
    Node *lchild, *rchild;
};

$$
lflag=
\begin{cases}
0 \quad lchild指示左孩子\
1 \quad lchild指示前驱
\end{cases}
$$

$$
rflag=
\begin{cases}
0 \quad lchild指示右孩子\
1 \quad lchild指示后继
\end{cases}
$$

相关概念：

  • 线索链表
  • 线索：指向节点前驱和后继的指针
  • 线索二叉树
  • 线索化

例：中序线索二叉树
创建一个头节点，lchild指向根节点，rchild指向最后一个节点。
中序遍历第一个节点lchild和最后一个节点rchild指向头节点。
$\Rightarrow$创建了一个双向线索链表。

2. 构造

线索化过程是在遍历中修改空指针$\Rightarrow$递归。
指针pre指向刚刚访问过的节点，指针T指向当前访问的节点。

不带头结点

先序线索二叉树
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
Node* pre=new Node;//pre是全局变量
pre->lchild=NULL;
pre->rchild=NULL;
void InThreading(Node* T)
{
    if(T)
    {
        
        if(!T->lchild)//当前节点没有左孩子
        {
            T->lflag=1;
            T->lchild=pre;//连接前驱。
        }
        else
        {
            T->lflag=0;
        }

        if(!pre->rchild)//前驱没有右孩子
        {
            pre->rflag=1;
            pre->rchild=T;//连接后继
        }
        else
        {
            pre->rflag=0;
        }

        pre=T;//更新pre
        InThreading(T->lchild);//遍历左子树
        InThreading(T->rchild);//遍历右子树
    }
}
中序线索二叉树
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
Node* pre=new Node;//pre是全局变量
pre->lchild=NULL;
pre->rchild=NULL;
void InThreading(Node* T)
{
    if(T)
    {
        InThreading(T->lchild);//遍历左子树

        if(!T->lchild)//当前节点没有左孩子
        {
            T->lflag=1;
            T->lchild=pre;//连接前驱。
        }
        else
        {
            T->lflag=0;
        }

        if(!pre->rchild)//前驱没有右孩子
        {
            pre->rflag=1;
            pre->rchild=T;//连接后继
        }
        else
        {
            pre->rflag=0;
        }

        pre=T;//更新pre

        InThreading(T->rchild);//遍历右子树
    }
}
后序线索二叉树
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
Node* pre=new Node;//pre是全局变量
pre->lchild=NULL;
pre->rchild=NULL;
void InThreading(Node* T)
{
    InThreading(T->lchild);//遍历左子树
    InThreading(T->rchild);//遍历右子树
    if(T)
    {
        
        if(!T->lchild)//当前节点没有左孩子
        {
            T->lflag=1;
            T->lchild=pre;//连接前驱。
        }
        else
        {
            T->lflag=0;
        }

        if(!pre->rchild)//前驱没有右孩子
        {
            pre->rflag=1;
            pre->rchild=T;//连接后继
        }
        else
        {
            pre->rflag=0;
        }

        pre=T;//更新pre
        
    }
}

😅其实先序和后序就是把递归的函数位置变了一下。敲完整代码只是为了显得牛逼。

带头节点

以中序遍历为例

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
Node* pre=new Node;//pre是全局变量
pre->lchild=NULL;
pre->rchild=NULL;

void InOrderThreading(Node*& head, Node T)
{
    head=new Node;
    head->lflag=0;
    head->rflag=1;
    head->rchild=head;//初始时指向自己

    if(!T)//树为空
    {
        T->lchild=T;
    }
    else
    {
        head->lchild=T;
        pre=head;
        InThreading(T);//调用不带头节点的算法
        pre->rchild=head;
        pre->rflag=1;
        head->rchild=pre;
    }
}

3. 遍历

先序遍历

中序遍历

  • 算法
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    void InOrderTraverse_Thread(Node* T)
    {
        Node* p=T->lchild;
        while(p!=T)
        {
            while(p->lflag==0)
            {
                p=p->lchild;
            }
            cout<<p->data;
            while(p->rflag==1&&p->rchild!=T)
            {
                p=p->rchild;
                cout<<p->data;
            }
            p=p->rchild;
        }
    }

💡时间复杂度 *O(n)*，空间复杂度 O(1)

后序遍历

5.6 树和森林

5.6.1 树的存储结构

  • 双亲表示法

    1
    2
    3
    4
    5
    struct Node
    {
        int data;
        int parent;//存父亲的位置
    };

    🚨求孩子时需要从头遍历

  • 孩子表示法

    1
    2
    3
    4
    5
    struct Node
    {
        int data;
        Node *child1, *child2, *child3...;
    };

    🚨同构：存在浪费空间的问题
    🚨不同构：操作不便

  • 孩子兄弟表示法
    以二叉树的形式存储树。
1
2
3
4
5
struct CSNode
{
    int data;
    CSNode *firstchild, *nextsibling;
};

5.6.2 森林与二叉树的转换

1. 森林转换成二叉树

左孩子都是第一个孩子，右孩子以及右孩子的右孩子是兄弟。

2. 二叉树转为森林

右孩子以及右孩子的右孩子都是兄弟，左孩子都是第一个孩子。

5.6.3 树和森林的遍历

1. 树的遍历

  • 先根遍历
    先访问根节点再依次访问子树

  • 后根遍历
    先依次后根遍历子树再访问根

2. 森林的遍历

  • 先序遍历
    （1）先访问第一棵树的根节点
    （2）先序遍历第一棵树
    （3）再先序遍历剩余树

  • 中序遍历
    （1）中序遍历第一棵树
    （2）访问第一棵树的根节点
    （3）中序遍历剩余树

🌟树的先根遍历 $ \Leftrightarrow $ 二叉树先序遍历
🌟树的后根遍历 $ \Leftrightarrow $ 二叉树中序遍历

5.7 哈夫曼树及其应用

5.7.1 基本概念

  • 哈夫曼树：带权路径长度最短的树。
    概念详见书P131

💡权值越大的节点离根节点越近。

5.7.2 哈夫曼树的构造算法

1. 哈夫曼树的构造过程

💡贪心算法
选取权值最小的两棵树作为左右子树构造二叉树，这棵二叉树的根是这两棵子树的权值之和。

2. 哈夫曼算法实现

💡观察
$ ~~~~~ $ n个叶子节点的哈夫曼树共2n-1个节点。
$ ~~~~~ $ 哈夫曼树中无度为1的节点。
$ ~~~~~ $ 数组存储✔️：数组大小 2n（a[0]不使用），前n个存叶子节点，后n-1个存非叶子。

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
77
78
79
80
81
//哈夫曼树节点
struct HFNode
{
    int weight;
    int parent, lchild, rchild;
}

void select(HFNode* T,int i,int*& p1, int*& p2);

//构造哈夫曼树
void CreateHFTree(HFNode*& T, int n)
{
    if(n<=1)
    {
        return;
    }

    //初始化
    m=2*n-1;
    T=new HFNode[m+1];//动态分配数组
    for(int i=1;i<=m;i++)
    {
        //先全部初始化为0
        T[i].parent=0;
        T[i].lchild=0;
        T[i].rchild=0;
    }

    for(int i=1;i<=n;i++)
    {
        cin>>T[i].weight;
    }

    //创建
    for(int i=n+1;i<=m;i++)
    {
        //通过n-1次的选择，选择出权值最小的两棵树并保存其序号s1，s2。
        int *p1, *p2;
        select(T,i-1,p1,p2);
        T[*p1].parent=i;
        T[*p2].parent=i;
        T[i].lchild=*p1;
        T[i].rchild=*p2;
        T[i].weight=T[*p1].weight+T[*p2].weight;
    }
}


//select函数的实现

void select(HFNode* T,int i,int*& p1, int*& p2)
{
    int min1=100,min2=100;
    int index1=-1,index2=-1;
    for(int k=1;k<i;k++)
    {
        if(T[i].parent==0)
        {
            if(T[k].weight<min1)
            {
                min2=min1;//在min1更新前存min1的值，能使min2最终不等于min1
                index2 = index1;//同上
                min1=T[k].weight;
                index1=k;
            }
            if(T[k].weight<min2)
            {
                min2=T[k].weight;
                index2=k;
            }
        }
    }

    /*
        p1=&min1;
        p2=&min2;
        min1 和 min2 只是局部变量，它们的地址并不是你需要返回的节点地址。
    */
    p1=&T[index1];
    p2=&T[index2];
}

5.7.3 哈夫曼编码

1. 编码思想

  • 相关概念

    • 前缀编码：任一编码都不是其他任何编码的前缀。
    • 哈夫曼编码：n个叶子的哈夫曼树，左分支赋0，右分支赋1。

  • 性质

    • 哈夫曼编码是前缀编码。
    • 哈夫曼编码是最优前缀编码。

2. 编码算法

由哈夫曼树到哈夫曼编码：
依次以叶子为出发点，向上回溯至根节点。走左分支生成0，右分支生成1。

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
void CreateHFCode(HFNode* T, char**& hc, int n)
{
    hc=new char*[n+1];

    //临时数组
    char *cd=new char[n];
    cd[n-1]='\0';
    for(int i=1;i<=n;i++)
    {
        int start=n-1;
        int c=i;
        int f=T[i].parent;

        //由叶子节点向上回溯
        while(f!=0)
        {
            --start;
            if(T[f].lchild==c)
            {
                cd[start]='0';
            }
            else
            {
                cd[start]='1';
            }
            c=f;
            f=T[f].parent;
        }

        hc[i]=new char[n-start];
        strcpy(hc[i], &cd[start]);
    }

    //临时数组记得销毁
    delete []cd;
}

3. 文件编码译码

  • 编码
    依次读入字符，并对于哈夫曼编码表转换成对于编码串。
  • 译码
    依次读入二进制码，从根节点出发。读入0，走左孩子，读入1，走右孩子。

5.8 案例分析

求解表达式的值

表达式树的创建

思路：

  • 叶子节点为操作数，分支节点为运算符。
  • 创建工作栈：OPTR，暂存运算符；EXPT，暂存已建立好的表达式树的根节点。

（每个表达式以”#”开始和结束）

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
void InitExpTree()
{
    InitStack(EXPT);
    InitStack(OPTR);

    Push(OPTR, '#');

    char ch;
    cin>>ch;

    while(ch!='#'||GetTop(OPTR)!='#')//栈顶元素也不为'#'
    {
        if(!In(ch))//ch不是运算符
        {
            CreateExpTree(T,NULL,NULL,ch);
            Push(EXPT,T);
            cin>>ch;
        }
        else
        {
            switch(Precede(GetTop(OPTR),ch))
            {
                case '<':
                    Push(OPTR,ch);
                    cin>>ch;
                    break;
                case '>':
                    Pop(OPTR,theta);//弹出OPTR栈顶运算符，并用theta存储
                    Pop(EXPT,b);
                    Pop(EXPT,a);//弹出EXPT栈顶两个操作数
                    CreateExpTree(T,a,b,theta);//以theta为根，a为左子树，b为右子树，创建二叉树
                    Push(EXPT,T);
                    break;
                case '=':
                    Pop(OPTR,x);
                    cin>>ch;
                    break;
            }
        }
    }
}
1
2
3
//初始化栈

void InitStack()
1
2
3
//压入栈


1
2
//返回栈顶元素

1
2
3
//创建ERPT表达式树
 void CreateExpTree(T,NULL,NULL,ch)

1
2
3
//
Precede(GetTop(OPTR),ch)

💡时间复杂度：O(n)
$ ~~~~ $空间复杂度：O(n)

表达式树求值

思路：

  • 为叶子节点，则返回叶子节点的数值
  • 非叶子节点，递归计算左右子树的值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int EvaluateTree(BiTNode* T)
{
    int lvalue=0;
    int rvalue=0;

    if(T->lchild=NULL&&T->rchild==NULL)
    {
        return T->data-'0';//因为入栈的是ascll字符，计算值需要用ascll码值相减
    }

    else
    {
        lvalue=EvaluateExpTree(T->lchild);
        rvalue=EvaluateExpTree(T->rchild);
        return GetValue(T->data,lvalue,rvalue);
    }
}

💡时间复杂度和空间复杂度：O(n)

Why can’t I keep high?

12.3敲完。
照着敲都敲了两天。。。。。。
有好多还是记不得也没理解。。。。。。
可恶！

  • Title: Chapter5_Tree_an_Binary_Tree
  • Author: Pomni
  • Created at : 2024-12-02 14:55:23
  • Updated at : 2024-12-03 21:11:11
  • Link: https://redefine.ohevan.com/2024/12/02/Tree-and-Binary-Tree/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
Chapter5_Tree_an_Binary_Tree
  1. 5.1 树和二叉树的定义
    1. 5.1.1 树的定义
    2. 5.1.2 树的基本术语
    3. 5.1.3 二叉树的定义
  2. 5.2 案例引入
    1. 1️⃣ 数据压缩
    2. 2️⃣ 二叉树求解表达式的值
  3. 5.3 树和二叉树的抽象数据类型定义
  4. 5.4 二叉树的性质和存储结构
    1. 5.4.1 性质
      1. 特殊二叉树
    2. 5.4.2 存储结构
      1. 1. 顺序存储结构
      2. 2. 链式存储结构
  5. 5.5 遍历二叉树和线索二叉树
    1. 5.5.1 遍历
      1. 1.遍历算法
      2. 2. 根据遍历序列确定二叉树
      3. 3. 二叉树遍历算法的应用
    2. 5.5.2 线索二叉树
      1. 1. 基本概念
      2. 2. 构造
      3. 3. 遍历
  6. 5.6 树和森林
    1. 5.6.1 树的存储结构
    2. 5.6.2 森林与二叉树的转换
      1. 1. 森林转换成二叉树
      2. 2. 二叉树转为森林
    3. 5.6.3 树和森林的遍历
      1. 1. 树的遍历
      2. 2. 森林的遍历
  7. 5.7 哈夫曼树及其应用
    1. 5.7.1 基本概念
    2. 5.7.2 哈夫曼树的构造算法
      1. 1. 哈夫曼树的构造过程
      2. 2. 哈夫曼算法实现
    3. 5.7.3 哈夫曼编码
      1. 1. 编码思想
      2. 2. 编码算法
      3. 3. 文件编码译码
  8. 5.8 案例分析
    1. 求解表达式的值
      1. 表达式树的创建
      2. 表达式树求值
  9. Why can’t I keep high?