数据结构与算法

前言

写在前面的话：数据结构与算法。

  1. 对于初识数据结构的小伙伴们，鉴于后面的数据结构的构建会使用到同tag前面的内容，包括具体数据结构的应用，所使用到的数据结构，也是自己构建的，未使用系统的库文件，因此，建议这类小伙伴们按顺序进行学习；

  2. 对于想查询有关资料的小伙伴们，可以选择性地浏览。希望大家都能有所收获～

二叉树构建

上一篇笔者介绍了二叉树的一些基本概念，本节主要介绍如何构建二叉树。

二叉树的构建相比前面学的数据结构更为复杂，代码中提供了详尽的注释，请读者细细体会。

二叉树中最重要的三种算法：

  • 先序遍历
  • 中序遍历
  • 后序遍历

下面的BinNode.h描述了二叉树结点具有的基本结构：

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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
/*
 *
 * 作者：易果啥笔
 * 时间：2021.8.20
 * 内容：二叉树结点模版类
 *
 *
 */

#ifndef STACK_BINNODE_H
#define STACK_BINNODE_H

#include <cstdlib>
#include "Queue.h"
#include "Stack.h"
/******************************************************************************************
* BinNode状态与性质的判断
******************************************************************************************/
#define IsRoot(x) ( ! ( (x).parent ) )
#define IsLChild(x) ( ! IsRoot(x) && ( & (x) == (x).parent->lc ) )
#define IsRChild(x) ( ! IsRoot(x) && ( & (x) == (x).parent->rc ) )
#define HasParent(x) ( ! IsRoot(x) )
#define HasLChild(x) ( (x).lc )
#define HasRChild(x) ( (x).rc )
#define HasChild(x) ( HasLChild(x) || HasRChild(x) ) //至少拥有一个孩子
#define HasBothChild(x) ( HasLChild(x) && HasRChild(x) ) //同时拥有两个孩子
#define IsLeaf(x) ( ! HasChild(x) )

/******************************************************************************************
* 与BinNode具有特定关系的节点及指针
******************************************************************************************/
#define sibling( p ) ( IsLChild( * (p) ) ? (p)->parent->rc : (p)->parent->lc ) /*兄弟*/
#define uncle( x ) ( sibling( (x)->parent ) ) /*叔叔*/
#define FromParentTo( x ) /*来自父亲的引用*/ ( IsRoot(x) ? _root : ( IsLChild(x) ? (x).parent->lc : (x).parent->rc ) )
#define stature(p) ((p) ? (p)->height : -1) //其余BST中节点的高度（NUll视作空树，对应于-1）

template <typename T> struct BinNode { //二叉树节点模板类
// 成员
    T data; //数值
    BinNode<T>* parent;
    BinNode<T>* lc;
    BinNode<T>* rc; //父节点及左、右孩子
    int height; //高度（通用）
// 构造函数
    BinNode() :
            parent (nullptr) , lc (nullptr) , rc ( nullptr ), height ( 0 ) { }
    BinNode ( T e, BinNode<T>* p = nullptr, BinNode<T>* lc = nullptr, BinNode<T>* rc = nullptr,
              int h = 0, int l = 1) :
            data ( e ), parent ( p ), lc ( lc ), rc ( rc ), height ( h ){ }
// 操作接口
    BinNode<T>* succ(); //取当前结点的直接后继
    BinNode<T>* insertAsLC ( T const & ); //作为当前节点的左孩子插入新节点
    BinNode<T>* insertAsRC ( T const & ); //作为当前节点的右孩子插入新节点
    void travLevel ( void (* visit)(T&) ); //子树层次遍历
    void travPre ( void (* visit)(T&) ); //子树先序遍历
    void travIn ( void (* visit)(T&) ); //子树中序遍历
    void travPost ( void (* visit)(T&) ); //子树后序遍历
};


/*
 *
 * 作者：易果啥笔
 * 时间：2021.8.21
 * 内容：二叉树结点模版类接口的实现
 *
 *
 */

