第95篇 C++数据结构（五）树
- 1.树的简介
-
- 1.1.树的特点
- 1.2.树的相关名词
- 1.3.二叉树
- 2.节点
- 3.实现
-
- 3.1.变量
- 3.2.方法
- 4.测试
-
- 4.1.测试代码
- 4.2.输出
- 5.实现代码
- 6.总结
有许多介绍树的博文，这里不做过多的介绍，本文注重于二叉树的相关操作，且实现的相当于是一颗有序二叉树。
1.树的简介 树形结构是一种重要的非线性数据结构。其中树和二叉树最为常用，直观看来树是以分支关系定义的层次结构。树形结构是我们平时比较熟悉的，比如文件夹目录、公司组织关系等。在计算机领域也得到广泛的应用，编译程序就是以树来表示源程序的语法结构。
1.1.树的特点 树（tree）是一种抽象数据类型（ADT）或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>=1）个有限节点组成一个具有层次关系的集合。
? ?（1）每个节点有 0 或 多个 子节点；
? ?（2）没有父节点的节点称为根节点；
? ?（3）每一个非根节点有且仅有一个父节点；
? ?（4）除了根节点外，每个子节点可以分为多个不相交的子树；
1.2.树的相关名词
? ?（1）节点的度：一个节点含有的子树的个数（数节点的子节点数即可）；
? ?（2）树的度：一棵树中，最大的节点的度称为树的度；
? ?（3）叶节点或终端节点：度为 0 的节点；
? ?（4）父节点：若一个节点含有子节点，则该节点称为其子节点的父节点；
? ?（5）子节点：一个节点含有的子树的根节点称为该节点的子节点；
? ?（6）兄弟节点：具有相同父节点的节点
? ?（7）节点的层次：从根节点开始定义，根为第 1 层，根的子节点为第 2 层，以此类推；
? ?（8）树的高度或深度：树种节点的最大层次
? ?（9）堂兄弟节点：父节点在同一层的节点互为堂兄弟
? ?（10）节点的祖先：从根到该节点所经分支上的所有点
? ?（11）子孙：以某节点为根的子树中任一节点都称为该节点的子孙
? ?（12）森林：由 m（m>0）棵互不相交的树的集合称为森林
1.3.二叉树
二叉树：每个节点最多含有两个子树的树称为二叉树
完全二叉树：对于一课二叉树，假设其深度为d（d>1）。除了第d层外，其它各层的节点数均已达最大值，且第d层所有节点从左向右连续地紧密排列；
平衡二叉树（AVL树）：当且仅当任何两棵子树的高度差不大于1的二叉树；
排序二叉树（二叉查找树 Binary Search Tree， 也称二叉搜索树、有序二叉树）；
2.节点 实现的是一颗排序二叉树，二叉树其实也可以用数组来表示，不过数组表示，对于任何形式的数据结构来说，插入删除之类的都麻烦，因此采用链表形式较好，在此定义一个节点：
template
struct TreeNode
{
using _TreeNodePtr = TreeNode*;
_dataType m_value;
_TreeNodePtr m_leftChild;
_TreeNodePtr m_rightChild;
TreeNode() : m_value(_dataType()), m_leftChild(nullptr), m_rightChild(nullptr) {}
TreeNode(_dataType value) : m_value(value), m_leftChild(nullptr), m_rightChild(nullptr) {}
TreeNode(_dataType value, _TreeNodePtr leftChild, _TreeNodePtr rightChild)
: m_value(value), m_leftChild(leftChild), m_rightChild(rightChild) {}
};
节点包含内容为，节点数据，节点左孩子，节点右孩子，为了便于可能遇到的构造需求，这里定义三个构造函数。
3.实现 3.1.变量 因为实现的排序树支持插入重复数据，因此替换数据的时候有可能替换很多个，而替换是通过删除于添加完成，因此使用removeCount来统计删除次数，这样删除目标数据几次，就添加替换数据几次就好了。
| 变量名 | 类型 | 属性 | 说明 |
|---|---|---|---|
| m_root | _TreeNodePtr | 私有 | 根节点 |
| m_len | size_t | 私有 | 树的节点数 |
| removeCount = 0 | int | 私有 | 统计删除次数 |
比如添加数据的函数add(_dataType value),递归实现的话需要传根节点，但是根节点是不给外面调用的，因此就写一个私有的add(_TreeNodePtr root, _dataType value)，可传根节点。
| 方法名 | 返回类型 | 参数 | 属性 | 说明 |
|---|---|---|---|---|
| Tree() | - | - | 公有 | 缺省构造 |
| Tree() | - | const Tree& t | 公有 | 拷贝构造 |
| operator = () | Tree& | const Tree& t | 公有 | =运算符重载 |
| ~Tree() | - | - | 公有 | 析构 |
| isEmpty() const | bool | - | 公有 | 判断树是否为空 |
| size() const | size_t | - | 公有 | 返回节点数 |
| add() | bool | _dataType value | 公有 | 添加数据 |
| remove() | bool | _dataType value | 公有 | 删除数据 |
| replace() | bool | _dataType target, _dataType value | 公有 | 替换数据 |
| search() | bool | _dataType value | 公有 | 查找数据 |
| clear() | bool | - | 公有 | 清空数据 |
| depth() | size_t | - | 公有 | 返回树的深度 |
| numberOfLeaves() | size_t | - | 公有 | 计算叶子数 |
| preorderTraversal() | void | - | 公有 | 先序遍历递归实现 |
| midorderTraversal() | void | - | 公有 | 中序遍历递归实现 |
| postorderTraversal() | void | - | 公有 | 后序遍历递归实现 |
| preorderTraversalIterate() | void | - | 公有 | 先序遍历迭代实现 |
| midorderTraversalIterate() | void | - | 公有 | 中序遍历迭代实现 |
| postorderTraversalIterate() | void | - | 公有 | 后序遍历迭代实现 |
| levelTraversal() | void | - | 公有 | 层次遍历 |
| add() | bool | _TreeNodePtr& root, _dataType value | 私有 | 添加数据 |
| remove() | bool | _TreeNodePtr& root, _dataType value | 私有 | 删除数据 |
| changeNodeParent() | _TreeNodePtr& | _TreeNodePtr& rNode | 私有 | 返回需要删除的节点的父节点 |
| replace() | bool | _TreeNodePtr root, _dataType target, _dataType value | 私有 | 替换数据 |
| search() | bool | _TreeNodePtr root, _dataType value | 私有 | 查找数据 |
| copy() | void | _TreeNodePtr& leftRoot, _TreeNodePtr rightRoot | 私有 | 复制数据 |
| clear() | void | _TreeNodePtr& root | 私有 | 清除数据 |
| depth() | size_t | _TreeNodePtr root | 私有 | 计算深度 |
| numberOfLeaves() | size_t | _TreeNodePtr root | 私有 | 计算叶子节点数 |
| preorderTraversal() | void | _TreeNodePtr root | 私有 | 先序遍历 |
| midorderTraversal() | void | _TreeNodePtr root | 私有 | 中序遍历 |
| postorderTraversal() | void | _TreeNodePtr root | 私有 | 后序遍历 |
#include #include "Tree.h"void treeTest();
//11 9 10 4 5 3 14 13 15 11 9 10 4 5 3 14 13 15
int main()
{
treeTest();
return 0;
}void treeTest()
{
std::cout << "\n构造测试：" << std::endl;
Tree t;
int num(0);
int c = 18;
while (c-- > 0) {
std::cin >> num;
t.add(num);
}
std::cout << "先序遍历迭代：";
t.preorderTraversalIterate();
std::cout << "先序遍历递归：";
t.preorderTraversal();
std::cout << std::endl;
std::cout << "中序遍历迭代：";
t.midorderTraversalIterate();
std::cout << "中序遍历递归：";
t.midorderTraversal();
std::cout << std::endl;
std::cout << "后序遍历迭代：";
t.postorderTraversalIterate();
std::cout << "后序遍历递归：";
t.postorderTraversal();
std::cout << std::endl;
std::cout << "层次遍历：";
t.levelTraversal();
std::cout << "树的深度：" << t.depth() << std::endl;
std::cout << "树的叶子数：" << t.numberOfLeaves() << std::endl;
std::cout << "树的节点数：" << t.size() << std::endl;
std::cout << "\n拷贝构造函数测试：" << std::endl;
Tree t2 = t;
std::cout << "中序遍历迭代：";
t2.midorderTraversalIterate();
std::cout << "\n复制运算符测试：" << std::endl;
Tree t3;
t3 = t2;
std::cout << "中序遍历迭代：";
t3.midorderTraversalIterate();
std::cout << "\n添加数据12：" << std::endl;
t.add(12);
std::cout << "中序遍历迭代：";
t.midorderTraversalIterate();
std::cout << "\n删除数据11：" << std::endl;
t.remove(11);
std::cout << "中序遍历迭代：";
t.midorderTraversalIterate();
std::cout << "\n将数据13替换为11：" << std::endl;
t.replace(13, 11);
std::cout << "中序遍历迭代：";
t.midorderTraversalIterate();
std::cout << "\n查找数据13：" << std::endl;
if (t.search(13)) {
std::cout << "13存在！" << std::endl;
}
else {
std::cout << "13不存在！" << std::endl;
} std::cout << "\n查找数据11：" << std::endl;
if (t.search(11)) {
std::cout << "11存在！" << std::endl;
}
else {
std::cout << "11不存在！" << std::endl;
} std::cout << "\n判断树是否为空：" << std::endl;
if (t.isEmpty()) {
std::cout << "树没有数据！" << std::endl;
}
else {
std::cout << "树有数据！" << std::endl;
} std::cout << "\n清空：" << std::endl;
t.clear();
if (t.isEmpty()) {
std::cout << "树没有数据！" << std::endl;
}
else {
std::cout << "树有数据！" << std::endl;
}
}
4.2.输出
构造测试：
11 9 10 4 5 3 14 13 15 11 9 10 4 5 3 14 13 15
先序遍历迭代：11, 9, 4, 3, 3, 5, 4, 5, 10, 9, 10, 14, 13, 11, 13, 15, 14, 15,
先序遍历递归：11, 9, 4, 3, 3, 5, 4, 5, 10, 9, 10, 14, 13, 11, 13, 15, 14, 15,
中序遍历迭代：3, 3, 4, 4, 5, 5, 9, 9, 10, 10, 11, 11, 13, 13, 14, 14, 15, 15,
中序遍历递归：3, 3, 4, 4, 5, 5, 9, 9, 10, 10, 11, 11, 13, 13, 14, 14, 15, 15,
后序遍历迭代：3, 3, 4, 5, 5, 4, 9, 10, 10, 9, 11, 13, 13, 14, 15, 15, 14, 11,
后序遍历递归：3, 3, 4, 5, 5, 4, 9, 10, 10, 9, 11, 13, 13, 14, 15, 15, 14, 11,
层次遍历：11, 9, 14, 4, 10, 13, 15, 3, 5, 9, 10, 11, 13, 14, 15, 3, 4, 5,
树的深度：5
树的叶子数：9
树的节点数：18拷贝构造函数测试：
中序遍历迭代：3, 3, 4, 4, 5, 5, 9, 9, 10, 10, 11, 11, 13, 13, 14, 14, 15, 15,复制运算符测试：
中序遍历迭代：3, 3, 4, 4, 5, 5, 9, 9, 10, 10, 11, 11, 13, 13, 14, 14, 15, 15,添加数据12：
中序遍历迭代：3, 3, 4, 4, 5, 5, 9, 9, 10, 10, 11, 11, 12, 13, 13, 14, 14, 15, 15,删除数据11：
中序遍历迭代：3, 3, 4, 4, 5, 5, 9, 9, 10, 10, 12, 13, 13, 14, 14, 15, 15,将数据13替换为11：
中序遍历迭代：3, 3, 4, 4, 5, 5, 9, 9, 10, 10, 11, 11, 12, 14, 14, 15, 15,查找数据13：
13不存在！查找数据11：
11存在！判断树是否为空：
树有数据！清空：
树没有数据！5.实现代码
#pragma once
#ifndef _TREE_H_
#define _TREE_H_#include
#include
#include
#include template
struct TreeNode
{
using _TreeNodePtr = TreeNode*;
_dataType m_value;
_TreeNodePtr m_leftChild;
_TreeNodePtr m_rightChild;
TreeNode() : m_value(_dataType()), m_leftChild(nullptr), m_rightChild(nullptr) {}
TreeNode(_dataType value) : m_value(value), m_leftChild(nullptr), m_rightChild(nullptr) {}
TreeNode(_dataType value, _TreeNodePtr leftChild, _TreeNodePtr rightChild)
: m_value(value), m_leftChild(leftChild), m_rightChild(rightChild) {}
};
template
class Tree
{
using _TreeNodePtr = TreeNode<_dataType>*;
public:
Tree() : m_root(nullptr), m_len(0) {} Tree(const Tree& t)
{
copy(this->m_root, t.m_root);
m_len = t.m_len;
} Tree& operator = (const Tree& t)
{
if (!this->isEmpty()) {
this->clear();
}copy(this->m_root, t.m_root);
m_len = t.m_len;
return *this;
} ~Tree()
{
clear();
} bool isEmpty() const
{
return m_root == nullptr;
} size_t size() const
{
return m_len;
} bool add(_dataType value) //添加数据
{
return add(m_root, value);
} bool remove(_dataType value) //删除数据
{
return remove(m_root, value);
} bool replace(_dataType target, _dataType value) //替换数据
{
return replace(m_root, target, value);
} bool search(_dataType value)
{
return search(m_root, value);
} bool clear()
{
clear(m_root);
return true;
} size_t depth()
{
return depth(m_root);
} size_t numberOfLeaves()
{
return numberOfLeaves(m_root);
} void preorderTraversal()
{
preorderTraversal(m_root);
} void midorderTraversal()
{
midorderTraversal(m_root);
} void postorderTraversal()
{
postorderTraversal(m_root);
} void preorderTraversalIterate()
{
std::stack<_TreeNodePtr> treeNodeStack;
_TreeNodePtr root = m_root;
while (root || !treeNodeStack.empty()) {
if (root) {
std::cout << root->m_value << ", ";
treeNodeStack.push(root);
root = root->m_leftChild;
}
else {
root = treeNodeStack.top();
treeNodeStack.pop();
root = root->m_rightChild;
}
}
std::cout << std::endl;
} void midorderTraversalIterate()
{
std::stack<_TreeNodePtr> treeNodeStack;
_TreeNodePtr root = m_root;
while (root || !treeNodeStack.empty()) {
if (root) {
treeNodeStack.push(root);
root = root->m_leftChild;
}
else {
root = treeNodeStack.top();
treeNodeStack.pop();
std::cout << root->m_value << ", ";
root = root->m_rightChild;
}
}
std::cout << std::endl;
} void postorderTraversalIterate()
{
std::stack<_TreeNodePtr> treeNodeStack;
_TreeNodePtr root = m_root;
_TreeNodePtr record = nullptr;
while (root || !treeNodeStack.empty()) {
if (root) {
treeNodeStack.push(root);
root = root->m_leftChild;
}
else {
root = treeNodeStack.top();
if (root->m_rightChild && root->m_rightChild != record) {
root = root->m_rightChild;
}
else {
treeNodeStack.pop();
std::cout << root->m_value << ", ";
record = root;
root = nullptr;
}
}
}
std::cout << std::endl;
} void levelTraversal()
{
std::queue<_TreeNodePtr> treeNodeStack;
_TreeNodePtr root = m_root;
treeNodeStack.push(root);
while (!treeNodeStack.empty()) {
root = treeNodeStack.front();
treeNodeStack.pop();
std::cout << root->m_value << ", ";
if (root->m_leftChild) {
treeNodeStack.push(root->m_leftChild);
}
if (root->m_rightChild) {
treeNodeStack.push(root->m_rightChild);
}
}
std::cout << std::endl;
}private:
_TreeNodePtr m_root;
//根节点
size_t m_len;
int removeCount = 0;
//统计删除次数 bool add(_TreeNodePtr& root, _dataType value)
{
if (root) {
if (value >= root->m_value) {
return add(root->m_rightChild, value);
}
else {
return add(root->m_leftChild, value);
}
}
else {
root = new TreeNode<_dataType>(value);
m_len++;
}return true;
} bool remove(_TreeNodePtr& root, _dataType value)
{
if (root) {
if (value =https://www.it610.com/article/= root->m_value) {
removeCount++;
if (root->m_rightChild) {
if (root->m_rightChild->m_leftChild) {
_TreeNodePtr cNodeParent = changeNodeParent(root->m_rightChild);
_TreeNodePtr cNode = cNodeParent->m_leftChild;
std::swap(root->m_value, cNode->m_value);
cNodeParent->m_leftChild = cNode->m_rightChild;
delete cNode;
cNode = nullptr;
return (remove(root, value) || true);
}
else {
_TreeNodePtr r = root;
root->m_rightChild->m_leftChild = root->m_leftChild;
root = root->m_rightChild;
delete r;
r = nullptr;
return (remove(root, value) || true);
}
}
else if (root->m_leftChild) {
_TreeNodePtr r = root;
root = root->m_leftChild;
delete r;
r = nullptr;
return true;
}
else {
delete root;
root = nullptr;
return true;
}
}
else if (value > root->m_value) {
return remove(root->m_rightChild, value);
}
else {
return remove(root->m_leftChild, value);
}
}
else {
return false;
}
} _TreeNodePtr& changeNodeParent(_TreeNodePtr& rNode)
{
if (rNode->m_leftChild->m_leftChild) {
return changeNodeParent(rNode->m_leftChild);
}
else {
return rNode;
}
} bool replace(_TreeNodePtr root, _dataType target, _dataType value)
{
if (target == value) {
return false;
}removeCount = 0;
remove(target);
if (removeCount == 0) {
return false;
}while (removeCount-- > 0) {
add(value);
}return true;
} bool search(_TreeNodePtr root, _dataType value)
{
if (root) {
if (value =https://www.it610.com/article/= root->m_value) {
return true;
}
else if (value > root->m_value) {
return search(root->m_rightChild, value);
}
else {
return search(root->m_leftChild, value);
}
}
else {
return false;
}
} void copy(_TreeNodePtr& leftRoot, _TreeNodePtr rightRoot)
{
if (rightRoot) {
leftRoot = new TreeNode<_dataType>(rightRoot->m_value);
copy(leftRoot->m_leftChild, rightRoot->m_leftChild);
copy(leftRoot->m_rightChild, rightRoot->m_rightChild);
}
} void clear(_TreeNodePtr& root)
{
if (root) {
clear(root->m_leftChild);
clear(root->m_rightChild);
delete root;
root = nullptr;
}
} size_t depth(_TreeNodePtr root)
{
if (root) {
size_t leftDepth = depth(root->m_leftChild);
size_t rightDepth = depth(root->m_rightChild);
return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
}
else {
return 0;
}
} size_t numberOfLeaves(_TreeNodePtr root)
{
if (root) {
if (root->m_leftChild && root->m_rightChild) {
return numberOfLeaves(root->m_leftChild) + numberOfLeaves(root->m_rightChild);
}
else if (root->m_leftChild) {
return numberOfLeaves(root->m_leftChild);
}
else if (root->m_rightChild) {
return numberOfLeaves(root->m_rightChild);
}
else {
return 1;
}
}
else {
return 0;
}
} void preorderTraversal(_TreeNodePtr root)
{
if (root) {
std::cout << root->m_value << ", ";
preorderTraversal(root->m_leftChild);
preorderTraversal(root->m_rightChild);
}
} void midorderTraversal(_TreeNodePtr root)
{
if (root) {
midorderTraversal(root->m_leftChild);
std::cout << root->m_value << ", ";
midorderTraversal(root->m_rightChild);
}
}
void postorderTraversal(_TreeNodePtr root)
{
if (root) {
postorderTraversal(root->m_leftChild);
postorderTraversal(root->m_rightChild);
std::cout << root->m_value << ", ";
}
}
};
#endif //_TREE_H_ 6.总结 【数据结构|第95篇 C++数据结构（五）树】只是实现，节点的删除如果不明白的话，可以自己多按着代码写几次，当然想，个人看别人的代码没有很好的耐心，就上课的时候自己画画写写，在纸上模拟过程，怎么删才好，还是觉得自己想过的东西才会有更深的理解。
推荐阅读
- 数据结构 happiness
- [ 数据结构 -- 手撕排序算法第七篇 ] 堆排序（中）堆排序的优化算法
- 计算机相关|信息学奥赛导论
- 我爷爷都看的懂的《栈和队列》，学不会来打我
- C语言典例|【数据结构】二叉树--链式结构
- 蓝桥杯|蓝桥侦探[蓝桥杯]——种类并查集
- 考研408|计算机考研408（数据结构（持续更新))
- LeetCode|450. 删除二叉搜索树中的节点
- 数据结构与算法|数据结构（第二章（一））