06树

1.树的定义

树(Tree)：树是n(n >= 0)个结点的有限集。当n = 0时称为空树。在任意一颗非空树中，（1）:有且仅有一个特定的称为根（root）的结点。（2）当n > 1时，其余结点可分为m（m > 0）个互不相交的有限集T1，T2...Tm，其中每个集合又是一棵树，称为根的子树。一棵树如图：

tree.png

堂兄弟与兄弟的区别：堂兄弟：其双亲在同一层的结点互为堂兄弟。兄弟：同一个双亲的孩子之间称为兄弟。兄弟是比堂兄弟更亲密的关系。

2.树的存储结构

1.前言

既然具有线性结构这种逻辑结构的线性表具有顺序存储结构和链式存储结构，那么我们也会想到对于树这种一对多的结构呢？树中某个节点的孩子可以有多个，所以无论按照何总顺序将树中所有结点存储到数组中，结点的存储位置都不能直接反映逻辑关系。简单的顺序存储结构是不能满足树的实现要求的。这里介绍三种树的存储结构表示方法：双亲表示法，孩子表示法，孩子兄弟表示法。

2.双亲表示法

以一组连续空间（数组）存储树的结点，同时在每个节点中附设一个整形的指针指示其双亲结点在数组中的下标位置。如图：

双亲表示法.png

双亲表示法实现树结构的简单定义如下：

#pragma once
#define ElemType int 
#define MAXSIZE 10

//树的双亲表示法的结点结构定义
typedef struct Node
{
    int parent;     //指示某个结点的双亲结点在数组中的位置下标
    ElemType data;  //结点数据
}Node;

//树结构
typedef struct Tree
{
    Node node[MAXSIZE];     //结点数组
    int rootPos, nodeNumber;//根的位置和结点的数量
}Tree;

上述定义中的数组是定长的，下面的定义是不定长存储结构的定义：

#pragma once
#define ElemType int 

//树的双亲表示法的结点结构定义
typedef struct Node
{
    int parent;     //指示某个结点的双亲结点在数组中的位置下标
    ElemType data;  //结点数据
}Node;

//树结构
typedef struct Tree
{
    Node* data;                      //结点数据
    int rootPos, nodeNumber;//根的位置和结点的数量
}Tree;

这样的存储结构的优缺点：优点是：可以根据某个结点的parent指针快速找到该节点的双亲结点，时间复杂度为O(1).缺点是：因为结点没有存储孩子结点的信息，所以不能快速找到该节点的孩子节点。遍历整个结构才行

改进：
1.当我们还需要快速找到一个结点的孩子结点时，就可以在上述的结点结构体另外附设一个整形指针指示第一个孩子结点在数组中的位置下标。如图：

改进一.png

2.当我们关注一个结点的兄弟节点的信息时，就可以在上述的结点结构体另外附设一个整形指针指示第一个兄弟结点在数组中的位置下标。如图：

改进二.png

显然，存储结构的设计是一个很灵活的过程。得需要根据需求设计合适得存储结构

3.孩子表示法

由于树中每个结点可能有多颗子树，可以考虑用多重链表。即每个结点有多个指针域，其中每个指针指向子树得根节点，这种方法叫做多重链表表示法。

设计方案一：将每个结点得指针域数量设为恒定值，即为树的度（各个结点度得最大值）。这样做得优缺点：优点是：当树得各节点度相差不大时，相比于方案二就可以不必附设指明指针域数量得信息，开辟得空间被充分利用。缺点是：树中各节点得度相差较大时，就会有的结点得指针域为空，显然浪费了存储空间。可如图表示：

方案一.png

设计方案二：按需分配指针域得空间，也就是说每个结点得指针域得数量是不一样的。因此我们在每个节点中附设一个计数器来存储指针域得个数（即为某个结点得孩子结点得个数）。这样做的优缺点：优点是：克服了空间浪费得缺点。缺点是：链表得各个结点结构不同，运算上带来时间得损耗，需要维护结点得计数器.可如图表示：

方案二.png

*能否有更好的方法既可以减少空指针得浪费，又能使得结点结构相同呢？树中每个结点得孩子是不确定的，所以我们再对每个节点中的孩子建立一个单链表来体现他们得关系。这就是孩子表示法。方法具体是：将每个结点得孩子结点以单链表为存储结构存储起来，则n个结点有n个单链表，因叶子节点没有孩子结点则此单链表为空。然后n个头指针（指向单链表得第一个数据结点）又组成一个线性表，采用线性存储结构存储到一维数组中。如图：

孩子表示法.png

孩子表示法的结构体定义：

