[数据结构与算法]数据结构与算法-第五章 树与二叉树

树

用来描述结点之间有分支，具有层次关系的结构

树的定义

树（Tree）是n（n>=0）个结点的有限集。
	若n=0，称为空树；
	若n>0，则满足如下两个条件：
		有且仅有一个特定的root
		其余结点可分为m个互不相交的有限集合，其中每个集合本身也是一棵子树

树的表示法

• 层次结构表示
• 嵌套集合表示
• 凹入表示
• 广义表表示

树的特点

• 树是一种递归的数据结构
• 除根结点外的所有结点有且仅有一个前驱结点
• 树中的所有结点可以有零个或多个后继结点

树的基本术语

• 根结点：非空子树中吴前驱结点的结点
• 结点的祖先：从根到该结点所经分支上的所有结点
• 结点的子孙：以某结点为根的子树中的任意结点
• 结点的孩子：结点的子树的根
• 结点的双亲：该结点所在子树的根
• 兄弟结点：共同的双亲
• 堂兄结点：双亲在同一层的结点
• 结点的度：结点拥有的子树的数量
• 树的度：树内各结点的度的最大值
• 分支结点：度！=0，非终端结点，除根结点的分支结点称为内部结点
• 叶子结点：度=0，终端结点
• 结点的层次：该结点的最大深度
• 树的深度：树中结点的最大层次
• 有序树：树中结点的各子树从左到右有次序（最左边为第一个孩子）
• 无序树：各子树无次序
• 森林：是m棵树互不相交的树的集合，一棵树也是森林，给森林中各子树加上一个双亲结点，森林就变成了树

二叉树

• 二叉树结构最简单，规律性最强
• 所有数都能转化为唯一对应的二叉树

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

二叉树的特点

• 每个结点最多有俩孩子（二叉树中不存在度大于2的结点）
• 子树有左右之分，其次序不能颠倒，是与树的最主要差别
• 二叉树可以是空集合，根可以有空的左子树或右子树

二叉树的五种基本形态

空二叉树，根和空的左右子树，根和左子树，根和右子树，根和左右子树

二叉树的性质

1. 在二叉树的第i层上至多有2的i-1次方个结点—第i层上最少有i个结点，每一层上最少有1个结点
2. 深度为k的二叉树至多有2的k次方-1个结点，最少有k个结点
3. 对任意一棵二叉树T，如果叶子数为n0，度为2的结点数为n2，则n0=n2 +1
4. 具有n个结点的完全二叉树的深度为log₂n的底+1；底表示不大于底的最大整数。
5. 如果对一棵有n个结点的完全二叉树的结点按层序编号，则，对任一结点i有：i=1，则结点i是二叉树的根，无双亲，如果i＞1，则双亲是结点i/2的底；如果2i＞n，则结点i为叶子结点，无左孩子，否则其左孩子是结点2i；如果2i+1＞n，则结点i无右孩子，否则其右孩子是结点2i+1

二叉树的存储结构

顺序存储结构

实现：按满二叉树的结点层次编号，用数组依次存放二叉树中的数据元素
顺序存储结构适用于满二叉树和完全二叉树

#define MAXSIZE 100
typedef int SqBiTree[MAXSIZE];
SqBiTree bt;

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

链式存储结构

二叉链表

二叉树结点的特点：parent，lchild，rchild，data
存储方式：[lchild，data，rchild] 其中结点缺少左右孩子，则对应的指针为空，
可推测在n个结点的二叉链表中，有n+1个空指针域

// 二叉链表
typedef struct BiNode{
    int data;
    struct BiNode * lchild; // 左孩子
    struct BiNode * rchild; // 右孩子
}BiNode, *BiTree;

三叉链表

三叉链表：[lchild，data，parent，rchild]

// 三叉链表
typedef struct TriTNode {
    int data;
    struct TriTNode *lchild, *parent, *rchild;
}TriTNode, *TriTree;

二叉树的基本操作

二叉树的创建

二叉树的遍历

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

• 先序遍历：根必定在第一个
• 中序遍历：需配合前后遍历确定一棵二叉树
• 后序遍历：根必定在最后一个
• 层次遍历：从根节点开始，从上到下，从左到右

