CosmosNing的个人博客

探索·好奇

0%

数据结构复习笔记5-树与二叉树

发表于 更新于 分类于
本文字数： 11k 阅读时长 ≈ 10 分钟
整理一下树和二叉树的知识

6．树与二叉树

二叉树的定义、性质和存储结构

定义

（见教材 P121 ）

性质

  1. 第 \(i\) 层至多 \(2^{i-1}\) 个结点

  2. 深度为 \(k\) ，至多 \(2^{k} - 1\) 个结点

  3. 设 \(n_0\) 为终端（叶子）结点个数， \(n_2\) 为度为 2 的结点个数，则 \(n_0 = n_2 +1​\)

  4. 具有 \(n\) 个结点的完全二叉树（每一个结点都与深度为 \(k\) 的满二叉树中的编号从 1 至 \(n\) 的结点一一对应）的深度为 \(\lfloor log_{2}n\rfloor + 1\) （普通二叉树不一定有此性质，下同）

  5. 具有 \(n\) 个结点的完全二叉树，按层序编号，对任意结点 \(i\) ，有

条件 结论 否则
\(i = 1\) \(i\) 是二叉树的根，无双亲 PARENT( \(i\) ) = \(\lfloor i/2\rfloor\)(\(i>1\))
\(2i>n\) 结点 \(i\) 无左孩子（为叶子节点） LCHILD( \(i\) ) = \(2i\)
\(2i+1>n\) 结点 \(i\) 无右孩子 RCHILD( \(i\) ) = \(2i+1\)

存储结构

顺序存储结构

1
2
3
4
5
// 顺序存储结构

#define MAX_TREE_SIZE 100                       // 二叉树的最大结点数
typedef TElemType SqBiTree[MAX_TREE_SIZE];      // 0 号存储根结点
SqBiTree bt;

链式存储结构

1
2
3
4
5
6
// 链式存储结构

typedef struct BiNode{
    TElemType     data;
    struct BiNode *lchild, rchild;             // 左右孩子指针
}BiNode, *BiTree;

线索存储

1
2
3
4
5
6
7
8
9
// 二叉线索存储结构

typedef enum{Link, Thread} PointerTag;      // Link = 0：  指针
                                            // Thread = 1：线索
typedef struct BiThrNode{
    TElemType        data;
    struct BiThrNode *lchild, *rchild;      // 左右孩子指针
    PointerTag       LTag, RTag;            // 左右标志
}BiThrNode, *BiThrTree;

遍历二叉树

（以链式存储的二叉树为例，顺序存储的二叉树的对应操作只需将相应的找左右孩子部分依据前述性质修改即可）

先序遍历

若二叉树不空，则

  1. 访问根结点
  2. 先序遍历左子树
  3. 先序遍历右子树
  • 递归实现
1
2
3
4
5
6
7
8
9
void PreOrderTraversal( BiTree bt )
{
    if( bt ) 
    {
        printf(bt->data);
        PreOrderTraversal( bt->Left );
        PreOrderTraversal( bt->Right );
    }
}
  • 非递归实现（★）
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
// 关键是利用栈暂存右孩子。
/* 循环流程：
   打印当前结点;
   若该结点有右孩子，则将右孩子入栈
   若该结点有左孩子，则将指向当前结点的指针指向其左孩子；否则，指向出栈元素
*/
void PreOrderTraversal_NonRecursive( BiTree bt )
{	
    SqStack S;
    BiTree  P = bt;
    InitStack(S);	
    Push(S,NULL);
    
    while (P)
    {     
        printf(P->data);
        
        if (P->rchild)
            Push(S, P->rchild);
        
        if (P->lchild)
            P = P->lchild;
        else 
            Pop(S,P);
    }
}
  • 通过先序遍历，建立二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void CreateBiTree(BiTree *T)
{   /* 算法6.4:按先序次序输入二叉树中结点的值（一个字符），空格字符代表空树 */
    /* 构造二叉链表表示的二叉树T。 */
    /* 输入示例(这里用 # 代表空格)：-+a##*b##-c##d##/e##f## */
    /* 即可构建教材 P129 图 6.9 表达式 a+b*(c-d)-e/f 的二叉树*/
    scanf( &ch );
    
    if(ch == '') /* 空 */
        T = NULL;
    else
    {
        if(!(T = (BiTree)malloc(sizeof(BiTNode))))
            exit(OVERFLOW);
        
        T->data = ch; /* 生成根结点 */
        CreateBiTree(T->lchild); /* 构造左子树 */
        CreateBiTree(T->rchild); /* 构造右子树 */
    }
}

