#3树形关系

发布于 2024-11-24  628 次阅读


一、树
（一）基本概念
树是n个结点的有限集合，表示数据元素之间的一对多的逻辑关系。特别地，当n=0时，此时是一棵空树。当n非零时，此时是一棵非空树。
在任意一棵非空树中，应当满足：
①有且仅有一个特定的被称为根的结点；
②当n>1时，其余的结点可以分为互不相交的子集，每一个子集也是一棵树，称为子树。
（二）基本属性
1、关系
父结点与孩子结点：在紧邻的一组一对多的逻辑关系中，将“一”称为父结点，“多”称为孩子结点。
祖先结点与子孙结点：在整体的一对多的逻辑关系中，将相对某一结点而言为“一”的结点称为祖先结点，将相对某一结点而言为“多”的结点称为子孙结点。
兄弟结点与堂兄弟结点：在整体的一对多的逻辑关系中，对于这一逻辑关系递归深度相同的结点而言，若有相同的父结点，则称为兄弟结点；反之称为堂兄弟结点。
结点路径与路径长度：将父结点到孩子结点的一条边称为结点间的一条路径，由某一结点到另一结点所经过的边数之和称为路径长度。
2、属性
结点的层次（深度）：从几何图形上看，是指结点位于从上向下数的第几层。
结点的高度：从几何图形上看，是指结点位于从下向上数的第几层。
树的深度（高度）：从几何图形上看，是指树的总层数。
结点的度：是指结点有几个孩子结点。
树的度：是指树中结点度的最大值。
（三）基本性质
1、结点数与总度数的关系
结点数=总度数+1
2、m度数与m叉树的区别

m度树 m叉树
任意结点的度不大于m 任意结点的度不大于m
至少有一个结点的度等于m 允许所有结点的度小于m
一定是非空树，至少有m+1个结点 可以是空树

3、度数、叉数与结点数的关系
m度树和m叉树的第i层至多有$m^{i-1}$个结点
4、高度与结点数的关系
高度为h的m叉树至多有$\frac{m^{h}-1}{m-1}$个结点
高度为h的m叉树至少有h个结点
高度为h的m度树至少有h+m-1个结点
具有n个结点的m叉树的最小高度为向上取整：$log_{m}(n(m-1)+1)$
（四）存储结构
1、双亲表示法

typedef struct{
    ElemType data;
    int parent;
}PTNode;
typedef struct{
    PTNode nodes[MaxSize];
    int n;
}PTree;

2、孩子表示法

struct CTNode{
    int child;
    struct CTNode *next;
};
typedef struct{
    ElemType data;
    struct CTNode *FirstChild;
}CTBox;
typedef struct{
    CTBox nodes[MaxSize];
    int n,r;
}CTree;

3、孩子兄弟表示法

typedef struct CSNode{
    ElemType data;
    struct CSNode *FirstChild,*NextSibling;
}CSNode,*CSTree;

（五）遍历算法
1、树的遍历
（1）先根遍历

void PreOrder(TreeNode *R){
    if(R!=NULL)
    {
        visit(R);
        while(判断R是否还有下一个子树r)
        {
            PreOrder(r);
        }
    }
}

（2）后根遍历

void PostOrder(TreeNode *R){
    if(R!=NULL)
    {
        while(判断R是否还有下一个子树r)
        {
            PostOrder(r);
        }
        visit(R);
    }
}

2、森林的遍历
（1）先序遍历
①访问第一棵树的根结点
②先序遍历第一棵树
③对其余的树重复上述步骤
（2）中序遍历
①访问第一棵树的根结点
②中序遍历第一棵树
③对其余的树重复上述步骤
二、二叉树
（一）基本概念
在树的定义上，将叉数限制为2的树，称为二叉树。
二叉树的两个孩子结点分别称为左孩子和右孩子。
（二）特殊二叉树
1、满二叉树
①只有最后一层有叶子结点
②不存在度数为1的结点
③结点i的左孩子为2i，右孩子为2i+1，父结点为向下取整i/2
2、完全二叉树
①只有最后两层可能有叶子结点
②最多只有一个度为1的结点
③结点i的左孩子为2i，右孩子为2i+1，父结点为向下取整i/2
④以向下取整n/2为界，大于该值的结点为叶子结点，小于等于该值的结点为分支结点
3、二叉排序树
按照一定的规则：
①左子树的结点的关键字小于根结点的关键字
②右子树的结点的关键字大于根结点的关键字
4、平衡二叉树
任意结点的左子树和右子树的深度之差不超过1
（三）基本性质
1、二叉树的基本性质
（1）度数与结点数的关系
设非空二叉树中度为0、1、2的结点数分别为$n_0,n_1,n_2$，则有
$n=n_0+n_1+n_2$（树的结点数=各个度的结点数之和）
$n=n_1+2n_2+1$（树的结点数=总度数+1）
$n_0=n_2+1$（两式相减）
（2）叉数与结点数的关系
二叉树的第i层至多有$2^{i-1}$个结点
（3）高度与结点数的关系
高度为h的二叉树至多有$2^h-1$个结点
2、完全二叉树的基本性质
（1）高度与结点数的关系
n个结点的完全二叉树的高度h为向上取整$log_2(n+1)$
（2）度数与结点数的关系
设完全二叉树中度为0、1、2的结点数分别为$n_0,n_1,n_2$，则有
$n_1=0或2$（完全二叉树中最多只有一个度为1的结点）
$n_0=n_2+1$（可以推出$n_0+n_2$一定为奇数）
若完全二叉树有2k个结点，则$n_0=k,n_1=1,n_2=k-1$
若完全二叉树有2k-1个结点，则$n_0=k,n_1=0,n_2=k-1$
（四）存储结构
1、顺序存储
根据结点关系，可以使用一个数组存储二叉树