// 先序遍历
void PreOrderTraverse(BiTree t) {
    if (t == NULL) {
        printf("tree is NULL");
    } else {
        printf("%d\t", t->data);
        PreOrderTraverse(t->lchild);
        PreOrderTraverse(t->rchild);
    }
}
// 中序遍历
void InOrderTraverse(BiTree t) {
    if (t == NULL) {
        printf("tree is NULL");
    } else {
        InOrderTraverse(t->lchild);
        printf("%d\t", t->data);
        InOrderTraverse(t->rchild);
    }
}
// 后序遍历
void PostOrderTraverse(BiTree t) {
    if (t == NULL) {
        printf("tree is NULL");
    } else {
        PostOrderTraverse(t->lchild);
        PostOrderTraverse(t->rchild);
        printf("%d\t", t->data);
    }
}
// 结论：从递归的角度看，三种算法是完全相同的，时间效率On，或者说这三种算法的访问路径是相同的，只是访问结点的时机不同。
// 从根节点出发到终点的路径上，每个结点经过三次，第一次经过时访问=先序遍历；第二次经过时访问=中序遍历；
// 第三次经过时访问=后序遍历

非递归遍历算法（栈）

我们需要手撕一个栈的基本操作

// 中序遍历非递归算法：入栈根结点，遍历根结点的左子树为空时，出栈根结点继续访问右子树。
typedef BiNode* STDataType;
typedef struct Stack {
    STDataType* a;
    int top;
    int capacity;
}ST;

void StackInit(ST * ps) {
    assert(ps);
    ps->a = NULL;
    ps->top = 0;
    ps->capacity = 0;
}

bool StackEmpty(ST* ps) {
    assert(ps);
    return ps->top == 0;
}

void StackPush(ST * ps, STDataType x) {
    assert(ps);
    if (ps->top == ps->capacity) {
        int newCapacity = ps->capacity == 0 ? 4 : ps->capacity *2;
        STDataType * tmp = realloc(ps->a, sizeof(STDataType)*newCapacity);
        if (tmp == NULL) {
            printf("realloc fail");
            exit(-1);
        }
        ps->a = tmp;
        ps->capacity = newCapacity;
    }
    ps->a[ps->top] = x;
    ps->top++;
}

void StackPop(ST* ps) {
    assert(ps);
    assert(!StackEmpty(ps));
    ps->top--;
}

STDataType StackTop(ST* ps) {
    assert(ps);
    assert(!StackEmpty(ps));
    return ps->a[ps->top - 1];
}
// 中序非递归遍历二叉树算法
void InorderTraverse(BiTree t, ST *S) {
    BiTree p = t;
    StackInit(S);
    while (p || StackEmpty(S)) {
        if (p) {
            StackPush(S,p);
            p = p->lchild;
        } else {
            p = StackTop(S);
            StackPop(S);
            printf("%c", p->data);
            p = p->rchild;
        }
    }
}

层次遍历算法（队列）

计算二叉树的深度

计算二叉树结点的总数

两种特殊形式的二叉树

• 满二叉树：一棵深度为k且有2的k次方-1个结点的二叉树称为满二叉树。1. 每一层上的结点都是最大结点数（即每层都满）2. 叶子结点全部在最底层。

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

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

在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即是一棵完全二叉树，一定是连续去掉！！！
叶子只可能分布在层次最大的两层上
对任一结点，如果其右子树的最大层次为i，其左子树的最大层次必为i或i+1

线索二叉树

当用二叉链表作为二叉树的存储结构时，可以很方便的找到某个结点的左右孩子；但一般情况下，无法直接找到该结点在某种遍历序列中的前驱和后继结点。
利用二叉链表的中的空指针域：如果某个结点的左孩子为空，则将空的左孩子指针域改为指向其前驱；如果某结点的右孩子为空，则将空的右孩子指针域改为指向其后继
为区分lchild和rchild指针到底指向的是孩子，还是指向前驱或者后继，对二叉链表中每个结点增设两个标志位ltag和rtag，并约定：ltag=0，lchild指向该结点的左孩子；ltag=1，lchild指向该结点的前驱

增设头结点的线索二叉树

ltag=0，lchild指向根结点
rtag=1，rchild指向遍历序列中最后一个结点
遍历序列中第一个结点的lchild域和最后一个结点的rc域都指向头结点