中序遍历

若二叉树不空，则

  1. 中序遍历左子树
  2. 访问根结点
  3. 中序遍历右子树
  • 递归实现
1
2
3
4
5
6
7
8
9
void InOrderTraversal( BiTree bt )
{
    if( bt ) 
    {
        InOrderTraversal( bt->Left );
        printf(bt->data);
        InOrderTraversal( bt->Right );
    }
}
  • 非递归实现（★）
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
// 在遍历左子树之前，先把根结点入栈，当左子树遍历结束后，从栈中弹出，访问，再遍历右子树

Status InOrder_NonRecursive1(BiTree T, Status ( * Visit)( TElemType e))
{   /* 采用二叉链表存储结构，Visit是对数据元素操作的应用函数。算法6.2 */
    /* 中序遍历二叉树T的非递归算法(利用栈)，对每个数据元素调用函数Visit */
    SqStack S;
    BiTree p;
    InitStack(&S);
    Push(&S,T); /* 根指针进栈 */
    while(!StackEmpty(S))
    {
        while(GetTop(S,&p)&&p)
            Push(&S,p->lchild); /* 向左走到尽头 */
        Pop(&S,&p); /* 空指针退栈 */
        if(!StackEmpty(S))
        { /* 访问结点,向右一步 */
            Pop(&S,&p);
            if(!Visit(p->data))
                return ERROR;
            Push(&S,p->rchild);
        }
    }
    return OK;
}

Status InOrder_NonRecursive2(BiTree T, Status ( * Visit)( TElemType e))
{   /* 采用二叉链表存储结构，Visit是对数据元素操作的应用函数。算法6.3 */
    /* 中序遍历二叉树T的非递归算法(利用栈)，对每个数据元素调用函数Visit */
    SqStack S;
    InitStack(&S);
    while(T||!StackEmpty(S))
    {
        if(T)
        { /* 根指针进栈,遍历左子树 */
            Push(&S,T);
            T=T->lchild;
        }
        else
        { /* 根指针退栈,访问根结点,遍历右子树 */
            Pop(&S,&T);
            if(!Visit(T->data))
                return ERROR;
            T=T->rchild;
        }
    }
    return OK;
}

### 后序遍历

若二叉树不空，则

  1. 后序遍历左子树
  2. 后序遍历右子树
  3. 访问根结点
  • 递归实现
1
2
3
4
5
6
7
8
9
10
void PostOrderTraversal( BiTree bt )
{
    if( bt ) 
    {
        
        PostOrderTraversal( bt->Left );
        PostOrderTraversal( bt->Right );
        printf(bt->data);
    }
}
  • 非递归实现（★）
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
// 设定一个指针，指向 最近访问过的结点。
// 在退栈取出根结点时，需判断：
// 若根结点的右子树为空，或它的右子树非空，但已遍历完毕，
// 即它的右子树根结点恰好是最近一次访问过的结点时，应该遍历该根结点。
// 反之，该根结点应重新入栈，先遍历它的右子树。

void PostOrderTraversal_NonRecursive( BiTree bt )
{
    BiTree p = bt, q = NULL;                 //q 指向 最近访问过的结点
    SqStack S;	
    InitStack(S);
    
    while (p || !StackEmpty(S))
    {  
        if (p)                               // 走到最左边
        {
            Push(S,p);
            p=p->lchild;  
        }
        else                                 // 向右
        {
            GetTop(S, p);                    // 取栈顶结点
            
            if(p->rchild && p->rchild != q)  // 若子树存在，且未被访问
            {
            	p = p->rchild;               // 转向右
            	Push(S,p);                   // 压入栈
            	p = p->lchild;               // 再走到最左
            }
            else                             // 否则，弹出结点并访问
            {
                Pop(S, p);                   // 将结点弹出
                Visit(p->data);              // 访问该结点
                q = p;                       // 记录最近访问过的结点
                p = NULL;                    // 结点访问完后，重置p
            }
       }
    }
}

层次遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 先将根结点入队，然后出队，访问该结点，
// 若它有左子树，则将其左子树根结点入队；
// 若它有右子树，则将其右子树根结点入队；
// 然后出队，对出队结点访问，如此反复，直至队列为空

void LevelOrderTraversal( BiTree bt )
{
    InitQueue(Q);
    BiTree p;
    
    EnQueue(Q, bt);
    
    while( ! IsEmpty(Q) )
    {
        Dequeue(Q, p);
        visit(p);
        
        if(p->lchild != NULL)
            EnQueue(Q, p->lchild);
        
        if(p->rchild != NULL)
            EnQueue(Q, p->rchild);
    }
}