struct TreeNode{
    ELemType data;//结点存储的数据
    bool IsEmpty;//结点是否为空
}//数组中存储的每一个结点的定义

TreeNode T[MaxSize];

2、链式存储

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

（五）遍历算法
1、先序遍历

void PreOrder(Bitree T){
    if(T!=NULL)
    {
        visit(T);//具体的访问函数
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

2、中序遍历

void InOrder(BiTree T){
    if(T!=NULL)
    {
        InOrder(T->lchild);
        visit(T);
        InOrder(T->rchild);
    }
}

3、后序遍历

void PostOrder(BiTree T){
    if(T!=NULL)
    {
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        visit(T);
    }
}

4、层序遍历

//定义辅助队列
typedef struct LinkNode{
    BiTreeNode *data;
    struct LinkNode *next;
}LinkNode;

typedef struct{
    LinkNode *front,*rear;
}LinkQueue;
//层序遍历
void LevelOrder(BiTree T){
    LinkQueue Q;
    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);
        }
    }
}

（六）二叉树的构造
1、前序+中序
①由前序的第一个结点确定根结点
②由根结点在中序中的位置确定左子树和右子树
③重复上述步骤
2、后序+中序
①由后序的最后一个结点确定根结点
②由根结点在中序中的位置确定左子树和右子树
③重复上述步骤
3、层次+中序
①由层次的第一个结点确定根结点
②由根结点在中序中的位置确定左子树和右子树
③由层次的后续顺序确定该层的结点
④重复上述步骤
三、应用树
（一）线索二叉树
1、存储结构

typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode *lchild,*rchild;
    int ltag,rtag;//标志位，表示指针是否为“线索”
}ThreadNode,*ThreadTree;

2、三种线索二叉树
（1）中序线索二叉树
以中序遍历的顺序，左线索指针指向前驱，右线索指针指向后继。
（2）先序线索二叉树
以先序遍历的顺序，左线索指针指向前驱，右线索指针指向后继。
（3）后序线索二叉树
以后序遍历的顺序，左线索指针指向前驱，右线索指针指向后继。
3、线索二叉树的构造
（1）中序线索化

void visit(ThreadNode *q){
    if(q->lchild==NULL)
    {
        q->lchild=pre;
        q->ltag=1;
    }
    if(pre!=NULL&&pre->rchild==NULL)
    {
        pre->rchild=q;
        pre->rtag=1;
    }
    pre=q;
}

void InThread(ThreadTree T){
    if(T!=NULL)
    {
        InThread(T->lchild);
        visit(T);
        InThread(T->rchild);
    }
}

（2）先序线索化

void visit(ThreadNode *q){
    if(q->lchild==NULL)
    {
        q->lchild=pre;
        q->ltag=1;
    }
    if(pre!=NULL&&pre->right==NULL)
    {
        pre->rchild=q;
        pre->rtag=1;
    }
    pre=q;
}

void PreThread(ThreadTree T){
    if(T!=NULL)
    {
        visit(T);
        if(T->ltag==0)
        {
            PreThread(T->lchild);
        }
        PreThread(T->rchild);
    }
}

（3）后序线索化

void visit(ThreadNode *q){
    if(q->lchild==NULL)
    {
        q->lchild=pre;
        q->ltag=1;
    }
    if(pre!=NULL&&pre->rchild==NULL)
    {
        pre->rchild=q;
        pre->rtag=1;
    }
    pre=q;
}

void PostThread(ThreadTree T){
    if(T!=NULL)
    {
        PostThread(T->lchild);
        PostThread(T->rchild);
        visit(T);
    }
}

（二）哈夫曼树
1、定义
在含有n个带权叶子结点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为哈夫曼树，也称最优二叉树。
2、构造
①选择权值最小的两个结点组合，并将其父结点权值记为两个结点权值之和
②重复上述步骤
3、哈夫曼编码
前缀编码：没有任何一个编码是另一个编码的前缀
固定长度编码：每个字符用等长的二进制位表示
可变长度编码：每个字符用可变长的二进制位表示
哈夫曼编码：将哈夫曼树的左右路径分别记为0，1.根结点到叶子结点的路径的代号组合即为一种哈夫曼编码。

学习是一段漫长的旅途