-
数据结构——C++实现二叉搜索树，前中后序、层序迭代遍历配合仿函数
通过介绍二叉搜索树，到实现最基础的二叉树模型，四种迭代遍历方式。
结点模型
template<class Type> class binary_tree { /* 二叉树是由多个结点组成的，所以定义一个内部的结点类用于构建树 */ class BTNode { /* 不允许无参构造，因为编译器会对m_val采用默认构造，如果是int类型会导致随机值，可能造成问题 */ BTNode() = delete; public: /* 防止隐式类型转换 */ explicit BTNode(const Type& _val) : m_val(_val), m_left(nullptr), m_right(nullptr) {} Type m_val; BTNode* m_left; BTNode* m_right; }; /* 创建结点，如果new失败则抛异常，需要在调用的时候捕获 */ static BTNode* create_node(const Type& _val) { BTNode* newNode = new BTNode(_val); if (newNode == nullptr) { throw std::exception("create_node failed"); } return newNode; }- 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
二叉树遍历
前序遍历
/* 前中后须遍历，统一使用标记法，使得三种遍历代码结构相似，和层序也有点相似 如果用第一种方法，前序会跟后序相似，但是中序会有差别 同时通过传入function对象，使得遍历拿到结点后可以执行自定义操作 返回值为bool是为了确认是否继续往后遍历，比如find，找到后应该返回true，表示不再往后遍历的，树中保证值是唯一的 */ static void pre_order(BTNode* root, std::function<bool(BTNode*)> func) { /* 方法一 */ //if (root == nullptr) // return; //std::stack- 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
中序遍历
static void in_order(BTNode* root, std::function<bool(BTNode*)> func) { /* 方法一 */ //std::stack- 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
后序遍历
static void post_order(BTNode* root, std::function<bool(BTNode*)> func) { if (root == nullptr) return; std::stack<BTNode*> st; st.push(root); while (!st.empty()) { auto node = st.top(); if (node != nullptr) { /* 先将结点从栈中拿出，用来访问左右，之后再按顺序插入 */ st.pop(); /* 访问过，但是没处理，用空来标识 */ st.push(node); st.push(nullptr); /* 左右中，因此入栈顺序要是中右左 */ if (node->m_right) st.push(node->m_right); if (node->m_left) st.push(node->m_left); } else { st.pop(); node = st.top(); st.pop(); func(node); } } }- 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
层序遍历
static void level_order(BTNode* root, std::function<bool(BTNode*)> func) { /* 广度优先遍历 每次一个结点入队，要访问时出队，并且将该结点的左右结点入队 因为访问和操作次序要一致，因此不能用栈，栈是模拟递归的 */ if (root == nullptr) return; std::queue<BTNode*> q; q.push(root); BTNode* cur = root; while (!q.empty()) { cur = q.front(); q.pop(); func(cur); if(cur->m_left) q.push(cur->m_left); if (cur->m_right) q.push(cur->m_right); } }- 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
二分遍历
static BTNode* binary_search(BTNode* root, const Type& _val) { BTNode* cur = root; BTNode* parent = nullptr; while (cur) { if (cur->m_val == _val) return cur; parent = cur; if (cur->m_val > _val) { cur = cur->m_left; } else if (cur->m_val < _val) { cur = cur->m_right; } } return nullptr; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
增删查改实现
public: using iterator = BTNode * ; binary_tree() : m_root(nullptr) {} explicit binary_tree(const Type& _val) : m_root(create_node(_val)) {} ~binary_tree() { /* 遍历每一个结点逐一析构，return false表示不要提前结束 */ pre_order(m_root, [](BTNode* node) {delete node; return false; }); } void insert(const Type& _val) { BTNode* newNode = nullptr; try { newNode = create_node(_val); } catch (const std::exception& exp) { std::cout << exp.what() << std::endl; return; } /* 目前为空树 */ if (m_root == nullptr) { m_root = newNode; return; } BTNode* cur = m_root; BTNode* parent = nullptr; while (cur) { if (cur->m_val == _val) return; parent = cur; if (cur->m_val > _val) { cur = cur->m_left; } else if (cur->m_val < _val) { cur = cur->m_right; } } cur = newNode; if (parent->m_val > _val) parent->m_left = cur; else parent->m_right = cur; } void erase(const Type& _val) { BTNode* cur = m_root; BTNode* parent = nullptr; while (cur) { if (cur->m_val == _val) break; parent = cur; if (cur->m_val > _val) { cur = cur->m_left; } else if (cur->m_val < _val) { cur = cur->m_right; } } if (cur == nullptr) return; /* 分三种情况：左为空，右为空，都为空 */ BTNode* left = cur->m_left; BTNode* right = cur->m_right; if (left == nullptr) { if (cur == m_root) { m_root = cur->m_right; } if (parent->m_right == cur) { parent->m_right = cur->m_right; } else { parent->m_left = cur->m_right; } delete cur; } else if (right == nullptr) { if (cur == m_root) { m_root = cur->m_left; } if (parent->m_right == cur) { parent->m_right = cur->m_left; } else { parent->m_left = cur->m_left; } delete cur; } else { /* 左右都不为空，要找左树的最大结点或右树的最小结点 比如找到左树的最大结点后，交换该结点和cur的值，之后重新链接，最后删除该最大结点 */ /* 要记录目标结点的父结点，因为要判断目标结点是父结点的左还是右，才能正确链接 */ auto minLeft = cur->m_left; auto minLeftParent = cur; while (minLeft->m_right) { minLeftParent = minLeft; minLeft = minLeft->m_right; } cur->m_val = minLeft->m_val; if (minLeftParent->m_left == minLeft) { minLeftParent->m_left = minLeft->m_left; } else { minLeftParent->m_right = minLeft->m_right; } delete minLeft; } } iterator find(const Type& _val) { return binary_search(m_root, _val); } iterator begin() { return m_root; } private: BTNode* m_root; };- 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
运算符重载
/* 重载流提取 */ friend std::ostream& operator<<(std::ostream& out, binary_tree& tree) { auto print = [](BTNode* node) -> bool { std::cout << node->m_val << ' '; return false; }; std::cout << "前序遍历："; tree.pre_order(tree.m_root, print); std::cout << std::endl; std::cout << "中序遍历："; tree.in_order(tree.m_root, print); std::cout << std::endl; std::cout << "后序遍历："; tree.post_order(tree.m_root, print); std::cout << std::endl; std::cout << "层序遍历："; tree.level_order(tree.m_root, print); std::cout << std::endl; return out; }- 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
测试代码
void tree_test() { binary_tree<int> tree; std::vector<int> arr{ 8,3,10,1,6,14,4,7,13,0,16 }; /* 8 3 1 0 6 4 7 10 14 13 16 0 1 3 4 6 7 8 10 13 14 16 0 1 4 7 6 3 13 16 14 10 8 8 3 10 1 6 14 0 4 7 13 16 */ for (auto& num : arr) { tree.insert(num); } std::cout << tree << std::endl; tree.erase(6); std::cout << tree << std::endl; if (tree.find(8)) { std::cout << "找到了\n"; } tree.erase(8); if (tree.find(8)) { std::cout << "找到了\n"; } std::cout << tree << std::endl; }- 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
但是二叉搜索树有一个缺点，在遇到插入的值都是比树中所有值都大的结点时，会一直往右插入，从而形成一个单链表。因而失去了二叉树的优势。平衡二叉树（AVL树）可以解决这个问题。
-
相关阅读:
正交试验测试用例设计及工具推荐
LeetCode：342. 数位和相等数对的最大和（C++）
java-net-php-python-ssmpoco图片社区交流网演示录像2019查重（论文先不写计算机毕业设计程序
仙人掌之歌——投石问路（1）
各GIS软件添加天地图方式
jar包不能够直接运行的解决办法
C++day7模板、异常、auto关键字、lambda表达式、数据类型转换、STL、list、文件操作
Java 进阶多线程(一)
可用于智能客服的完全开源免费商用的知识库项目
中国各朝代行政区划、点位矢量数据下载与背景介绍
- 原文地址：https://blog.csdn.net/qq_51963665/article/details/132834565
