《数据结构与算法》-4-树与二叉树

该系列博客的目的是为了学习一遍数据结构中常用的概念以及常用的算法，为笔试准备；主要学习过程参考王道的《2018年-数据结构-考研复习指导》；

已总结章节：

其知识框架如下图所示：

1. 树的基本概念

1.1 树的定义

树是(N)个结点的有限集合，(N=0)表示空树；应满足：

有且仅有一个称为根的结点；
其余结点可以分成m个子集合(T_1,T_2,cdots,T_m)，其中每一个子集合也是一个树，并成为根节点的子树；

树是一种递归的数据结构，作为逻辑结构，树也是一种分层结构，有以下特点：

树中，除根节点之外，其他结点有且只有一个前驱结点；
树中，所有结点可以有0个或多个结点；
n个结点的树，有n-1条边；

1.1.2 基本术语

结点之间的关系：

祖先结点、子孙结点、双亲结点、孩子结点、兄弟结点；

其他概念：

结点的度：一个结点的子节点的个数；
树的度：树中结点的最大度数；
分支结点：度大于0的结点；
叶子结点：度等于0的结点；
结点的层次：
结点的深度：从根节点向下累加；
结点的高度：从叶节点向上累加；
树的高度（深度）：树中结点的最大层数；

有序树、无序树：

有序树：树中结点的子树从左到右是有次序的；
无序树：树中结点的子树从左到有是无次序的；

路径、路径长度：

树中两个结点之间的路径是由两个结点之间的所经过的结点序列；
路径长度指路径上经过的边的个数；

森林：

互不相交的树的集合；

1.1.3 树的性质

树中结点数等于所有结点的度加1；
度为(m)的树第(i(i geq 1))层上至多有(m^{i-1})个结点；

为什么这样说呢？要判断至多有多少结点，就假设度为(m)的树就是一颗(m)叉树，即树中每个结点都有(m)个子结点；这样的话，第一层有1个结点，第二层有(m)个结点，第三层有(m^2)个结点，所有第(i)层有(m^{i-1})个结点；

高度为h的m叉树至多有(dfrac{m^h-1}{m-1})个结点；（等比数列求和公式）

[S = 1 + m + m^2 +m^3 + m^{h-1} = dfrac{m^h-1}{m-1} ]

具有n个结点的m叉树的最小高度为(lceil log_m(n(m-1)+1) ceil)；

2. 二叉树的概念

2.1 二叉树的定义及其主要特性

2.1.1 二叉树的定义

二叉树中，每一个结点至多有两个子树；即每个结点的度不大于0；且二叉树中的子树有左右次序之分；

二叉树与度为2的树：

度为2的树至少有三个结点，二叉树可以为空；
度为2的树，没有左右子树之分；二叉树有左右子树之分；

2.1.2 几个特殊的二叉树

满二叉树：

即高度为(h)的二叉树，共有(2^h-1)个结点，称为满二叉树；即除叶子结点外，其他结点的度为2；

完全二叉树：

高度为(h)，有(n)个结点的二叉树，当且仅当其中每个结点都与高度为h的满二叉树中编号为(1~n)的结点一一对应，称为完全二叉树；

完全二叉树的性质：

若(ileq lfloor dfrac{n}{2} floor)，则(i)是分支结点，否则是叶子结点；
叶子出现在最大的两层上；最大层上的叶子结点，依次排列在左侧；
只可能存在一个度为1的结点，且该结点有左孩子，无右孩子；
按层次编号，如果出现某个结点为叶子结点，或者只有左孩子无右孩子，那么该结点之后的所有结点都是叶子结点；
若n为奇数，每个分支结点都有左孩子和右孩子；若n为偶数，编号为(dfrac{n}{2})的结点为分支节点，且该结点只有左孩子无右孩子；

二叉排序树：

左子树上所有结点的关键字都小于根节点关键字；
右子树上所有结点的关键字都大于根节点的关键字；
每个结点的左子树和右子树也是二叉排序树；

平衡二叉树：

二叉树中任一结点的左子树和右子树的深度之差不超过1；

2.1.3 二叉树的性质

非空二叉树的叶子结点数等于度为2的结点数加1，即(N_0 = N_2 + 1)；
非空二叉树的第(k)层至多有(2^{k-1}(k geq 1))个结点；
高度为(h)的二叉树，至多有(2^h-1(h geq 1))个结点；
在完全二叉树中，从上到下、从左到右结点编号为(1,2,cdots,N)；
- 当(i>1)时，双亲结点的编号为(lfloordfrac{i}{2} floor)；当(i)为奇数时，双亲结点编号(dfrac{i}{2})，是双亲结点的左孩子；当(i)为偶数时，双亲结点编号(dfrac{i-1}{2})，是双亲结点的右孩子；
- 当(2ileq N)时，结点(i)的左孩子编号(2i)，否则无左孩子；
- 当(2i+1 leq N)时，结点(i)的右孩子编号(2i+1)，否则无右孩子；
- 结点(i)所在的层次为(lfloor log_2i floor+1)；
具有(N)个结点的完全二叉树的高度为(lceil log_2(N+1) ceil或lfloor log_2 N floor +1)；

2.2 二叉树的存储结构

2.2.1 顺序存储结构

二叉树的顺序存储结构是用一组地址连续的存储单元依次从上到下、从左到右存储结点元素，并使用某种方法来指定结点之间的逻辑关系；

对于满二叉树、完全二叉树：

采用顺序存储比较适合；树中结点序号可以反应结点之间的逻辑关系；

对于一般二叉树：

添加一些不存在的空结点，从而其每个结点能够与完全二叉树上的结点相对应，进而存储到一维数组中；

2.2.2 链式存储结构

