二叉树

二叉树

   数据结构 15 分钟读完 (大约2254个字) 0次访问

二叉树（Binary Tree)三种遍历算法

基于链表结构实现的二叉树又称二叉链表，本文主要介绍二叉树的存储以及先序遍历、中序遍历和后序遍历三种遍历方式的递归和非递归算法：

二叉树构造

二叉树抽象数据类型定义—— 基于链表实现

1
2
3
4
5
6
7
8
//----------二叉树的二叉链表存储表示--------------
typedef char TElemType;
typedef bool Status;
// 树节点定义
typedef struct BiTNode {
    TElemType data;
    struct BiTNode* lchild, * rchild;
}BiTNode, * BiTree;

二叉树递归构造： 通过指定按照满二叉树的节点输入顺序进行输入，对空树以 ‘.’ 表示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*---------------------二叉树创建函数------------------*/
Status CreateBiTree(BiTree& T)
{
    // 递归读入二叉树的各元素，因此最开始的T还是指向根节点
    TElemType ch;
    cin >> ch;
    if (ch == '.') T = NULL;
    else {
        if (!(T = (BiTree)malloc(sizeof(BiTNode)))) return false;
        T->data = ch;          // 生成根节点
        CreateBiTree(T->lchild);   // 递归构造左子树
        CreateBiTree(T->rchild);   // 递归构造右子树
    }
    return true;
}

二叉树操作算子

对二叉树的遍历往往是一个广泛的概念，遍历是对二叉树的每一个节点做一系列操作，其中最简单的就是输出节点数据域，这里只是以输出函数为例说明问题。

1
2
3
4
5
6
Status TreeTransOperator(TElemType e)    // 二叉树遍历算子
{
    // 对数据元素操作的应用函数
    cout << e << " ";
    return true;
}

递归算法

总体而言，递归算法较为简单，只需更换二叉树节点三部分的顺序即可，但需要注意的是左子树始终在右子树之前遍历；

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
//--------------------递归遍历算法-------------------------//
Status PreOrderTranRecursion(BiTree T, Status(*Visit)(TElemType e))
{
    /*---------------先序遍历二叉树的递归算法-------------------*/
    // 采用二叉链表存储结构，Visit是对数据元素操作应用的函数
    // 对于一个节点而言，一旦判断节点的三个单元为空即可返回递归上层
    if (T) {   // T所指节点非空
        if (Visit(T->data)) {      // 调用操作函数，Visit采用函数指针，指向操作函数
            if (PreOrderTranRecursion(T->lchild, Visit)) {    // 递归调用：Visit所指函数也进行递归
                if (PreOrderTranRecursion(T->rchild, Visit))  return true;
            }
        }
        return false;
    }
    else return true;
}
Status InOrderTranRecursion(BiTree T, Status(*Visit)(TElemType e))
{
    /*---------------中序遍历二叉树的递归算法-------------------*/
    // 采用二叉链表存储结构，Visit是对数据元素操作应用的函数
    // 对于一个节点而言，一旦判断节点的三个单元为空即可返回递归上层
    if (T) {   // T所指节点非空
        if (InOrderTranRecursion(T->lchild, Visit)) {      // 调用操作函数，Visit采用函数指针，指向操作函数
            if (Visit(T->data)) {    // 递归调用：Visit所指函数也进行递归
                if (InOrderTranRecursion(T->rchild, Visit))  return true;
            }
        }
        return false;
    }
    else return true;
}
Status PostOrderTranRecursion(BiTree T, Status(*Visit)(TElemType e))
{
    /*---------------后序遍历二叉树的递归算法-------------------*/
    // 采用二叉链表存储结构，Visit是对数据元素操作应用的函数
    // 对于一个节点而言，一旦判断节点的三个单元为空即可返回递归上层
    if (T) {   // T所指节点非空
        if (PostOrderTranRecursion(T->lchild, Visit)) {      // 调用操作函数，Visit采用函数指针，指向操作函数
            if (PostOrderTranRecursion(T->rchild, Visit)) {    // 递归调用：Visit所指函数也进行递归
                if (Visit(T->data))  return true;
            }
        }
        return false;
    }
    else return true;
}
//--------------------递归遍历算法-------------------------//

非递归算法

对于递归算法而言，当数据量比较大时，程序的时间复杂度往往较高，不易于直接使用；一个好的处理方式是，将递归函数转换为循环结构进行求解，而通过栈来模拟递归机理；
这里给出一个自定义栈模板类的程序，作为非递归算法的数据存储结构：

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
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<cstdlib>
//-----------------------自定义栈模板类--------------
typedef bool Status;

// 抽象数据类型定义
template<class TElemType>
struct SqNode{
    TElemType data;
    struct SqNode *next, *pre;    // 基于双向链表模拟栈
};

