数据结构(五)树和二叉树

作者: AdRainty | 来源:发表于2021-08-22 00:48 被阅读0次

5.1 树的基本概念

5.1.1 树的定义

树是 $n(n \ge 0)$ 个结点的有限集，当n=0称为空树。任意一颗非空树

1)有且仅有一个特定的称为根的结点

2)当 $n>1$ 时，其余结点可分为 $m(m>0)$ 个互不相交的有限集，其中每个集合本身又是一颗树，并且称为根的子树。

①树的根结点没有前驱，除了根结点外所有结点有且仅有一个前驱

②树中所有结点可以有零个或多个后继

在n个结点中的树中有n-1条边

树

树中一个结点的孩子个数称为该结点的度
度大于0的结点称为分支结点，度为0的结点称为叶子结点
森林是 $m(m \ge 0)$ 颗互不相交的树的集合

5.1.2 树的性质

①结点树=度数+1

②度为m的树第i层至多有 $m^{i-1}$ 个结点

③高度为h的树至多有 $(m^h-1)/(m-1)$ 个结点

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

⑤具有n个结点的m叉树的最小高度为 $\lceil log_m{(n(m-1)+1)} \rceil$

5.2 二叉树

5.2.1 二叉树的概念

二叉树是一种特殊的树，每个结点至多只有两颗子树

二叉树与度为2的有序树的区别：

①度为2的树至少有3个结点，而二叉树可以为空

②度为2的有序树孩子左右次序可以无序区分

5.2.2 几个特俗的二叉树

5.2.2.1 满二叉树

树中每层都含有最多的结点；对于编号为i的结点，若有双亲，则其双亲为 $\lfloor i/2 \rfloor$ ，若有左孩子，则左孩子为2i，若有右孩子，右孩子为2i+1。

5.2.2.2 完全二叉树

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

①若 $i \le \lfloor n/2 \rfloor$ ，则结点i为分支结点，否则为叶子结点

②叶子结点只可能在最大两层上出现，对于最大层叶子结点，都一次排列在该层最左边的位置上

③若有度为1的结点，则只可能有1个，且该节点只有左孩子没有右孩子

④一旦出现某结点为叶子结点或只有左孩子，则编号大于i的结点均为叶子结点

⑤若n为奇数，则每个分支结点都有左孩子和右孩子，若n为偶数，则编号最大的分支结点(n/2)只有左孩子没有右孩子，其余分支结点左右孩子都有

满二叉树和完全二叉树

5.2.2.3 二叉排序树

左子树上所有结点关键字均小于根结点关键字，右子树上的所有结点均大于根节点的关键字；左子树和右子树又各是一颗二叉排序树

5.2.3 二叉树的性质

①非空二叉树上的叶子结点树等于度为2的结点数+1

②非空二叉树上的第k层上至多有 $2^{k-1}(k \ge 1)$ 个结点

③高度为h的二叉树至多有 $2^{h}-1$ 个结点

④对完全二叉树按从上到下，从左到右的顺序编号1~n，则

当 $i > 1$ ，结点i双亲 $\lfloor i/2\rfloor$
当 $2i<n$ 时结点i的左孩子编号为2i，否则无左孩子
当 $2i+1 \le n$ 时，结点i右孩子编号为2i+1，否则无右孩子
结点i的所在层次(深度)为 $\lfloor log_2i +1 \rfloor$
具有n个结点的完全二叉树高度为 $\lceil log_2(n+1) \rceil$ 或 $\lfloor log_2n \rfloor +1$

5.3 二叉树的存储结构

二叉树分为顺序存储和链式存储，但由于顺序存储空间利用率较低，因此二叉树存储一半都采用链式存储结构，用链表来存储二叉树中每个结点

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

在含有n个结点的二叉链表中，含有n+1个空链域

5.4 二叉树的遍历

遍历二叉树要决定对根节点N，左子树L和右子树R的访问顺序，常见的有先序(NLR)、中序(LNR)和后序(LRN)三种遍历方式

5.4.1 先序遍历

