数据结构与算法树

一、树的定义

树(Tree)是n(n>=0)个节点的有限集。当n=0时成为空树，在任意一棵非空树中：

有且仅有一个特定的称为根(Root)的节点
当n>1时，其余节点可分为m(m>0)个互不相交的有限集T1 T2 T3 … Tm，其中每个集合本身又是一棵树，并且称为根的子树(SubTree)。

二、节点分类

节点拥有的子树数称为节点的度(Degree)，树的度取树内各节点的度的最大值。

度为0的节点称为叶节点或终端节点
度不为0的节点称为分支节点或非终端节点，除根节点外，分支节点也称为内部节点。

节点之间的关系

节点的子树的根称为节点的孩子(Child)，相应的，该节点称为孩子的双亲(Parent)，同一双亲的孩子之间互称为兄弟(Sibling)。

节点的祖先是从根到该节点所经分支上的所有节点。

节点的层次

节点的层次(level)从根开始起，根为第一层，根的孩子为第二层。

其双亲在同一层的节点互为堂兄弟。

树中节点的最大层次称为树的深度(depth)或高度。

其他概念

如果将树中节点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。

三、树的存储结构

说到存储结构，就会想到我们前面章节讲过的顺序存储和链式存储两种基本结构。

对于线性表来说，很直观就可以理解，但对于树这种一对多的结构，我们应该怎么办呢？

要存储树，简单的顺序存储结构和链式存储结构是不能的。不过如果充分利用他们各自的特点，完全可以间接地来实现。

这里要介绍三种不同的表示法：双亲表示法、孩子表示法、孩子兄弟表示法。

双亲表示法

双亲表示法，言外之意就是以双亲作为索引的关键词的一种存储方式。

我们假设以一组连续空间存储树的节点，同时在每个节点中，附设一个指示其双亲节点在数组中位置的元素。

也就是说，每个节点除了知道自己是谁之外，还知道他的双亲在哪。

//树的双亲表示节点结构定义

#define MAX_TREE_SIZE 100

typedef int ElemType;

typedef struct PTNode{
    ElemType data;//节点数据
    int parent;//双亲位置
}PTNode;

typedef struct{
    PTNode nodes[MAX_TREE_SIZE];
    int r;//根的位置
    int n;//节点数目·
}PTree

这样的存储结构，我们可以根据某节点的parent指针找到他的双亲节点，所用的时间复杂度是O(1)，索引到parent的值为-1时，表示找到了树节点的根。

可是，如果我们要知道某个节点的孩子是什么？那么需要遍历整个树结构。

这真的麻烦，能不能改进以下呢？我们只需稍微改变以下结构即可：

那现在我们又比较关心他们兄弟之间的关系呢？

孩子表示法

我们这次换个角度来考虑，由于树中每个节点可能有多棵子树，可以考虑用多重链表来实现。

双亲孩子表示法

那只找好孩子找不到双亲貌似还不够完善，那么我们合并上一讲的双亲孩子表示法：

parent_child.c

#define MAX_TREE_SIZE = 100
typedef char ElemType;
//孩子节点
typedef struct CTNode{
    int child;/孩子节点的下标
    struct CTNode *next;//指向下一个孩子节点的指针
} *ChildPtr;

//表头结构
typedef struct{
    ElemType Data;//存放在树中的节点的数据
    int parent;//存放双亲的下标
    ChildPtr firstchild;//指向 第一个孩子的指针
}CTBox;

//树结构
typedef struct{
    CTBox node[MAX_TREE_SIZE];//节点数组
    int r,n;
};

四、二叉树

因为二叉树使用范围最广，最具有代表意义，因此我们重点讨论二叉树。

二叉树(Binery Tree)是n（n>=0）个节点的有限集合，该集合或者为空集（空二叉树），或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。

二叉树的特点

每个节点最多有两棵子树，所以二叉树中不存在度大于2的节点。（注意：不是都需要两棵子树，而是最多可以是两棵，没有子树或者有一棵子树也都是可以的。）

左子树和右子树是由顺序的，次序不能颠倒。

即使树中某节点只有一棵子树，也要区分它是左子树还是右子树，下面是完全不同的二叉树：

二叉树的五种基本形态

空二叉树
只有一个根节点
根节点只有左子树
根节点只有右子树
根节点既有左子树又有右子树

特殊二叉树

斜树要么往左斜，要么往右斜
满二叉树在一棵二叉树中，如果所有分支节点都存在左子树和右子树，并且所有叶子都在同一层，这样的二叉树称为满二叉树。
完全二叉树对一棵具有n个节点的二叉树按层序编号，如果编号为i(1<=i<=n)的节点与同样深度的满二叉树中编号为i的节点位置完全相同，则这棵二叉树称为完全二叉树。

二叉树的性质

在二叉树的第i层上至多有2^(i-1)个节点(i>=1)

深度为k的二叉树至多有2^k-1个节点

对任何一棵二叉树T，如果其终端节点数为n0，度为2的节点数为n2则n0 = n2+1

具有n个节点的完全二叉树的深度为[log2 n]+1

如果对一棵有n个节点的完全二叉树（其深度为[log2 n] +1）的节点按层序编号，对任一节点i(1<=i<=n)有以下性质：