线索二叉树

  • 经常遍历或查找结点在遍历所得线性序列中的前驱和后继，则应使用线索链表作为存储结构。

遍历线索二叉树

教材和参考书只给出了中序

中序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Status InOrderTraverse_Thr(BiThrTree T,Status(*Visit)(TElemType))
{   /* 中序遍历二叉线索树T(头结点)的非递归算法。算法6.5 */
    BiThrTree p;
    p=T->lchild; /* p指向根结点 */
    while(p!=T)
    { /* 空树或遍历结束时,p==T */
        while(p->LTag==Link)
            p=p->lchild;
        if(!Visit(p->data)) /* 访问其左子树为空的结点 */
            return ERROR;
        while(p->RTag==Thread&&p->rchild!=T)
        {
            p=p->rchild;
            Visit(p->data); /* 访问后继结点 */
        }
        p=p->rchild;
    }
    return OK;
}

二叉树的线索化

中序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Status InOrderThreading(BiThrTree *Thrt,BiThrTree T)
{   /* 中序遍历二叉树T,并将其中序线索化,Thrt指向头结点。算法6.6 */
    *Thrt=(BiThrTree)malloc(sizeof(BiThrNode));
    if(!*Thrt)
        exit(OVERFLOW);
    (*Thrt)->LTag=Link; /* 建头结点 */
    (*Thrt)->RTag=Thread;
    (*Thrt)->rchild=*Thrt; /* 右指针回指 */
    if(!T) /* 若二叉树空，则左指针回指 */
        (*Thrt)->lchild=*Thrt;
    else
    {
        (*Thrt)->lchild=T;
        pre=*Thrt;
        InThreading(T); /* 中序遍历进行中序线索化 */
        pre->rchild=*Thrt;
        pre->RTag=Thread; /* 最后一个结点线索化 */
        (*Thrt)->rchild=pre;
    }
    return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void InThreading(BiThrTree p)
{   /* 中序遍历进行中序线索化。算法6.7 */
    if(p)
    {
        InThreading(p->lchild); /* 递归左子树线索化 */
        if(!p->lchild) /* 没有左孩子 */
        {
            p->LTag=Thread; /* 前驱线索 */
            p->lchild=pre; /* 左孩子指针指向前驱 */
        }
        if(!pre->rchild) /* 前驱没有右孩子 */
        {
            pre->RTag=Thread; /* 后继线索 */
            pre->rchild=p; /* 前驱右孩子指针指向后继(当前结点p) */
        }
        pre=p; /* 保持pre指向p的前驱 */
        InThreading(p->rchild); /* 递归右子树线索化 */
    }
}

树的定义和存储结构

定义

（见教材 P118 ）

存储结构

双亲表示法

  • 便于找爹（常数时间内），不易找孩子（可能需要遍历整个树）
1
2
3
4
5
6
7
8
9
10
11
12
13
// 双亲存储表示

#define MAX_TREE_SIZE 100

typedef struct PTNode{             // 结点结构
    TElemType data;
    int       parent;              // 双亲位置域
}PTNode;

typedef struct{                    // 树结构
    PTNode nodes[MAX_TREE_SIZE];
    int    r,n;                    // 根的位置和结点数
}PTree;

孩子表示法

  • 便于找孩子，不易找爹
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 孩子链表存储表示

typedef struct CTNode{            // 孩子节点
    int           child;
    struct CTNode *next;
} *ChildPtr;

typedef struct{
    TElemType data;
    ChildPtr  firstchild;         // 孩子链表头指针
}CTBox;

typedef struct{
    CTBox nodes[MAX_TREE_SIZE];
    int   r, n;                   // 根的位置和结点数
}CTree;

变种：带双亲的孩子链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 孩子链表存储表示

typedef struct CTNode{            // 孩子节点
    int           child;
    struct CTNode *next;
} *ChildPtr;

typedef struct{
    TElemType data;
    ChildPtr  firstchild;         // 孩子链表头指针
    int       parent;             // 增添双亲位置域
}CTBox;

typedef struct{
    CTBox nodes[MAX_TREE_SIZE];
    int   r, n;                   // 根的位置和结点数
}CTree;

孩子兄弟表示法

  • 便于实现各种操作
1
2
3
4
5
6
// 孩子-兄弟（二叉链表）存储表示

typedef struct CSNode{
    ElemType data;
    struct CNode *firstchild, *nextsibling;
}CSNode, *CSTree;

赫夫曼编码

  • 存储结构
1
2
3
4
5
6
7
/* 赫夫曼树和赫夫曼编码的存储表示 */
typedef struct
{
    unsigned int weight;
    unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; /* 动态分配数组存储赫夫曼树 */
typedef char **HuffmanCode; /* 动态分配数组存储赫夫曼编码表 */
  • 求赫夫曼编码
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
void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,int n) 
    /* 算法6.12 */
{   /* w存放n个字符的权值(均>0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC */
    int m,i,s1,s2,start;
    unsigned c,f;
    HuffmanTree p;
    char *cd;
    if(n<=1)
        return;
    m=2*n-1;
    *HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /* 0号单元未用 */
    for(p=*HT+1,i=1;i<=n;++i,++p,++w)
    {
        (*p).weight=*w;
        (*p).parent=0;
        (*p).lchild=0;
        (*p).rchild=0;
    }
    for(;i<=m;++i,++p)
        (*p).parent=0;
    for(i=n+1;i<=m;++i) /* 建赫夫曼树 */
    { /* 在HT[1~i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2 */
        select(*HT,i-1,&s1,&s2);
        (*HT)[s1].parent=(*HT)[s2].parent=i;
        (*HT)[i].lchild=s1;
        (*HT)[i].rchild=s2;
        (*HT)[i].weight=(*HT)[s1].weight+(*HT)[s2].weight;
    }
    /* 从叶子到根逆向求每个字符的赫夫曼编码 */
    *HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
    /* 分配n个字符编码的头指针向量([0]不用) */
    cd=(char*)malloc(n*sizeof(char)); /* 分配求编码的工作空间 */
    cd[n-1]='\0'; /* 编码结束符 */
    for(i=1;i<=n;i++)
    { /* 逐个字符求赫夫曼编码 */
        start=n-1; /* 编码结束符位置 */
        for(c=i,f=(*HT)[i].parent;f!=0;c=f,f=(*HT)[f].parent)
            /* 从叶子到根逆向求编码 */
            if((*HT)[f].lchild==c)
                cd[--start]='0';
        else
            cd[--start]='1';
        (*HC)[i]=(char*)malloc((n-start)*sizeof(char));
        /* 为第i个字符编码分配空间 */
        strcpy((*HC)[i],&cd[start]); /* 从cd复制编码(串)到HC */
    }
    free(cd); /* 释放工作空间 */
}
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
void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,int n) 
    /* 前半部分为算法6.12 */
{   /* w存放n个字符的权值(均>0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC */
    int m,i,s1,s2; /* 此句与上面的不同 */
    unsigned c,cdlen; /* 此句与上面的不同 */
    HuffmanTree p;
    char *cd;
    if(n<=1)
        return;
    m=2*n-1;
    *HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /* 0号单元未用 */
    for(p=*HT+1,i=1;i<=n;++i,++p,++w)
    {
        (*p).weight=*w;
        (*p).parent=0;
        (*p).lchild=0;
        (*p).rchild=0;
    }
    for(;i<=m;++i,++p)
        (*p).parent=0;
    for(i=n+1;i<=m;++i) /* 建赫夫曼树 */
    { /* 在HT[1~i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2 */
        select(*HT,i-1,&s1,&s2);
        (*HT)[s1].parent=(*HT)[s2].parent=i;
        (*HT)[i].lchild=s1;
        (*HT)[i].rchild=s2;
        (*HT)[i].weight=(*HT)[s1].weight+(*HT)[s2].weight;
    }
    /* 以下为算法6.13，无栈非递归遍历赫夫曼树,求赫夫曼编码，以上同算法6.12 */
    *HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
    /* 分配n个字符编码的头指针向量([0]不用) */
    cd=(char*)malloc(n*sizeof(char)); /* 分配求编码的工作空间 */
    c=m;
    cdlen=0;
    for(i=1;i<=m;++i)
        (*HT)[i].weight=0; /* 遍历赫夫曼树时用作结点状态标志 */
    while(c)
    {
        if((*HT)[c].weight==0)
        { /* 向左 */
            (*HT)[c].weight=1;
            if((*HT)[c].lchild!=0)
            {
                c=(*HT)[c].lchild;
                cd[cdlen++]='0';
            }
            else if((*HT)[c].rchild==0)
            { /* 登记叶子结点的字符的编码 */
                (*HC)[c]=(char *)malloc((cdlen+1)*sizeof(char));
                cd[cdlen]='\0';
                strcpy((*HC)[c],cd); /* 复制编码(串) */
            }
        }
        else if((*HT)[c].weight==1)
        { /* 向右 */
            (*HT)[c].weight=2;
            if((*HT)[c].rchild!=0)
            {
                c=(*HT)[c].rchild;
                cd[cdlen++]='1';
            }
        }
        else
        { /* HT[c].weight==2,退回 */
            (*HT)[c].weight=0;
            c=(*HT)[c].parent;
            --cdlen; /* 退到父结点,编码长度减1 */
        }
    }
    free(cd);
}