#define ElemType int
#define MAXSIZE 10

//表示孩子结点的单链表结构体
typedef struct ChildNode
{
    int child;              //结点的数据域存储当前孩子结点在表头数组中的位置下标
    struct ChildNode* next; //指针域存储指向下一个孩子结点的地址
}ChildNode;

//表示表头数组的表头结点的结构体
typedef struct 
{
    ElemType data;          //树中结点的数据
    ChildNode* headPointer; //头指针指向第一个孩子结点
}HeadArrayNode;

//表示树结构的结构体
typedef struct
{
    HeadArrayNode node[MAXSIZE];//树中结点数组
    int rootPos, nodeNumber;    //根的位置和结点的数量
}Tree;

当然孩子表示法选择不定长结构时只需修改树中的结点数组，这样即使堆上分配的容量不足时扩容也方便：

HeadArrayNode * node;

孩子表示法的优缺点：优点是：可以快速找到某个结点的孩子节点或者兄弟节点。缺点是：如何不通过遍历树快速知道某个结点的双亲结点呢？于是我们将双亲表示法和孩子表示法结合一下：如图：

双亲孩子表示法.png

4.孩子兄弟表示法

孩子兄弟表示法即为：在一个节点中含有两个指针域，一个指针域存储一个结点的第一个孩子，另一个指针域存储一个节点的右兄弟。可如图表示

孩子兄弟表示法.png
树的孩子兄弟法结构体定义如下：

#pragma once
#define ElemType int

//结点结构
typedef struct CSNode
{
    ElemType data;
    struct CSNode* firstChild, * rightSib;
}CSNode;

typedef struct
{
    CSNode* node;
    int rootPos, nodeNumber;//根的位置和结点的数量
}Tree;

此方法的优缺点：优点是：可以将一棵树转化为二叉树。缺点是：如果要寻找某个结点的双亲，这种表示法也是有缺点的。因此我们还可以增加一个指针域存储指向某个结点的双亲结点。

总而言之，树的存储结构是围绕着当前结点，当前节点的孩子节点，当前结点的兄弟节点三者之间的关联来灵活设计的。关注的结点不同，自然存储结构的实现方法也不一样。

3.二叉树

1.二叉树的定义

二叉树（BinaryTree）的定义：二叉树是n（n >= 0）个结点的有限集合，当n为0时称为空二叉树，或者由一个根节点和两颗互不相交的，分别称为根节点的左子树和右子树的二叉树组成。二叉树一节中概念术语较多，就不一一列举。比如说二叉树的特点（二叉树的五种形态），特殊二叉树（斜树，满二叉树，完全二叉树），二叉树的五条性质,二叉树的四种遍历方法概念（先序遍历，中序遍历，后序遍历，层次遍历），遍历结果的推导。

2.二叉树的顺序存储结构

二叉树的顺序存储结构：
前面谈到树的存储结构，并说到顺序存储结构对树这种一对多的关系实现起来是困难的。但是二叉树是一种特殊的二叉树，由于它的特殊性使得用顺序存储结构也可以实现。二叉树的存储结构是用一维数组存储二叉树的结点，并且数组的下标（结点的存储位置）能体现节点之间的逻辑关系。

先看完全二叉树的顺序存储，一颗二叉树如图：

完全二叉树.png

按标号将二叉树存入数组中，相应的下标对应同样的位置，如图：

完全二叉树顺序存储示意图.png
对于一般的二叉树，为了使数组的下标能体现结点之间的逻辑关系，我们对二叉树的结点也按照完全二叉树编号。把不存在的结点用一个特殊符号标记一颗一般二叉树如图，浅色结点表示不存在：
一般二叉树.png
按标号将二叉树存入数组中，相应的下标对应同样的位置，如图：
一般二叉树顺序存储示意图.png
显然，数组中就有四个结点空间的大小被浪费。考虑一颗深度为K的右斜树，有k个结点，却在数组中要分配2的k次方减一个存储单元空间，这显然浪费了很多空间。所以顺序存储结构来实现二叉树一般只针对完全二叉树，缺点是对于一般的二叉树来说会造成空间的极大浪费。

3.二叉树的链式存储结构

二叉树的链式存储结构：在用链式存储结构实现二叉树时，因为二叉树每个节点最多有两个孩子。所以我们为二叉树的结点设计一个数据域和两个指针域（分别指向孩子结点），这样的链表称为二叉链表。
任意一个结点结构如图：

结点结构示意图.png

二叉链表的结构体定义：

#pragma once
#define ElemType int