template <typename T> BinNode<T>* BinNode<T>::insertAsLC ( T const& e )
{ return lc = new BinNode ( e, this ); } //将e作为当前节点的左孩子插入二叉树

template <typename T> BinNode<T>* BinNode<T>::insertAsRC ( T const& e )
{ return rc = new BinNode ( e, this ); } //将e作为当前节点的右孩子插入二叉树

template <typename T> BinNode<T>* BinNode<T>::succ() { //定位节点v的直接后继
    BinNode<T> *s = this; //记录后继的临时变量
    if (rc) { //若有右孩子，则直接后继必在右子树中，具体地就是
        s = rc; //右子树中
        while (HasLChild (*s)) s = s->lc; //最靠左（最小）的节点
    } else { //否则，直接后继应是“将当前节点包含于其左子树中的最低祖先”，具体地就是
        while (IsRChild (*s)) s = s->parent; //逆向地沿右向分支，不断朝左上方移动
        s = s->parent; //最后再朝右上方移动一步，即抵达直接后继（如果存在）
    }
    return s;
}
/*
 *
 * 先序遍历
 *
 */

//递归版
template <typename T>
void travPre_R(BinNode<T>* x,void (* visit)(T&)){ //递归版
    if(!x){ return;}
    visit(x->data);
    travPost_R(x->lc,visit);
    travPost_R(x->rc,visit);

}
//迭代版1
template <typename T>
void travPre_I1(BinNode<T>* x,void (* visit)(T&)){
    Stack<BinNode<T>*> S;
    if(x){S.push(x); };
    while(!S.Empty()){
        x = S.pop();
        visit(x->data);
        if(HasRChild(*x)) S.push(x->rc);
        if(HasLChild(*x)) S.push(x->lc);
    }
}

//迭代版2
//从当前节点出发，沿左分支不断深入，直至没有左分支的节点；沿途节点遇到后立即访问
template <typename T>
static void visitAlongVine ( BinNode<T>* x, void (* visit)(T&), Stack<BinNode<T>*>& S ) {
    while ( x ) {
       visit ( x->data ); //访问当前节点
       S.push ( x->rc ); //右孩子入栈暂存（可优化：通过判断，避免空的右孩子入栈）
       x = x->lc;  //沿左分支深入一层
    }
}
template <typename T>
void travPre_I2 ( BinNode<T>* x, void (* visit)(T&) ) {
    Stack<BinNode<T>*> S; //辅助栈
    while ( true ) {
       visitAlongVine ( x, visit, S ); //从当前节点出发，逐批访问
       if ( S.Empty() ) break; //直到栈空
       x = S.pop(); //弹出下一批的起点
    }
}

template <typename T>
void BinNode<T>::travPre ( void (* visit)(T&) ) { //二叉树先序遍历算法统一入口
    switch ( rand() % 3 ) { //此处暂随机选择以做测试，共三种选择
        case 0: travPre_I1 ( this, visit ); break; //迭代版1
        case 1: travPre_I2 ( this, visit ); break; //迭代版2
        default: travPre_R ( this, visit ); break; //递归版
    }
}

/*
 *
 * 中序遍历
 *
 */

//递归版
template <typename T> //元素类型、操作器
void travIn_R(BinNode<T>* x,void (* visit)(T&)){
    if(!x){ return;}
    travPost_R(x->lc,visit);
    visit(x->data);
    travPost_R(x->rc,visit);

}

//迭代版1
template <typename T> //从当前节点出发，沿左分支不断深入，直至没有左分支的节点
static void goAlongVine ( BinNode<T>* x, Stack<BinNode<T>*>& S ) {
    while ( x ) { S.push ( x ); x = x->lc; } //当前节点入栈后随即向左侧分支深入，迭代直到无左孩子
}
template <typename T>
void travIn_I1 ( BinNode<T>* x, void (* visit)(T&) ) {
    Stack<BinNode<T>*> S; //辅助栈
    while ( true ) {
       goAlongVine ( x, S ); //从当前节点出发，逐批入栈
       if ( S.Empty() ) break; //直至所有节点处理完毕
       x = S.pop(); visit ( x->data ); //弹出栈顶节点并访问之
       x = x->rc; //转向右子树
    }
}