解题技巧小结及结论补充

  1. 求解树结点与度之间的关系有（★★★★★）
    • 总结点数 = \(n_0 +n_1+n_2+\cdots+n_m\) （其中 \(n_i\) 表示度为 \(i\) 的结点个数）
    • 总分支数 = \(1n_1+2n_2+\cdots+mn_m\)
    • 总结点数 = 总分支数 + 1
  2. 完全二叉树的一个重要特征：若有度为 1 的结点，则只可能有一个，且该结点只有左孩子而无右孩子
  3. 在含有\(n\) 个结点的二叉链表中，含有\(n+1\) 个空链域
  4. 由遍历序列构造二叉树（★★★★★）
    • 先序 + 中序（唯一确定）
      • 确定步骤
        1. 先序第一个为根，找其在中序中的位置，这个位置的左边为左子树的中序序列，右边为右子树中序序列
        2. 根据这上述两个子序列，找到在先序中的对应子序列。左子序列的第一个元素为左子树的根，右子序列的第一个元素为右子树的根。这样递归的找下去，即可
      • 举例说明：
        • 先序：A B C D E F G
        • 中序：C B E D A F G
          1. A 为根，C B E D 为左，F G 为右
          2. C B E D 在先序中为 B C D E，B 为左子树的根；B 中序分割，其左为 C，右为 E D；F G 在先序中为 F G，F 为右子树的根；F 中序分割，其左为空，其右为 G
          3. 以此类推···
    • 中序 + 后序（唯一确定）
      • 确定步骤
        1. 后序最后一个为根，找其在中序中的位置，这个位置的左边为左子树的中序序列，右边为右子树中序序列
        2. 根据这上述两个子序列，找到在后序中的对应子序列。左子序列的最后一个元素为左子树的根，右子序列的最后一个元素为右子树的根。这样递归的找下去，即可
    • 层序 + 中序（唯一确定）
      • 确定步骤
        1. 层序第一个为根，找其在中序中的位置，这个位置的左边为左子树的中序序列，右边为右子树中序序列
        2. 当上述左右子树的中序序列都非空时，层序遍历第二个为左子树的根，第三个为右子树的根；当有一个子树为空时，层序第二个为对应非空子树的根；根据根在中序中找其左右子树。以此类推，即可。
    • 先序 + 后序（不行）
      • 但可确定二叉树中结点的祖先关系：当先序序列为 XY ，后序序列为 YX 时，则 X 为 Y 的祖先。
      • 解题时，可任画一个满足的二叉树，对选项进行判断
  5. 二叉树的先序、中序、后序序列，叶子结点的先后顺序完全相同
  6. 先序遍历和中序遍历的关系：先序序列为入栈次序，中序序列为出栈次序。对于 \(n\) 个不同元素进栈，出栈序列的个数为\(\frac{1}{n+1}C_{2n}^{n}\)
  7. 线索二叉树是一种物理结构
  8. 后序线索二叉树的遍历仍需要栈的支持（★★★★★，加深对线索二叉树和二叉树遍历的理解）
    • 遍历不需要栈的关键：从当前访问的结点开始，通过左右指针，能够找到下一个结点
    • 叶子结点：其左右指针都用于线索，故一定能找到下一个结点
    • 非叶子节点：
      1. 先序情况
        1. 当前访问结点的左子树非空，下一个节点为当前左子树的根
        2. 当前访问结点的左子树为空（意味着右子树不空，否则该节点为叶子节点），下一个节点为当前右子树的根
      2. 中序情况
        • 找当前结点右子树的最左结点
      3. 后序情况
        • 一个特例：设根节点的右子树的根的左右子树非空（即根的右子树的根的两个指针域全部用于指向其左右孩子），当遍历到根结点的右子树的根时，下一个应该遍历的应该是根结点，而此时无法通过当前节点的左右指针找到该根结点，故后序线索二叉树的遍历需要栈。
  9. 在 n 个结点的树中，有n-1 条边。那么对于每棵树，其结点数比边数多一。森林中，结点数比边数多 x ，则有 x 棵树。

参考资料

  1. 数据结构（C语言版）.严蔚敏等
  2. 2020年数据结构考研复习指导.王道论坛