void PreOrder(BiTree T){
    if (T!=NULL){
        visit(T);  //访问根节点
        PreOrder(T->lchild); //递归遍历左子树
        PreOrder(T->rchild); //递归遍历右子树
    }
}

5.4.2 中序遍历

void InOrder(BiTree T){
    if (T!=NULL){
        InOrder(T->lchild); //递归遍历左子树
        visit(T);  //访问根节点
        InOrder(T->rchild); //递归遍历右子树
    }
}

5.4.3 后序遍历

void PostOrder(BiTree T){
    if (T!=NULL){
        PostOrder(T->lchild); //递归遍历左子树
        PostOrder(T->rchild); //递归遍历右子树
        visit(T);  //访问根节点
    }
}

5.4.4 层次遍历

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);
    }
}

只有中序遍历和其他任意一个遍历才可以唯一确定一颗二叉树

5.5 线索二叉树

在含有n个结点二叉树中，有n+1个空指针，为了利用这些空指针，引入线索二叉树

规定：若无左子树，令lchild指向其前驱结点，若无右子树，令rchild指向其后继结点，并增加两个标志域标识指针域是指向其左右孩子还是前驱后继

typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;
}ThreadNode, *ThreadTree;

5.5.1 中序线索二叉树的遍历

void InThread(ThreadTree &p, ThreadTree &pre){
    if(p!=NULL){
        InThread(p->lchild, pre);
        if(p->lchild==NULL){
            p->lchild=pre;
            p->ltag=1;
        }
        if(pre!=NULL&&pre->rchild!=NULL){
            pre->rchild=p;
            pre->rtag=1;
        }
        pre=p;
        InThread(p->rchild,pre);
    }
}

5.6 树和森林

5.6.1 树的存储结构

双亲表示法：每个结点中保存指向双亲的“指针”

#define MAX_TREE_SIZE 100 // 最多结点数
typedef struct{
    ElemType data;
    int parent; //双亲位置域
}PTNode;
typedef struct{
    PTNode nodes[MAX_TREE_SIZE];  //双亲表示
    int n;  //结点数
}PTree;

孩子表示法：顺序存储各个节点，每个结点中保存孩子链表头指针

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

孩子兄弟法：有两个指针，分别指向第一个孩子的结点和下一个兄弟结点

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

5.7 树与二叉树应用

5.7.1 二叉排序树

二叉排序树的查找

BSTNode *BST_Search(BiTree T, ElemType key){
    while(T!=NULL&&key!=T->data){
        if(key<T->data) T=T->lchild;
        else T=T->rchild;
    }
    return T;
}

二叉排序树的插入

int BST_Insert(BiTree &T,ElemType k){
    if(T==NULL){
        T=(BiTree)malloc(sizeof(BSTNode));
        T->key=k;
        T->lchild=T->rchild=NULL;
        return 1;
    }
    else if (k==T->key)return 0;
    else if (k<T->key) return BST_Insert(T-lchild, k);
    else return BST_Insert(T-rchild, k);
}

5.7.2 平衡二叉树

任意结点左右子树高度差不超过1的树称为平衡二叉树

调整平衡二叉树问题分成四类：LL、RR、LR、RL

LL指的是A结点左孩子的左子树插入新的结点导致失衡，解决办法一般是进行一次右旋操作
RR指的是A结点的右孩子的右子树插入新结点，导致失去平衡；这时我们会对A结点左旋
LR指的是结点A的左孩子的右子树上插入新的结点导致失衡，需要先左旋再右旋
RL指的是A结点的右孩子的左子树上插入新结点，导致二叉树不平衡，，这时需要先右旋再左旋

①设n(h)表示深度为h的平衡二叉树最少结点数，则
$n(h)=\left\{ \begin{array}{l} 0,h=0\\ 1,h=1\\ n(h-1)+n(h-2)+1,h\ge1\\ \end{array} \right.$

5.7.3 哈夫曼树

树中所有叶结点带权路径长度之和称为该树的带权路径长度
$WPL=\sum_{i=1}^n{w_il_i}$
在含有n个带权叶结点二叉树中，WPL最小的树称为哈夫曼树

哈夫曼树.png