//迭代版2
template <typename T>
void travIn_I2 ( BinNode<T>* x, void (* visit)(T&) ) {
    Stack<BinNode<T>*> S; //辅助栈
    while ( true )
       if ( x ) {
          S.push ( x ); //根节点进栈
          x = x->lc; //深入遍历左子树
       } else if ( !S.Empty() ) {
          x = S.pop(); //尚未访问的最低祖先节点退栈
          visit ( x->data ); //访问该祖先节点
          x = x->rc; //遍历祖先的右子树
       } else
          break; //遍历完成
}

//迭代版3
template <typename T>
void travIn_I3 ( BinNode<T>* x, void (* visit)(T&) ) {
    bool backtrack = false; //前一步是否刚从左子树回溯——省去栈，仅O(1)辅助空间
    while ( true )
       if ( !backtrack && HasLChild ( *x ) ) //若有左子树且不是刚刚回溯，则
          x = x->lc; //深入遍历左子树
       else { //否则——无左子树或刚刚回溯（相当于无左子树）
          visit ( x->data ); //访问该节点
          if ( HasRChild ( *x ) ) { //若其右子树非空，则
             x = x->rc; //深入右子树继续遍历
             backtrack = false; //并关闭回溯标志
          } else { //若右子树空，则
             if ( ! ( x = x->succ() ) ) break; //回溯（含抵达末节点时的退出返回）
             backtrack = true; //并设置回溯标志
          }
       }
}

//二叉树中序遍历算法统一入口
template <typename T>
void BinNode<T>::travIn ( void (* visit)(T&) ) {
    switch ( rand() % 4 ) { //此处暂随机选择以做测试，共四种选择
       case 0: travIn_I1 ( this, visit ); break; //迭代版1
       case 1: travIn_I2 ( this, visit ); break; //迭代版2
       case 2: travIn_I3 ( this, visit ); break; //迭代版3
       default: travIn_R ( this, visit ); break; //递归版
    }
 }

/*
*
* 后序遍历
*
*/

//递归版
template <typename T> //元素类型、操作器
void travPost_R(BinNode<T>* x,void (* visit)(T&)){
    if(!x){ return;}
    travPost_R(x->lc,visit);
    travPost_R(x->rc,visit);
    visit(x->data);
}

//迭代版
template <typename T> //在以S栈顶节点为根的子树中，找到最高左侧可见叶节点
static void gotoLeftmostLeaf ( Stack<BinNode<T>*>& S ) { //沿途所遇节点依次入栈
    while ( BinNode<T>* x = S.top() ) //自顶而下，反复检查当前节点（即栈顶）
       if ( HasLChild ( *x ) ) { //尽可能向左
          if ( HasRChild ( *x ) ) S.push ( x->rc ); //若有右孩子，优先入栈
          S.push ( x->lc ); //然后才转至左孩子
       } else //实不得已
          S.push ( x->rc ); //才向右
    S.pop(); //返回之前，弹出栈顶的空节点
}

template <typename T>
void travPost_I ( BinNode<T>* x, void (* visit)(T&) ) { //二叉树的后序遍历（迭代版）
    Stack<BinNode<T>*> S; //辅助栈
    if ( x ) S.push ( x ); //根节点入栈
    while ( !S.Empty() ) { //x始终为当前节点
       if ( S.top() != x->parent ) ////若栈顶非x之父（而为右兄）
          gotoLeftmostLeaf ( S ); //则在其右兄子树中找到HLVFL（相当于递归深入）
       x = S.pop(); visit ( x->data ); //弹出栈顶（即前一节点之后继），并访问之
    }
}


