二叉树

发表于 更新于 阅读次数： 9 本文字数： 2.6k 阅读时长 ≈ 9 分钟

树的基本概念和存储结构已经介绍过了，现在介绍数据结构中极其重要的二叉树。

部分显示问题，请参考

定义

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

二叉树的特点有:

每个结点最多有两棵子树，所以二又树中不存在度大于 2 的结点。注意不是只有两棵子树，而是最多有。没有子树或者有棵子树都是可以的。

左子树和右子树是有顺序的，次序不能任意颠倒。就像人是双手、双脚，但显然左手、左脚和右手、右脚是不一样的，右手戴左手套、右脚穿左鞋都会极其别扭和难受。

即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。图 6-5-3 中，树 1 和树 2 是同一棵树，但它们却是不同的二叉树。就好像你一不小心，摔伤了手，伤的是左手还是右手，对你的生活影响度是完全不同的。

二叉树具有五种基本形态:

1. 空二叉树。

2. 只有一个根结点。

3. 根结点只有左子树。

4. 根结点只有右子树。

5. 根结点既有左子树又有右子树。

特殊二叉树

斜树

所有的结点都只有左子树的二叉树叫左斜树。所有的结点都只有右子树的二叉树叫右斜树。这两者统称为斜树。

满二叉树

在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

特点：

(1) 叶子只能出现在最下一层。出现在其他层就不可能达成平衡。

(2) 非叶子结点的度一 - 定是 2。否则就是 “缺胳膊少腿” 了。

(3) 在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。

完全二叉树

对一棵具有 n 个结点的二叉树按层序编号，如果编号为 i（1≤i≤n）的结点与同祥深度的满二叉树中编号为 i 的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。

特点：

(1) 叶子结点只能出现在最下两层。

(2) 最下层的叶子一定集中在左部连续位置。

(3) 倒数二层，若有叶子结点，一定都在右部连续位置。

(4) 如果结点度为 1，则该结点只有左孩子，即不存在只有右子树的情况。

(5) 同样结点数的二叉树，完全二叉树的深度最小。

二叉树的性质

性质一

在二叉树的第 i 层上至多有 2i−1 个结点（i>=1）。

性质二

深度为 k 的二叉树至多有 2k−1 个结点（k>=1）。

性质三

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

性质四

具有 n 个结点的完全二叉树的深度为 [log2n]+1（[x] 表示不大于 x 的最大整数）。

性质五

对于完全二叉树，若从上至下、从左至右编号，则编号为 i 的结点，其左孩子编号必为 2i，右孩子编号必为 2i＋1，双亲的编号必为 i/2。

二叉树的存储结构

二叉树顺序存储结构

一般只用于完全二叉树，不详解。

二叉链表

二叉树每个结点最多有两个孩子，所以为他设计一个数据与和两个指针域，称这样的链表叫做二叉链表。

lchild | data | rchild |
1
2
3
4
5
typedef struct BiTNode
{
    TElemType data;     /*数据*/
    struct BiTNode* lchild, * rchild;   /*左右孩子指针*/
}BiTNode, * BiTree;

遍历二叉树

原理

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

遍历方法

前序遍历即先（根）序的遍历算法

1
2
3
4
5
6
7
8
void PreOrderTraverse(BiTree T)
{
    if (T == NULL)
        return;
    cout << T->data;
    PreOrderTraverse(T->lchild);
    PreOrderTraverse(T->rchild);
}

上图前序遍历：A BDG CEF

中序遍历即中（根）序的遍历算法

1
2
3
4
5
6
7
8
void InOrderTraverse(BiTree T)
{
    if (T == NULL)
        return;
    InOrderTraverse(T->lchild);
    cout << T->data;
    InOrderTraverse(T->rchild);
}

上图中序遍历：DGB A ECF

后序遍历即后（根）序的遍历算法

1
2
3
4
5
6
7
8
void PostOrderTraverse(BiTree T)
{
    if (T == NULL)
        return;
    PostOrderTraverse(T->lchild);
    PostOrderTraverse(T->rchild);
    cout << T->data;
}

上图后序遍历：GDB EFC A

层序遍历即逐层遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void FloorPrint(BiTree T)
{
    BiTree temp[100];   //创建pTreeNode指针类型的指针数组
    int in = 0;
    int out = 0;
    temp[in++] = T;  //先保存二叉树根节点
    while (in > out)
    {
        if (temp[out])
        {
            cout << temp[out]->data;
            temp[in++] = temp[out]->lchild;
            temp[in++] = temp[out]->rchild;
        }
        out++;
    }
}

上图层序遍历：A BC DEF G

二叉树建立

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void CreateBiTree(BiTree& T)
{
    TElemType c;
    cin >> c;
    if (c == '#')
        T = NULL;
    else
    {
        T = new BiTNode;
        if (!T)
            cout << "分配空间失败" << endl;
        else
        {
            T->data = c;
            CreateBiTree(T->lchild);
            CreateBiTree(T->rchild);
        }
    }
}

