数据结构note（五）

发表于 更新于 分类于 ， Waline： 阅读次数： 本文字数： 3.2k 阅读时长 ≈ 3 分钟

树的定义

树(Tree)是n(n>=0)个结点的有限集。

  • 若n=0，称为空树；

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

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

  • 其余结点可分为m(m>=0)个互不相交的有限集T1,T2,…,Tm，其中每一个集合本身又是一棵树，并称为根的子树(Subtree)。

基本术语

结点：数据元素以及指向子树的分支（特殊：没有前驱结点的结点叫根结点）

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

叶子结点/终端结点：度=0的结点

分支结点：度≠0的结点，且除了根节点的分支结点称为内部结点

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

根节点看成第一层，其孩子看成第二层，以此类推。双亲位于同一层上的结点称为堂兄弟。从根到该结点所经过分支上的所有结点称为结点的祖先，以某结点为根的子树中的任一结点称为结点的子孙。

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

树的深度/高度：树中结点的最大层次

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

无序树：树中结点的各个子树无次序

森林：是m(m≥0)棵互不相交的树的集合（一棵树也是森林，把根节点删除后也能成为森林）

二叉树

二叉树也即每个结点最多只有两个“叉”的树，研究二叉树的意义在于，普通树若不转化为二叉树，则运算很难实现。

  • 二叉树结构简单、规律性强；

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

特点：

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

  2. 子树有左右之分，顺序不能颠倒

  3. 可以是空集，可以有空左子树和空右子树

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

具有三个结点的二叉树可能有几种不同形态？普通树呢？

答：二叉树有五种：左—（左，右）；左—左—左；左—左—右；左—右—左；左—右—右。

普通树则只有两种。所以说二叉树和树是两个概念。

性质：

  1. 在二叉树的第i层上至多有$2^{i-1}$个结点(i≥1)，至少有1个结点。

  2. 深度为k的二叉树至多有$2^k-1$个结点，至少k个结点。（k≥1，等比数列求和可证明）

  3. 对任何一棵二叉树T，如果叶子数为$n_0$，度为2的结点数为$n_2$，则$n_0=n_2+1$。

满二叉树

深度为k且有$2^k-1$个结点的二叉树称为满二叉树。其叶子结点均在最底层。

对满二叉树结点位置进行编号，规则是自上而下，自左而右。

完全二叉树

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

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

完全二叉树的叶子只可能分布在层次最大的两层，对任意结点，如果其右子树的最大层数为i，则其左子树的最大层次必为i或i+1。

具有n个结点的完全二叉树的深度为$\lfloor log_2n\rfloor+1$，这里$\lfloor x \rfloor$是指不大于x的最大整数，即向下取整。

设某个孩子结点的编号是i，则其双亲的编号是$\lfloor i/2 \rfloor$，这个孩子的左孩子编号为$2i$，右孩子为$2i+1$。

二叉树的链式储存（二叉链表）

顺序储存有空间冗余过大的缺点，最好用于满二叉树和完全二叉树。这里主要介绍链式储存。

在n个结点的二叉链表中，有n+1个空指针域。这是因为总共2n个链域，除了根结点外每个结点都有一个双亲，所以有n-1个结点的链域存放指针。故空指针数目=2n-(n-1)=n+!。

二叉树的遍历

即顺着某一条搜索路径巡访二叉树的结点，使得每个结点都被且仅被访问一次。

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

遍历是树结构插入、删除、修改、查找和排序运算的前提，是一切运算的基础和核心。

遍历方法（一）

假设L：遍历左子树；D：访问根结点；R：遍历右子树

则遍历整个二叉树的方案有：DLR/DRL/LDR/LRD/RDL/RLD六种。

若规定先左后右，按根结点的访问顺序命名，则只有三种：

DLR：先（根）序遍历；

LDR：中（根）序遍历；

LRD：后（根）序遍历。

通过已知中序和任意其他序确定唯一的二叉树

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

先序：ABCDEFGHIJ

中序：CDBFEAIHGJ

这类确定的方法是先通过先序的第一个结点结合其在中序的位置确定左右子树的结点分配，在这里先序第一个结点为A，即根结点为A，A在中序的位置可以确定左子树包含CDBFE，右子树包含IHGJ，这样以此类推，就可以确定如下二叉树。

在这个例子中就可以明显看出中序的作用了。

遍历方法（二）

前面的方法是将二叉树看为L，D，R三个部分，这里的层次遍历法则是将二叉树按照层次顺序来遍历，即：从根节点开始，按从上到下，从左到右的方式访问每一个结点，每个结点仅访问一次。

算法思路是结合队列，①将根结点入队，②队不为空时循环：从队列中出列一个结点p，访问它；若它有左孩子则左孩子进队，有右孩子则右孩子进队。下面视频的2:54处有很形象的介绍。

具体实现

ADT定义：

1
2
3
4
5
6
7
8
typedef char TElemType;//可修改为其他数据类型
enum traverse { DLR = 1, LDR, LRD };//遍历类型

typedef class BiNode {
public:
    TElemType data;//数据域
    BiNode* lchild, * rchild;//左孩子、右孩子指针
}BiNode,* BiTree;

操作集：（这里只放了最基本的操作集）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
//判空
bool IsEmpty(BiTree BT) {
    if (BT == NULL) return true;
    else return false;
}

//访问二叉树
void Visit(BiTree BT) {
    std::cout<<BT->data;
    return;
}

//二叉树的遍历
void Traversal(BiTree BT,traverse way) {
    if (BT == NULL) return;
    else {
        switch (way) {
        case DLR: {
            Visit(BT);
            Traversal(BT->lchild, DLR);
            Traversal(BT->rchild, DLR);
        }
              break;
        case LDR: {
            Traversal(BT->lchild, LDR);
            std::cout << BT->data;
            Traversal(BT->rchild, LDR);
        }
              break;
        case LRD: {
            Traversal(BT->lchild, LRD);
            Traversal(BT->rchild, LRD);
            Visit(BT);
        }
              break;
        }
    }
}

//先序创建二叉树
void CreateBiTree(BiTree &T) {
    char ch;
    std::cin >> ch;
    if (ch == '#') {
        T = NULL;
    }
    else {
        T = new BiNode;
        T->data = ch;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }

}

这里创建二叉树的函数中，由于要对实参进行修改，首先考虑指针，而BiTree已经是BiNode的指针了，再使用指针就会产生指针的指针，这对代码的阅读上不太方便，因此这里采用了引用。

参考资料：C++实现先序创建二叉树