template <typename T>
void BinNode<T>::travPost ( void (* visit)(T&) ) { //二叉树中序遍历算法统一入口
    switch ( rand() % 2 ) { //此处暂随机选择以做测试
        case 0: travPost_I ( this, visit ); break; //迭代版
        default: travPost_R ( this, visit ); break; //递归版
    }
}

/*
 *
 * 层次遍历
 *
 */

template<typename T>
void BinNode<T>::travLevel(void (* visit)(T&)) { //二叉树层次遍历算法
    Queue<BinNode<T>*> Q;  //辅助队列
    Q.enqueue(this); //根结点入队
    while (!Q.empty()){
        BinNode<T>* x = Q.dequeue();
        visit(x->data);
        if(HasLChild(*x)) Q.enqueue(x->lc);
        if(HasRChild(*x)) Q.enqueue(x->rc);
    }
}

#endif //STACK_BINNODE_H

在该算法中，对于先序遍历，中序遍历，后序遍历，笔者提供了多种实现（迭代+递归），请读者细细体会不同算法间有何相同，相异之处，效率是否相同。

此外，算法中还包含了前面学过的Stack.h，Queue.h等头文件，具体可参考本tag的其他文章。

接着，来构建二叉树结点之间的逻辑关系：

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
/*
 *
 * 作者：易果啥笔
 * 时间：2021.8.21
 * 内容：二叉树模版类
 *
 *
 */

#ifndef STACK_BINTREE_H
#define STACK_BINTREE_H
#include "BinNode.h"

template <typename T> class BinTree {
    protected:
        int _size_; BinNode<T>* _root; //规模、根节点
        virtual int updateHeight ( BinNode<T>* x ); //更新节点x的高度
        void updateHeightAbove ( BinNode<T>* x ); //更新节点x及其祖先的高度
    public:
        BinTree() : _size_ ( 0 ), _root ( NULL ) { } //构造函数
        ~BinTree() { if ( 0 < _size_ ) remove ( _root ); } //析构函数
        int size() const { return _size_; } //规模
        bool empty() const { return !_root; } //判空
        BinNode<T>* root() const { return _root; } //树根
        BinNode<T>* insert ( T const & ); //插入根节点
        BinNode<T>* insert ( T const &, BinNode<T>* ); //插入左孩子
        BinNode<T>* insert ( BinNode<T>*, T const & ); //插入右孩子
        int remove ( BinNode<T>* ); //子树删除
        BinTree<T>* secede ( BinNode<T>* ); //子树分离
        void travLevel ( void (* visit)(T&) ) { if ( _root ) _root->travLevel ( visit ); } //层次遍历
        void travPre ( void (* visit)(T&) ) { if ( _root ) _root->travPre ( visit ); } //先序遍历
        void travIn ( void (* visit)(T&) ) { if ( _root ) _root->travIn ( visit ); } //中序遍历
        void travPost ( void (* visit)(T&) ) { if ( _root ) _root->travPost ( visit ); } //后序遍历
        bool operator< ( BinTree<T> const& t ) //比较器
        { return _root && t._root && lt ( _root, t._root ); }
        bool operator== ( BinTree<T> const& t ) //判等器
        { return _root && t._root && ( _root == t._root ); }
 }; //BinTree

/*
*
* 作者：易果啥笔
* 时间：2021.8.21
* 内容：二叉树模版类接口的实现
*
*
*/

template <typename T> int BinTree<T>::updateHeight ( BinNode<T>* x ) //更新节点x高度
 { return x->height = 1 + max ( stature ( x->lc ), stature ( x->rc ) ); } //具体规则，因树而异

template <typename T> void BinTree<T>::updateHeightAbove ( BinNode<T>* x ) //更新高度
 { while ( x ) { updateHeight ( x ); x = x->parent; } } //从x出发，覆盖历代祖先。可优化