二叉树的存储结构

二叉树是一种特殊的树，由于他的特殊性，使得用顺序存储结构或链式存储结构都能简单实现。

二叉树的顺序存储结构就是用一维数组存储二叉树中的各个节点，并且节点的存储位置能体现节点之间的逻辑关系。

这下看出完全二叉树的优越性了吧，由于他的严格定义，在数组直接能表现出逻辑。

当然对于一般的二叉树，尽管层序编号不能反映逻辑关系，但是也可以按照完全二叉树编号方式修改一下，把不存在的节点用^代替即可。

但是考虑到一种极端的情况，回顾一下斜树，如果是一个右斜树，那么会变成这样

既然顺序存储方式的适用性不强，那么我们就要考虑链式存储结构了。二叉树的存储按照国际惯例来说一般也是采用链式存储结构的。

二叉树的每个节点最多有两个孩子，所以为它设计一个数据域和两个指针域是比较自然的想法，我们称这样的链表叫做二叉链表。

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

五、二叉树的遍历

二叉树的遍历(traversing binery tree)是指从根节点出发，按照某种次序依次访问二叉树中所有节点，使得每个节点被访问一次且仅被访问一次。

二叉树的遍历次序不同于线性结构，线性结构最多也就是分为顺序、循环、双向等简单的遍历方式。

树的节点之间不存在唯一的前驱和后继这样的关系，在访问一个节点后，下一个被访问的节点面临着不同的选择。

二叉树的遍历方式可以很多，如果我们限制了从左到右的习惯方式，那么主要就分为以下四种：

第一种：前序遍历
若二叉树为空，则空操作返回，否则先访问根节点，然后前序遍历左子树，再前序遍历右子树。
第二种：中序遍历
若树为空，则空操作返回，否则从根节点开始（注意并不是先访问根节点），中序遍历根节点的左子树，然后是访问根节点，最后中序遍历右子树。
第三种：后序遍历
若树为空，则空操作返回，否则从左到右先叶子后节点的方式遍历访问左右子树，最后访问根节点。
第四种：层序遍历若树为空，则空操作返回，否则从树的第一层，也就是根节点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对节点逐个访问。

六、二叉树的建立和遍历算法

题目要求：建立二叉树并输出每个字符所在的层数。如图：

#include<stdio.h>
#include<stdlib.h>

typedef char ElemType;

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


//创建一棵二叉树,约定用户遵照前序遍历的方式输入数据
void createBiTree(BiTree *T){
    char c;
    scanf("%c",&c);
    
    if(' ' == c){//说明此子树不存在
        *T = NULL;
    }else{
        *T = (BiTNode *)malloc(sizeof(BiTNode));
        (*T)->data = c;
        createBiTree(&(*T)->lchild);//左子树
        createBiTree(&(*T)->rchild);//右子树
    }
}

//访问二叉树节点的具体操作
void visit(ElemType c,int level){
    printf("%c位于第%d层
",c,level);
}
//遍历二叉树
void PreOrderTraverse(BiTree T,int level){
    if(T){
        visit(T->data,level);
        PreOrderTraverse(T->lchild,level+1);
        PreOrderTraverse(T->rchild,level+1);
    }
}

int main(){
    int level = 1;
    BiTree T = NULL;
    
    createBiTree(&T);
    
    PreOrderTraverse(T,level);
    return 0;
}

七、线索二叉树

为什么需要线索二叉树呢？

我想正如程序员发觉单链表并不总能满足他们设计的程序某些要求的时候，发明了双向链表来弥补一样，线索二叉树也是在需求中被创造的！

那普通二叉树到底有什么缺陷让我们发指呢？

主要是浪费时间和空间

八、树、森林及二叉树的相互转换

从一棵普通的树开始介绍，在满足树的条件下可以是任意状态，一个节点可以有任意多个孩子，这样对树处理显得要复杂很多。

所以我们研究除了一些条条框框的限定，如：二叉树，完全二叉树，满二叉树等。

那么这时候你就会想，如果所有的树都像二叉树一样方便处理就好了。

普通树转换为二叉树

步骤如下：

在树中所有的兄弟节点之间加一连线
对每个节点，除了保留与其长子的连线外，去掉该节点与其他孩子的连线

森林到二叉树的转换

先将森林中的每一棵树变为二叉树（方法同上）
再将各二叉树的根节点视为兄弟从左至右连在一起。

二叉树到树、森林的转换

若节点x是其双亲的左孩子，则把x的的右孩子，右孩子的右孩子,…，都与y用线连起来。
去掉所有双亲到右孩子之间的连线

树与森林的遍历

树的遍历分为两种方式：一种是先根遍历，另一种是后根遍历。

先根遍历：先访问树的根节点，然后再依次先根遍历根的每一棵子树。

后根遍历：先依次遍历每棵子树，然后再访问根节点。

森林的遍历也分为前序遍历和后序遍历，其实就是按照树的先根遍历和后根遍历依次访问森林的每一个树。

我们惊人的发现：树、森林的前根（序）遍历和二叉树的前序遍历结果相同，树、森林的后根（序）遍历和二叉树的终须遍历结果相同

本文摘自：https://blog.51cto.com/u

数据结构与算法 树2022-04-25 22:54:29