树与二叉树

1.树

1.树形结构(非线性结构)

结点之间有分支，具有层次关系

树的定义：

树(tree)是n(n≥0)个有限集。

若n = 0，则称为空树；

若n > 0，则它满足如下两个条件：

1. 有且仅有一个特定的称为根(Root)的结点；

2. 其余结点可分为m(m≥0)个互不相交的有限集T1,T2,T3,.....,Tm,其中每一个集合本身又是一棵树，并称为根的子树(SubTree)；

树的其他表示方法：

嵌套集合

广义表

凹入表式

2.树的基本术语

结点：数据元素以及指向子树的分支。

根节点：非空树中无前驱结点的结点

结点的度：结点拥有的子树数

树的度：树内各节点的度的最大值

非终端结点：根结点以外的分支结点称为内部结点

叶结点：终端结点

结点的子树的根称为该结点的孩子，该结点称为孩子的双亲

堂兄弟结点：双亲在同一层的结点

结点的祖先：从根到该结点所经分支上的所有结点。

结点的子孙：以某结点为根的子树中的任一结点。

有序树：树中结点的各子树从左至右有次序（最左边的为第一个孩子）。

森林：是m(m≥0)棵互不相交的树的集合。

把根结点删除树就变成了森林。

一棵树可以看成是一个特殊的森林。

给森林中的各子树加上一个双亲结点，森林就变成了树。

3.树结构和线性结构的比较

2.二叉树

二叉树的结构最简单，规律性最强；

可以证明，所有树都能转为唯一对应的二叉树，不失一般性。

普通树（多叉树）若不转化为二叉树，则运算很难实现。

二叉树在树结构的应用中起着非常重要的作用，因为对二叉的许多操作算法简单，而任何树都可以与二叉树相互转换，这样就解决了树的存储结构及其运算中存在的复杂性。

1.二叉树的定义