template <typename T> BinNode<T>* BinTree<T>::insert ( T const& e )
 { _size_ = 1; return _root = new BinNode<T> ( e ); } //将e当作根节点插入空的二叉树

template <typename T> BinNode<T>* BinTree<T>::insert ( T const& e, BinNode<T>* x )
 { _size_++; x->insertAsLC ( e ); updateHeightAbove ( x ); return x->lc; } //e插入为x的左孩子

template <typename T> BinNode<T>* BinTree<T>::insert ( BinNode<T>* x, T const& e )
 { _size_++; x->insertAsRC ( e ); updateHeightAbove ( x ); return x->rc; } //e插入为x的右孩子

template <typename T> //删除二叉树中位置x处的节点及其后代，返回被删除节点的数值
int BinTree<T>::remove ( BinNode<T>* x ) { //assert: x为二叉树中的合法位置
    FromParentTo ( *x ) = NULL; //切断来自父节点的指针
    updateHeightAbove ( x->parent ); //更新祖先高度
    int n = removeAt ( x ); _size_ -= n; return n; //删除子树x，更新规模，返回删除节点总数
}

template <typename T> //删除二叉树中位置x处的节点及其后代，返回被删除节点的数值
static int removeAt ( BinNode<T>* x ) { //assert: x为二叉树中的合法位置
    if ( !x ) return 0; //递归基：空树
    int n = 1 + removeAt ( x->lc ) + removeAt ( x->rc ); //递归释放左、右子树
    free ( x ); return n; //释放被摘除节点，并返回删除节点总数
 }

template <typename T> //二叉树子树分离算法：将子树x从当前树中摘除，将其封装为一棵独立子树返回
BinTree<T>* BinTree<T>::secede ( BinNode<T>* x ) { //assert: x为二叉树中的合法位置
    FromParentTo ( *x ) = NULL; //切断来自父节点的指针
    updateHeightAbove ( x->parent ); //更新原树中所有祖先的高度
    BinTree<T>* S = new BinTree<T>; S->_root = x; x->parent = NULL; //新树以x为根
    S->_size_ = size(); _size_ -= S->_size_; return S; //更新规模，返回分离出来的子树
}

#endif //STACK_BINTREE_H

这样，二叉树便构建完毕。我们用一个main.cpp来测试一下：

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
/*
 *
 * 作者：易果啥笔
 * 时间：2021.8.21
 * 内容：二叉树模版类的使用
 *
 *
 */

#include <iostream>
#include "BinTree.h"


template<typename T> void print(T a){
    std::cout<<a<<"  ";
}

int main(){
    //构建二叉树
    BinTree<int> binTree;

    //添加数据
    binTree.insert(1);
    binTree.insert(binTree.root(),3);
    binTree.insert(2,binTree.root());
    binTree.insert(4,binTree.root()->succ());
    binTree.insert(binTree.root()->succ(),5);
    binTree.insert(6,binTree.root()->succ()->succ());
    binTree.insert(binTree.root()->succ()->succ(),7);

    //remove()删除指定结点及其子树
    binTree.remove(binTree.root()->succ()->succ());
    //四种遍历方式
    cout<<"层次遍历：";
    binTree.travLevel(print);
    cout<<endl;
    cout<<"先序遍历：";
    binTree.travPre(print);
    cout<<endl;
    cout<<"中序遍历：";
    binTree.travIn(print);
    cout<<endl;
    cout<<"后序遍历：";
    binTree.travPost(print);
    cout<<endl;
    //size()返回二叉树结点总数
    cout<<"该二叉树共有"<<binTree.size()<<"个结点."<<endl;
    //secede()分离子树
    BinTree<int>* S = binTree.secede(binTree.root()->succ());
    S->travLevel(print);

    return 0;
}

本文作者：LuoYing @ 小小白的笔记屋

本文链接：https://luoying.netlify.app/2021/08/20/fon3vuca/

本文标题：数据结构与算法之-----二叉树（二）

本文版权：本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！