//结点结构
typedef struct BiTreeNode
{
    ElemType data;
    struct BiTreeNode* lChild;  //指向左孩子的指针
    struct BiTreeNode* rChild;  //指向右孩子的指针
}BiTreeNode,*BiTree;

二叉链表的遍历：

//递归遍历二叉树应当理解递归的思想
//前序遍历
void preOrderTraverse(BiTree root)
{
    if (root == nullptr)
    {
        return;
    }
    printf("%d\t",root->data);
    preOrderTraverse(root->lChild);
    preOrderTraverse(root->rChild);
}

//中序遍历
void inOrderTraverse(BiTree root)
{
    if (root == nullptr)
    {
        return;
    }
    inOrderTraverse(root->lChild);
    printf("%d\t", root->data);
    inOrderTraverse(root->rChild);
}

//后续遍历
void postOrderTraverse(BiTree root)
{
    if (root == nullptr)
    {
        return;
    }
    postOrderTraverse(root->lChild);
    postOrderTraverse(root->rChild);
    printf("%d\t", root->data);
}

二叉链表结构如图：

二叉树链式存储结构的示意图.png
如果有需求还可以增加一个指向双亲的指针域，叫做三叉链表。

4.二叉树的创建

#号法创建二叉树：即让二叉树的结点的度都为2,也就是让二叉树每个节点的空指针引出一特定值。比如下图所示：

扩展二叉树.png
我们用前序遍历输入上述二叉树结点的值：AB#D##C##，构建一颗二叉树如下：

//#号法创建一颗二叉树
BiTree createBiTree()
{
    BiTreeNode* temp = nullptr;
    char temp1;
    scanf("%c",&temp1); //按照前序输入二叉树结点的值
    getchar();
    if (temp1 == '#')
    {
        return nullptr;
    }
    else
    {
        temp = (BiTreeNode*)malloc(sizeof(BiTreeNode));
        assert(temp != nullptr);
        temp->data = temp1;

        //创建左子树
        temp->lChild = createBiTree();
        //创建右子树
        temp->rChild = createBiTree();

        return temp;
    }
}

5.线索二叉树

在二叉链表中，我们发现有很多空指针域的存在，浪费了一些存储空间。对于一个有n个结点的二叉链表，共有2n个指针域，有效指针域为n-1个，所以就有2n-（n-1）= n+1个指针域浪费了空间。并且再二叉链表中，我们需要知道一个结点的前驱结点和后继节点时只有通过遍历二叉树才能得到，这样很耗时间。有没有更快的方法呢？于是我们想到利用空指针域，存放当前结点在某种遍历次序下的的前驱结点和后继节点的地址。问题又来了，如何区分一个结点中的lChild指针域指向前驱结点或者左孩子呢？还有一个结点中的rChild指针域指向后继节点还是右孩子呢？于是我们在一个节点结构中再增加两个标志域(区分标记)ltag,rlag（bool类型变量）。

我们把这种指向前驱结点和后继节点的指针叫做线索，加上线索的链表叫做线索链表，相应的二叉树称为线索二叉树（Threaded Binary Tree）。

线索化：对二叉树以某种次序遍历使其变成线索二叉树的过程。由于前驱和后继的信息只有在遍历二叉树的时候才能得到，所以线索化的过程就是再遍历的过程中修改空指针的过程。
结点结构如下：

线索二叉链表链表的结点结构.png
ltag为0时指向左孩子，为1时指向前驱结点；rtag为0时指向右孩子，为1时指向后继结点。
一颗线索二叉链表如图所示（可以看到与二叉链表的明显不同）：
线索二叉链表.png

*简单实现一颗线索二叉树如下：

#pragma once
#ifndef _THREADBITREE_H
#define _THREADBITREE_H

/*
*   @brief 线索二叉链表的简单实现
*/

typedef char ElemType;

//LINK为0表示线索二叉链表中某个节点的左右孩子指针指向左右孩子
//THREAD为1表示线索二叉链表中某个节点的左右孩子指针指向前驱结点后继节点
enum class PointerTag
{
    LINK = 0,
    THREAD = 1
};

typedef struct BiThrNode
{
    ElemType data;              //结点数据
    PointerTag ltag, rtag;      //一个结点的左右指针标志
    struct BiThrNode* lChild;   //左孩子指针
    struct BiThrNode* rChild;   //右孩子指针
}BiThrNode,*BiThrTree;

//#号法创建二叉链表树
BiThrNode* createTree();

//中序遍历线索化二叉树
void inThreading(BiThrNode* root);

//中序遍历线索二叉链表树
void inOrderTraverseBiThrTree(BiThrNode* root);