线索二叉树

把指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树就称为线索二叉树（Threaded Binary Tree）。

lchild | ltag | data | rtag | rchild |

其中：

ltag 为 0 时指向该结点的左孩子，为 1 时指向该结点的前驱。

rtag 为 0 时指向该结点的右孩子，为 1 时指向该结点的后继。

线索二叉树结构实现

存储结构定义

1
2
3
4
5
6
7
typedef struct BiThrNode
{
    TElemType data;
    struct  BiThrNode* lchild, * rchild;
    int LTag, RTag; //LTag(RTag)=0表示指向孩子，LTag(RTag)=1表示只是前驱或后继
}BiThrNode, * BiThrTree;
BiThrTree pre;//全局变量，始终指向刚刚访问过的节点

中序遍历进行中序线索化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void InThreading(BiThrTree p)
{
    if (p)
    {
        InThreading(p->lchild);/* 递归左子树线索化 */
        if (!p->lchild)/* 没有左孩子 */
        {
            p->LTag = 1;/* 前驱线索 */
            p->lchild = pre; /* 左孩子指针指向前驱 */
        }
        else
            p->LTag = 0;
        if (!pre->rchild) /* 前驱没有右孩子 */
        {
            pre->RTag = 1;/* 后继线索 */
            pre->rchild = p;/* 前驱右孩子指针指向后继(当前结点p) */
        }
        else
            p->RTag = 0;
        pre = p;/* 保持pre指向p的前驱 */
        InThreading(p->rchild);/* 递归右子树线索化 */
    }
}

中序线索二叉树遍历（带有头节点）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void InOrderTraverse_Thr(BiThrTree T)
{
    BiThrTree p;
    p = T->lchild; /* p指向根结点 */
    while (p != T)/* 空树或遍历结束时,p==T */
    {
        while (p->LTag == 0)
            p = p->lchild;
        cout << p->data;
        while (p->RTag == 1 && p->rchild != T)
        {
            p = p->rchild;
            cout << p->data;
        }
        p = p->rchild;
    }
}

树、森林与二叉树的转换

树转换为二叉树

1. 加线。在所有兄弟结点之间加一条连线。

2. 去线。对树中每个结点，只保留它与第一一个孩子结点的连线， 删除它与其他孩子结点之间的连线。

3. 层次调整。以树的根结点为轴心，将整棵树顺时针旋转定的角度， 使之结构层次分明。注意第一个孩子是二叉树结点的左孩子，兄弟转换过来的孩子是结点的右孩子。

森林转换为二叉树

森林是由若干棵树组成的，所以完全可以理解为，森林中的每一棵树都是兄弟，可以按照兄弟的处理办法来操作。步骤如下:

1. 把每个树转换为二叉树。

2. 第一棵二又树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子用线连接起来。当所有的二叉树连接起来后就得到了由森林转换来的二叉树。

二叉树转换为树

二叉树转换为树是树转换为二叉树的逆过程，也就是反过来做而已。步骤如下:

1. 加线。若某结点的左孩子结点存在，则将这个左孩子的右孩子结点、右孩子的右孩子结点、右孩子的右孩子的右孩子结.... 哈，反正就是左孩子的 n 个右孩子结点都作为此结点的孩子。将该结点与这些右孩子结点用线连接起来。

2. 去线。删除原二叉树中所有结点与其右孩子结点的连线。

3. 层次调整。使之结构层次分明。

二叉树转换为森林

判断一棵二叉树能够转换成棵树还是森林， 标准很简单，那就是只要看这棵二叉树的根结点有没有右孩子，有就是森林，没有就是一棵树。那么如果是转换成森林，步骤如下:

1. 从根结点开始，若右孩子存在，则把与右孩子结点的连线删除，再查看分离后的二叉树，若右孩子存在，则连线删除.... 直到所有右孩子连线都删除为止，得到分离的二叉树。

2. 再将每棵分离后的二叉树转换为树即可。

树与森林的遍历

最后我们再谈谈关于树和森林的遍历问题。

树的遍历分为两种方式。

1. 一种是先根遍历树， 即先访问树的根结点，然后依次先根遍历根的每棵子树。

2. 另一种是后根遍历》即先依次后根遍历每棵子树，然后再访问根结点。

森林的遍历也分为两种方式:

1. 前序遍历：先访问森林中第一棵树的根结点，然后再依次先根遍历根的每棵子树，再依次用同样方式遍历除去第一棵树的剩余树构成的森林。

2. 后序遍历：是先访问森林中第一棵树，后根遍历的方式遍历每棵子树，然后再访问根结点，再依次同样方式遍历除去第一棵树的剩余树构成的森林。

总结

二叉树应用很广的。

部分显示问题，请参考