template<class TElemType>
class mystack
{
    public:
        struct SqNode<TElemType> *base,*top;   // 栈底和栈顶指针
        Status Init()
        {
            if(!(base = (struct SqNode<TElemType>*)malloc(sizeof(struct SqNode<TElemType>)))) return false;
            top = base;    // 判断栈空标志
            base->data = 0;   // 栈顶结点数据域记录栈中元素数
            base->next = NULL;
            base->pre = NULL;
            return true;
        }
        Status Push(TElemType e)
        {
            struct SqNode<TElemType> *stemp;
            if(!(stemp=(struct SqNode<TElemType>*)malloc(sizeof(struct SqNode<TElemType>)))) return false;
            top->next = stemp;
            stemp->data = e;
            stemp->pre = top;
            stemp->next = NULL;
            top = top->next; // 移动top指针始终位于栈顶

            base->data++;      // 栈元素计数
            return true;
        }
        Status Pop(TElemType &e)
        {
            if(top == base) return false;  // 栈空
            struct SqNode<TElemType> *stemp = top;
            top = top->pre;
            top->next = NULL;
            e = stemp->data;
            free(stemp);

            base->data--;
            return true;
        }
        Status Top(TElemType &p)
        {
            if(top == base) return false;
            p = top->data;
            return true;
        }

        Status Empty()
        {
            if(top == base) return true;
            else return false;
        }
        int Size()
        {
            return base->data;
        }
};

有了遍历所依赖的数据栈结构，那么便可以通过模拟递归的机理来进行处理：

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
//--------------------非递归遍历算法-------------------------//
//---------------------先序遍历二叉树------------------------//
Status PreOrderTranverse_1(BiTree T, Status(*Visit)(TElemType e))
{
    // 先序遍历二叉树T的非递归算法一
    mystack<BiTree> S; S.Init(); //创建并初始化遍历二叉链表所需要的栈
    S.Push(T);    // 根指针进栈
    BiTree p;     // 创建二叉树游标指针
    while (!S.Empty()) {
        while (S.Top(p) && p) {
            if (!Visit(p->data)) return false;
            S.Push(p->lchild);
        }
        S.Pop(p);    // 将向左尽头的空指针弹出
        if (!S.Empty()) {
            S.Pop(p);   // 根节点出栈
            S.Push(p->rchild);   // 遍历后转向
        }
    }
    return true;
}
Status PreOrderTranverse_2(BiTree T, Status(*Visit)(TElemType e))
{
    // 先序遍历二叉树T非递归算法二
    mystack<BiTree> S; S.Init(); //创建遍历二叉链表所需要的栈
    BiTree p = T;
    while (p || !S.Empty()) {
        if (p) {
            if (!Visit(p->data)) return false;
            S.Push(p);       // 根指针进栈
            p = p->lchild;    // 遍历左子树,当p=NULL时未进栈
        }
        else {
            S.Pop(p);
            p = p->rchild;
        }
    }
    return true;
}
//---------------------中序遍历二叉树------------------------//
Status InOrderTranverse_1(BiTree T, Status(*Visit)(TElemType e))
{
    // 中序遍历二叉树T的非递归算法一
    mystack<BiTree> S; S.Init(); //创建并初始化遍历二叉链表所需要的栈
    S.Push(T);    // 根指针进栈
    BiTree p;     // 创建二叉树游标指针
    while (!S.Empty()) {
        while (S.Top(p) && p) S.Push(p->lchild);   // 向左走到尽头
        S.Pop(p);    // 将向左尽头的空指针弹出
        if (!S.Empty()) {  
            S.Pop(p);   // 根节点出栈
            if (!Visit(p->data)) return false;   //遍历
            S.Push(p->rchild);   // 遍历后转向
        }
    }
    return true;
}