二叉树是n(n≥0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成。

特点：

1. 每个结点最多有两个孩子（二叉树中不存在大于2的结点）。

2. 子树有左右之分，其次序不能颠倒。

3. 二叉树可以是空集合，根可以有空的左子树或空的右子树。

注意：二叉树不是树的特殊情况，他们是两个不同的概念。

二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。

树当结点只有一个孩子时，就无须区分它是左还是右的次序。因此二者是不同的。这是二叉树与树的最主要的差别。

(也就是二叉树每个结点位置或者说次序都是固定的，可以是空，但是不可以说它没有位置，而树的结点位置是相对于别的结点来说的，没有别的结点时，它就无所谓左右了)

思考：

注意：虽然二叉树与树概念不同，但有关树的基本术语对二叉树都适用。

3.应用案例

1.数据压缩问题

将数据文件转换成由0、1组成的二进制串，称之为编码。

2.利用二叉树求解表达式的值

以二叉树表示表达式的递归定义如下：

1. 若表达式为数或简单变量，则相应二叉树中仅有一个根结点，其数据域存放该表达式信息；

2. 若表达式为“第一操作数运算符第二操作数”的形式，则相应的二叉树中以左子树表示第一操作数，右子树表示第二操作数，根结点的数据域存放运算符(若为一元运算符，则左子树为空)，其中，操作数本身又为表达式。

​

4.抽象数据类型定义

1.二叉树的抽象数据类型定义

类型定义

ADT BinaryTree
{
    数据对象D:D是具有相同特性的数据元素的集合
    数据关系R:若D＝∅，则R=∅中;
             若D≠Φ，则R={H};H是如下二元关系：
            ①root唯一//关于根的说明
            ②Dj∩Dk=∅//关于子树不相交的说明
            ③//关于数据元素的说明
            ④//关于左子树和右子树的说明
    基本操作P:
}ADT BinaryTree;

具体形式

CreateBiTree(&T,definition)
{
    初始条件:definition给出二叉树T的定义;
    操作结果:按definition构造二叉树;
}
​
PreOrderTraverse(T)
{
    初始条件:二叉树T存在;
    操作结果:先序遍历T，对每个节点访问一次;
}
​
InOrderTraverse(T)
{
    初始条件:二叉树T存在;
    操作结果:中序遍历T，对每个结点访问一次;
}
​
PostOrderTraverse(T)
{
    初始条件:二叉树T存在;
    操作结果:后序遍历T，对每个结点访问一次;
}

2.二叉树的性质和存储结构

性质1：在二叉树的第i层上至多有2^(i-1)个结点(i≥1)。

证：采用归纳法证明此性质。 归纳基：当i=1时，只有一个根结点，2^(i-1)=2=1，命题成立。 归纳假设：设对所有的(1 ≤ j < i)，命题成立，即第j层上至多有2^(j-1)个结点。那么可以证明 j = i时命题也成立。

性质2：深度为k的二叉树至多有2^(k) - 1个结点(k≥1)。

证：由性质1可知，深度为k的二叉树的最大结点数为：

推论：深度为k时至少有k个结点。

性质3：对任何一棵二叉树T，如果其叶子数为n0，度为2的结点数为n2，则n0 = n2 + 1。

5.特殊形式的二叉树

1.满二叉树

一棵深度为k且有2^k-1个结点的二叉树称为满二叉树。

特点：

1. 每一层上的结点数都是最大结点数（即每层都满）

2. 叶子节点全部在最底层

3. 对满二叉树结点位置进行编号

4. 编号规则：从根结点开始，自上而下，自左而右。

5. 每一结点位置都有元素。

满二叉树在同样深度的二叉树中结点个数最多

满二叉树在同样深度的二叉树中叶子结点个数最多

2.完全二叉树

深度为k的具有个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应时，称之为完全二叉树。

注意：在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即是一棵完全二叉树，一定是连续的去掉！！！

特点：

1. 叶子只可能分布在层次最大的两层上。

2. 对任一结点，如果其右子树的最大层次为i，则其左子树的最大层次必为i或i+1。

性质4：具有n个结点的完全二叉树的深度为[Iog2n]+1。

性质5：如果对一棵有n个结点的完全二叉树（深度为[Iog2n]+1点按层序编号（从第1层到第[Iog2n]+1层，每层从左到右），则对任一结点i(1≤i≤n)，有：

1. 如果i = 1，则结点 i 是二叉树的根，无双亲；如果i>1,则其双亲是结点[ i / 2 ]。

2. 如果2i>n,则结点为叶子结点，无左孩子；否则，其左孩子是结点2ⅰ。

3. 如果2i+1>n,则结点无右孩子；否则，其右孩子是结点2i+1。

性质5表明了完全二叉树中双亲结点编号与孩子结点编号之间的关系

6.二叉树的性质和存储结构

1.二叉树的顺序存储

实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素。

//二叉树的顺序存储
#define MAXTSIZE 100
Typedef TElemType SqBiTree[MAXSTIZE]
SqBiTree bt;

注意：普通二叉树也能按照这样的存储结构进行存储，为空的部分预留位置出来。

二叉树的顺序存储缺点：最坏情况：深度为②的且只有k个结点的单支树需要长度为2^k - 1的一维数组。

特点：结点间关系蕴含在其存储位置中,浪费空间，适于存满二叉树和完全二叉树

2.二叉树的链式存储

二叉树结点的特点：有两个孩子

存储方式：

typedef struct BiNode
{
    TElemType data;
    struct BiNode *lchild, *rchild;//左右孩子指针
}BiNode,*BiTree;

分析空指针域：

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

分析：必有2个链域。除根结点外每个结点有且仅有一个双亲，所以只会有 n - 1个结点的链域存放指针指向非空子女结点。

空指针数目 = 2n - (n - 1) = n + 1

3.三叉链表

typedef struct TriTNode
{
    TelemType data;
    struct TriTNode *lchild,*parent,*rchild;
}TriTNode, *TriTree;

遍历二叉树

遍历定义：顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次（又称周游）

“访问”的含义很广，可以是对结点作各种处理，如：输出结点的信息、修改结点的数据值等，但要求这种访问不破坏原来的数据结构。

遍历目的：得到树中所有结点的一个线性排列。

遍历的用途：它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树运算的基础和核心。

1.遍历的方法

依次遍历二叉树中的三个组成部分，便是遍历了整个二叉树

DLR——先（根）序遍历 根左右 ABC

LDR——中（根）序遍历 左根右 BAC

LRD——后（根）序遍历 左右根 BCA

例题1：

先序：A B D G C E H F

中序：D G B A E H C F

后序：G D B H E F C A

例题2：

已知先序和中序序列求二叉树

已知二叉树的先序和中序序列，构造出相应的二叉树

先序：A B C D E F G H I J

中序：C D B F E A I H G J

最上面的根是A，通过中序可知左右子树

2.递归算法

1.先序遍历算法

Status PreOrderTraverse(BiTree T)
{
    if(T == NULL) return OK;//空二叉树
    else
    {
        visit(T);//访问根节点
        PreOrderTraverse(T->lchild);//递归遍历左子树
        PreOrderTraverse(T->rchild);//递归遍历右子树
    }
}

2.中序遍历算法

Status PreOrderTraverse(BiTree T)
{
    if(T == NULL) return OK;//空二叉树
    else
    {
        PreOrderTraverse(T->lchild);//递归遍历左子树
        visit(T);//访问根节点
        PreOrderTraverse(T->rchild);//递归遍历右子树
    }
}

3.后序遍历算法

Status PreOrderTraverse(BiTree T)
{
    if(T == NULL) return OK;//空二叉树
    else
    {
        PreOrderTraverse(T->lchild);//递归遍历左子树
        PreOrderTraverse(T->rchild);//递归遍历右子树
        visit(T);//访问根节点
    }
}

3.非递归算法

1.中序遍历算法

栈

Status InOrderTraverse(BiTree T)
{
    BiTree p;
    InitStack(S);
    p = T;
    while(p || !StackEmpty(S))
    {
        if(p)
        {
            Push(S,p);
            p = p->lchild;
        }
        else
        {
            Pop(S,q);
            cout << q->data << " ";
            p = q->rchild;
        }
        return OK;
    }
}

2.层次遍历算法

将根结点进队；

队不空时循环：从队列中出列一个结点*p，访问它；

1. 若它有左孩子结点，将左孩子结点进队；

2. 若它有右孩子结点，将右孩子结点进队。

void LevelOrder(BTNode *b)
{
    BTNode *p;
    SqOueue *qu;
    InitQueue(qu);//初始化队列
    enQueue(qu, b);//根结点指针进入队列
    while(!QueueEmpty(qu))
    {
        //队不为空，则循环
        deQueue(qu, p);//出队结点p
        cout << p->data;//访问结点p
        if(p->lchild != NULL)
            enQueue(qu, p->lchild);//有左孩子时将其进队
        if(p->rchild != NULL)
            enQueue(qu, p->rchild);//有右孩子时将其进队
    }
}

4.二叉树的建立

按先序遍历序列建立二叉树的二叉链表

例：已知先序序列为：A B C D E G F

1. 从键盘输入二叉树的结点信息，建立二叉树的存储结构；

2. 在建立二叉树的过程中按照二叉树先序方式建立；

Status CreateBiTree(BiTree &T)
{
    cin >> ch;
    if(ch == "#") T = NULL;
    else
    {
        if(!(T = (BiTNode *)malloc(sizeof(BiTNode))))
        {
            exit(OVERFLOW);//T = new BiTNode;
        }
        T->data = ch;//生成根结点
        CreateBiTree(T->lchild);//构建左子树
        CreateBiTree(T->rchild);//构建右子树
    }
    return OK;
}//CreateBiTree

5.复制二叉树

如果是空树，递归结束；

否则，申请新结点空间，复制根结点

递归复制左子树和递归复制右子树

int Copy(BiTree T, BiTree &NewT)
{
    if(T == NULL)
    {
        //如果是空树返回0
        NewT = NULL;
        return 0;
    }
    else
    {
        NewT = new BiTNode;
        NewT->data = T->data;
        Copy(T->lchild, NewT->lchild);
        Copy(T->rchild, NewT->rchild);
    }
}

6.计算二叉树的深度

如果是空树则深度为0；

否则，递归计算左子树的深度记为，递归计算右子树的深度记为n,二叉树的深度则为m与的较大者加1。

int Depth(BiTree T)
{
    if(T == NULL) return 0;//如果是空树就返回0
    else
    {
        m = Depth(T->lchild);
        n = Depth(T->rchild);
        if(m > n) return ( m + 1 );
        else return (n + 1);
    }
}

7.二叉树结点总数

如果是空树，则结点个数为

否则，结点个数为左子树的结点个数 + 右子树的结点个数 + 1。

int NodeCount(BiTree T)
{
    if(T == NULL)
    {
        return 0;
    }
    else
        return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
}

8.二叉树叶子结点数

如果是空树，则叶子结点个数为0；

否则，为左子树的叶子结点个数 + 右子树的叶子结点个数。

int LeadCount(BiTree T)
{
    if(T == NULL)//如果是空树返回0
        return 0;
    if(T->lchild == NULL && T->rchild == NULL)
    {
        return 1;//如果是叶子结点返回1
    }
    else
        return LeafCount(T->lchild) + LeafCount(T->rchild);
}

线索二叉树

1.线索二叉树概念

提出的问题：

如何寻找特定遍历序列中二叉树结点的前驱和后继？？？

解决的方法：

1. 通过遍历寻找——费时间；

2. 再增设前驱、后继指针域——增加了存储负担；

回顾：

二叉树链表中空指针域的数量：具有n个结点的二叉链表中，一共有2n个指针域；因为n个结点中有n - 1个孩子，即2n个指针域中，有n - 1个用来指示结点的左右孩子，其余n + 1个指针域为空。

利用二叉链表中空指针域：如果某个结点的左孩子为空，则将空的左孩子指针域改为指向其前驱；如果某结点的右孩子为空，则将右孩子指针域改为指向其后继。

——这种改变指向的指针称为“线索”

加上线索的二叉树称为线索二叉树(Threaded Binary Tree)

按照存储结构的前驱和后继，将指针域的值进行指向

为了区分lchild和rchild指针到底是指向孩子的指针，还是指向前驱或者后继的指针，对二叉链表中每一个结点增设两个标志域ltag和rtag，并且约定：

ltag = 0 lchild指向该结点的左孩子

ltag = 1 lchild指向该结点的前驱

rtag = 0 rchild指向该结点的右孩子

rtag = 1 rchild指向该结点的后继

增设头结点：ltag=O,Ichild指向根结点，rtag=1,rchild指向遍历序列中最后一个结点。遍历序列中第一个结点的c域和最后一个结点的rc域都指向头结点。

2.线索二叉树练习

1.先序线索二叉树

先序序列：A B C D E

2.中序线索二叉树

中序遍历：H D I B E A F C G

树和森林

1.树与森林概念

树(Tree)是n(n≥0)个结点的有限集。若n=0,称为空树； 若n>0

1. 有且仅有一个特定的称为根(Root)的结点；

2. 其余结点可分为m(m≥0)个互不相交的有限集T1,T2,T3,...,Tm,

森林：是m(m≥0)棵不相交的树的集合。

2.树的存储结构

1.双亲表示法

实现：定义结构数组，存放树的结点，每个结点含两个域；

1. 数据域：存放结点本身信息。

2. 双亲域：指示本结点的双亲结点在数组中的位置。

类型描述

typedef struct PTNode
{
    TElemType data;
    int parent;//双亲位置域
}PTNode;

树结构：

#define MAX_TREE_SIZE 100
typedef struct
{
    PTNode nodes[MAX_TREE_SIZE];
    int r, n;//根结点的位置和结点个数
}PTree;

2.孩子链表

把每个结点的孩子结点排列起来，看成是一个线性表，用单链表存储，则n个结点有n个孩子链表（叶子的孩子链表为空表）。而n个头指针又组成一个线性表，用顺序表（含n个元素的结构数组）存储。

C语言类型描述：

孩子结点结构：

typedef struct CTNode
{
    int child;
    struct CTNode *next;
}*ChildPtr;
双亲结点结构：

typedef struct
{
    TElemType data;
    ChildPtr firstchild;//孩子链表头指针
}CTBox;

特点：找孩子容易，找双亲难。

3.孩子兄弟表示法

（二叉树表示法，二叉链表表示法）

实现：用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点

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

3.树与二叉树的转换

1.将树转化为二叉树

将树转化为二叉树进行处理，利用二叉树的算法来实现对树的操作。

由于树与二叉树都可以用二叉链表做存储，则以二叉链表作为媒介可以导出树与二叉树之间的一个对应关系。

算法：

1. 加线：在兄弟之间加一连线

2. 抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系

3. 旋转：以树的根结点为轴心，将整树顺时针转45°

口诀：树变二叉树：兄弟相连留长子

例题：

2.将二叉树还原回树

1. 加线：若p结点是双亲结点的左孩子，则将的右孩子，右孩子的右孩子.…沿分支找到的所有右孩子，都与p的双亲用线连起来

2. 抹线：抹掉原二叉树中双亲与右孩子之间的连线

3. 调整：将结点按层次排列，形成树结构

口诀：二叉树变树，左孩右右连双亲，去掉原来右孩线。

例题：

4.森林与二叉树的转化

1.森林转换成二叉树(二叉树与多棵树之间的关系)

1. 将各棵树分别转换成二叉树

2. 将每棵树的根结点用线相连

3. 以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构

2.二叉树转化成森林

1. 抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树

2. 还原：将孤立的二叉树还原成树

口诀：去掉全部右孩线，孤立二叉再还原

例题：

5.树与森林的遍历

1.树的遍历（三种方式）

1. 先序：根左右

   若树不为空，则先访问根节点，然后依次遍历各棵子树

2. 后序：左右根

   若树不为空，则先依次后根遍历各棵子树，然后访问根节点

3. 按层次遍历：

   若树不为空，则自上而下自左至右访问树中每个结点

2.森林的遍历

将森林看作由三部分构成：

1. 森林中第一棵树的根结点；

2. 森林中第一棵树的子树森林；

3. 森林中其它树构成的森林。

先序遍历：

若森林不空，则

1. 访问森林中第一棵树的根结点；

2. 先序遍历森林中第一棵树的子树森林；

3. 先序遍历森林中（除第一棵树之外）其余树构成的森林。

中序遍历：

若森林不空，则

1. 中序遍历森林中第一棵树的子树森林；

2. 访问森林中策一棵树的根结点；

3. 中序遍历森林中（除第一棵树之外）其余树构成的森林。

先序遍历：A B C D E F G H I J

中序遍历：B C D A F E H J I G