由于顺序存储的空间利用率比较低，一般使用链表来存储一颗二叉树；

二叉树中每个结点对应链表中的结点，二叉树中，结点结构通常包括若干数据域和若干指针域，二叉链表至少包括三个域：数据域data、左指针域lchild、右指针域rchild；

含有(n)个结点的二叉链表中含有(n+1)个空链域；

因此，度为1的结点空1个空指针，叶子结点有2个空指针，所有总共有：(2N_0+N_1)；又因为(N_0 = N_2 +1)，所以：

[2N_0+N_1 = N_0 + N_1 +N_0 = N_0+N_1+N_2+1 = N + 1 ]

二叉树的链式存储结构描述如下：

typedef struct BiTNde{
    ElemType data;
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

3. 二叉树的遍历和线索二叉树

有关二叉树的的遍历操作的python实现，请看：Python实现二叉树的前序、中序、后序、层次遍历；

3.1 二叉树的遍历

二叉树的遍历是指按照某种方式访问树中的每个结点；

三种遍历方式，时间复杂度和空间复杂度都是(O(n))；

前序遍历：

// 递归算法
void PreOrder(BiTree T){
    if(T != NULL){
		visit(T);
        PreOrder(T -> lchild);
        PreOrder(T -> rchild);
    }
}

// 非递归算法：借助栈
void PreOrder2(BiTree T){
    InitStack(S);
    BiTree p = T;
    while(p || !IsEmpty(S)){
        if(p){
            visit(p);
            Push(S, p);
            p = p -> lchild;
        }
        else{
            Pop(S, p);
            p = p -> rchild;
        }
    }
}

中序遍历：

// 递归算法
void InOrder(BiTree T){
    if(T != NULL){
        InOrder(T -> lchild);
        visit(T);
        InOrder(T -> rchild);
    }
}

// 非递归算法：借助栈
void InOrder2(BiTree T){
    InitStack(S);
    BiTree p = T;
    while(p || !IsEmpty(S)){
        if(p){
            Push(S, p);
            p = p -> lchild;
        }
        else{
            Pop(S, p);
            visit(p);
            p = p -> rchild;
        }
    }
}

后序遍历：

// 递归算法
void PostOrder(BiTree T){
    if(T != NULL){
        InOrder(T -> lchild);
        InOrder(T -> rchild);
        visit(T);
    }
}

// 非递归算法：借助两个栈
void PostOrder2(BiTree T){
    InitStack(S1);
    InitStack(S2);
    BiTree p = T;
    push(S1, p)
    while(!IsEmpty(S1)){
        Pop(S1, p);
        if(p -> lchild != NULL)
            Push(S1, p -> lchild);
        if(p -> rchild != NULL)
            Push(S1, p -> rchild);
        Push(S2, p)
    }
    while(!IsEmpty(S2)){
        Pop(S2, p);
        visit(p);
    }
}

层次遍历：

void LevelOrder(BiTree T){
	InitQueue(Q);
    BiTree p;
    EnQueue(Q, T);  // 根节点入队
    while(!IsEmpty(Q)){
        DeQueue(Q, p);
        visit(p);
        if(p -> lchild != NULL)
            EnQueue(Q, p -> lchild);
        if(p -> rchild != NULL)
            EnQueue(Q, p -> rchild);
    }
}

由遍历序列构造二叉树：

由先序遍历和中序遍历可以唯一确定一颗二叉树；
由后序遍历和中序遍历可以唯一确定一颗二叉树；

3.2 线索二叉树

3.2.1 基本概念

上一节中提到的各种遍历，其实质都是将非线性结构进行线性化的操作；

利用二叉链表构造线索二叉树；其中lchild指向左子树或者前驱结点；rchild指向右子树或者后继结点；

线索二叉树的存储结构描述：

typedef struct ThreadNode{
	ElemType data;						// 数据元素
    struct ThreadNode *lchild, rchild;	// 左、右孩子指针
    int ltag, rtag;						// 左、右线索标志
}ThreadNode, *ThreadTree;

线索链表：以这种结点结构构成的二叉链表作为二叉树的存储结构；
线索：其中指向结点前驱和后继的指针；
加上线索的二叉树称为线索二叉树；
以某种次序遍历二叉树使其变为线索二叉树的过程称为线索化；

3.2.2 线索二叉树的构造

线索二叉树的构造就是在遍历二叉树的时候，检查当前结点左、右指针是否为空，若为空，将它们改为指向该结点的前驱结点后者后继结点。

（本想用python实现构造线索二叉树，最终把自己都搞懵了....）

通过中序遍历队二叉树线索化的递归算法：

void InThread(ThreadTree &p,ThreadTree &pre){
    if(p!=NULL){
        InThread(p->lchild,pre);                //递归，线索化左子树
        if(p->lchild==NULL){                   //左子树为空，建立前驱线索
            p->lchild=pre;
            p->tag=1;
        }
        if(pre!=NULL&&pre->rchild==NULL){
            pre->rchild=p;                    //建立前驱结点的后继线索
            pre->rtag=1;
        }
        pre=p;                               //标记当前结点成为刚刚访问过的结点
        InThread(p->rchild,pre)             //递归，线索化右子树
    }
}

void CreateInThread(ThreadTree T){
    ThreadTree pre=NULL;
    if(T!=NULL){            //非空二叉树，线索化
        InThread(T,pre);   //线索化二叉树
        pre->rchild=NULL;  //处理遍历的最后一个结点
        pre->rtag=1;
    }
}

3.2.3 线索二叉树的遍历

中序线索二叉树主要是为访问运算服务的，利用线索二叉树，可以实现二叉树遍历的非递归实现，同时不需要借助栈和队列，因为结点已经包含有前驱和后继信息。