#endif

#include "ThreadBiTree.h"
#include <cstdio>
#include <cassert>
#include <cstdlib>
#include <iostream>

//#号法创建二叉链表树
BiThrNode* createTree()
{
    BiThrNode* newNode = nullptr;
    //这里我们按照先序遍历输入我们要创建的一颗二叉树的值
    char temp;
    printf("请输入先序遍历中的值：");
    scanf("%c",&temp);
    getchar();
    if (temp == '#')
    {
        return nullptr; //这是退出递归的必要条件
    }
    newNode = (BiThrNode*)malloc(sizeof(BiThrNode));
    assert(newNode != nullptr);
    newNode->data = temp;
    newNode->ltag = newNode->rtag = PointerTag::LINK;   //默认值为0

    newNode->lChild = createTree();
    newNode->rChild = createTree();

    return newNode;
}



//中序遍历线索化二叉树
BiThrNode* pre2 = nullptr;  //始终指向刚刚访问过的结点
void inThreading(BiThrNode* root)
{

    if (root == nullptr)
    {
        return;
    }
    inThreading(root->lChild);

    //如果访问到的某个结点没有左孩子，就将左指针域线索化
    if (root->lChild == nullptr)
    {
        root->ltag = PointerTag::THREAD;
        root->lChild = pre2;    //指向前驱
    }
    //如果刚刚访问到的结点pre没有右孩子，就把其右孩子指针域线索化指向当前访问到的结点（后继结点）
    if (pre2 != nullptr && pre2->rChild == nullptr )
    {
        pre2->rtag = PointerTag::THREAD;
        pre2->rChild = root;
    }
    pre2 = root;    //让pre指向当前访问的结点

    inThreading(root->rChild);
}


//中序遍历线索二叉链表树，有些书中也会利用头结点来遍历
void inOrderTraverseBiThrTree(BiThrNode* root)
{

    BiThrNode* workNode = root; //根节点

    while (workNode != nullptr)
    {
        //当ltag为1时表示到了中序遍历的第一个结点
        while (workNode->ltag == PointerTag::LINK)
        {
            workNode = workNode->lChild;
        }
        //访问该结点的值
        printf("%c\t",workNode->data);

        while (workNode->rtag == PointerTag::THREAD && workNode->rChild != nullptr)
        {
            workNode = workNode->rChild;
            printf("%c\t", workNode->data);

        }
        workNode = workNode->rChild;
    }

}

测试程序如下：

#include <iostream>
#include "ThreadBiTree.h"

int main()
{
    BiThrNode* node = nullptr;
    //创建一颗二叉链表树
    node = createTree();
    std::cout << std::endl;

    //中序线索化
    inThreading(node);
    //中序遍历该线索二叉链表树
    inOrderTraverseBiThrTree(node);
    //线索化后不能再递归遍历
    //preOrderTraverse(node);
    return 0;
}

按照下图前序遍历输入待chua构建二叉树的值，可得结果为：

扩展二叉树.png

线索二叉树充分利用了空指针域的空间（节省了空间）,有保证创建时的一次遍历就可以利用前驱后继的信息。（节省了时间）如果所用的二叉树需要经常遍历或者查找某个节点需要某种遍历次序中的前驱或者后继，那么采用线索二叉树为宜。

4.树，深林，二叉树的转化（概念不详诉）

1.树转二叉树：前面提过，在树的存储结构中，孩子兄弟法可以将一棵树转化为二叉树。利用的就是二叉链表来转化。既然兄弟表示法的二叉链表存储结构中，每个结点的第二个指针域指向兄弟结点，那么树转二叉树的第一步就是在所有兄弟节点中加线（加线）。每个结点的第一个结点的第一个指针域只指向第一个孩子，不管他有多少个孩子，所以第二部就是去除每个节点中与孩子结点除与长子外的连线（去线）。第三步就是层次调整，注意：第一个孩子是二叉树结点的左孩子，兄弟转化过来的孩子是结点的右孩子。

2.森林转二叉树：第一步：把每棵树转化为二叉树。第二部：第一颗二叉树不动，从第二颗二叉树开始依次把后一颗二叉树的根结点作为前一棵二叉树的根节点的右孩子，用线连接起来。

3.二叉树转树：树转二叉树的逆序过程。

4，二叉树转森林：深林转二叉树的逆序过程。

注：当以二叉链表作树的存储结构时，树的先根遍历和后根遍历可以借用二叉树的前序遍历和中序遍历算法来实现。因为树的前根遍历与二叉树的前序遍历相同，树的后根遍历与二叉树的中序遍历一样。