Status InOrderTranverse_2(BiTree T, Status(*Visit)(TElemType e))
{
    // 中序遍历二叉树T非递归算法二
    mystack<BiTree> S; S.Init(); //创建遍历二叉链表所需要的栈
    BiTree p = T;
    while (p || !S.Empty()) {
        if (p) {
            S.Push(p);       // 根指针进栈
            p = p->lchild;    // 遍历左子树
        }
        else {
            S.Pop(p);
            if (!Visit(p->data)) return false;
            p = p->rchild;
        }
    }
    return true;
}
//---------------------后序遍历二叉树------------------------//
Status PostOrderTranverse_1(BiTree T, Status(*Visit)(TElemType e))
{
    // 后序遍历二叉树T的非递归算法一
    mystack<BiTree> S; S.Init(); //创建并初始化遍历二叉链表所需要的栈
    S.Push(T);    // 根指针进栈
    BiTree p,lastp = NULL;     // 创建二叉树游标指针
    while (!S.Empty()) {
        while (S.Top(p) && p) S.Push(p->lchild);   // 向左走到尽头
        S.Pop(p);    // 将向左尽头的空指针弹出
        if (!S.Empty()) {
            S.Top(p);   // 获取根节点 
            if (p->rchild == NULL||p->rchild == lastp) {   // 节点信息无用时直接出栈
                S.Pop(p);  // 此时结点才可出栈
                lastp = p;
                if (!Visit(p->data)) return false;   //遍历
                S.Push(NULL);       //保证返回上层结点而不是下一轮继续向左走
            }else S.Push(p->rchild);
        }
    }
    return true;
}
Status PostOrderTranverse_2(BiTree T, Status(*Visit)(TElemType e))
{
    // 后序遍历二叉树T非递归算法二
    mystack<BiTree> S; S.Init(); //创建遍历二叉链表所需要的栈
    BiTree p = T,lastp = NULL;
    while (p || !S.Empty()) {
        if (p) {
            S.Push(p);       // 根指针进栈
            p = p->lchild;    // 遍历左子树,当p=NULL时未进栈
        }
        else {
            S.Top(p);
            if (p->rchild == NULL || p->rchild == lastp) {
                S.Pop(p);
                if (!Visit(p->data)) return false;
                lastp = p;
                p = NULL;          // 往回溯，置于NULL
            }
            else p = p->rchild;        // 控制右移转向
        }
    }
    return true;
}

主函数设定

为了直观的观察遍历结果，主函数设定一些输出参数：

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
int main()
{
    BiTree T;    // 构造一棵二叉树
    cout << "Input binary tree elements in order: (note: '.' means empty tree)\n";
    if (!CreateBiTree(T)) {
        cout << "Space allocate error!\n";
        return 0;
    }
    cout << "------------------Binary Recursion Traverse----------------------\n";
    cout << "Binary Tree First Order Traverse:\n";
    PreOrderTranRecursion(T, TreeTransOperator);
    cout << endl << "Binary Tree Middle Order Traverse:\n";
    InOrderTranRecursion(T, TreeTransOperator);
    cout << endl << "Binary Tree Post Order Traverse:\n";
    PostOrderTranRecursion(T, TreeTransOperator);

    cout << endl << "------------------Binary NonRecursion Traverse-------------------\n";
    cout << "Binary Tree First Order Traverse 1:\n";
    PreOrderTranverse_1(T, TreeTransOperator);
    cout << endl << "Binary Tree First Order Traverse 2:\n";
    PreOrderTranverse_2(T, TreeTransOperator);
    cout << endl << "Binary Tree Middle Order Traverse 1:\n";
    InOrderTranverse_1(T, TreeTransOperator);
    cout << endl << "Binary Tree Middle Order Traverse 2:\n";
    InOrderTranverse_2(T, TreeTransOperator);
    cout << endl << "Binary Tree Post Order Traverse 1:\n";
    PostOrderTranverse_1(T, TreeTransOperator);
    cout << endl << "Binary Tree Post Order Traverse 2:\n";
    PostOrderTranverse_2(T, TreeTransOperator);
    cout << endl;
    return 0;
}

给出一个算例演示：

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
/*
One Example:
Input binary tree elements in order: (note: '.' means empty tree)
A B C . . D E . G . . F . . .
------------------Binary Recursion Traverse----------------------
Binary Tree First Order Traverse:
A B C D E G F
Binary Tree Middle Order Traverse:
C B E G D F A
Binary Tree Post Order Traverse:
C G E F D B A
------------------Binary NonRecursion Traverse-------------------
Binary Tree First Order Traverse 1:
A B C D E G F
Binary Tree First Order Traverse 2:
A B C D E G F
Binary Tree Middle Order Traverse 1:
C B E G D F A
Binary Tree Middle Order Traverse 2:
C B E G D F A
Binary Tree Post Order Traverse 1:
C G E F D B A
Binary Tree Post Order Traverse 2:
C G E F D B A
*/

二叉树

https://markstiff.github.io/数据结构/二叉树/

作者

Mark Stiff

发布于

2022-10-13

更新于

2024-01-21

许可协议

 

喜欢这篇文章？打赏一下作者吧

评论

  关注我

目录

分类

标签

Generative Model1
Latex3
Markdown1
二叉树1
人工智能1
体系结构1
图论2
字符串1
嵌入式2
嵌入式系统1
排序4
数字信号处理1
数学6
数据库系统1
数据结构16
数据结构与算法 - LeetCode1
概率论与数理统计 - 数学1
稀疏矩阵3
算法3
算法竞赛3
计算机原理4
软件工程1
×