投米网,葫芦岛法律服务网,男生被女生玩鸡视频
本文主要讲了如何使用c++来构建一个二叉树类，以及一些功能算法的实现。文中大部分函数的思想都是递归，其中赋值运算符重载有传统写法和现代写法两个版本，层序遍历是非递归，前、中、后序遍历有递归和非递归两个版本。
1、构造函数（递归）
2、拷贝构造函数（递归）
3、析构函数（递归）
4、赋值运算符重载（传统/现代）
5、前中后序遍历（递归/非递归）
6、层序遍历（非递归）
7、查找第k层结点个数（递归）
8、精确查找值为x的结点，并返回当前结点的指针（递归）
9、查找叶子结点个数（递归）
10、查找结点总个数（递归）
11、计算树的深度（递归）
树的结点类型，每个结点都需要有一个指向右孩子的指针，一个指向左孩子的指针，以及一个数据。（当然，如果你想构造三叉树的话，也可以增加一个指向父节点的指针。）
这里我写出了结点的构造函数，方便我们在创建树的时候使用。
注意：这棵树我使用了模板
我要评论
template
struct binarytreenode
{
binarytreenode* _left;//左孩子
binarytreenode* _right;//右孩子
t _data;//数据
binarytreenode(t data = t())//结点自己的构造函数，t()为一个匿名对象。
:_left(null)//初始化为空
, _right(null)
, _data(data)
{}
};
下面代码中会经常用到binarytreenode
typedef binarytreenode node;
class binarytree
{
public:
private:
binarytreenode* _root;//根节点
};
1、构造函数
binarytree(const t* a, size_t size,int index, const t& invalid)
构造函数有4个参数，t类型的指针a，传参时传一个数组，负责传入数据。size保存数组a 的大小，index记录下标，invalid表示非法值。
因为我们需要用到递归，所以在这个函数内部我们需要再封装一个递归函数_maketree()，并让它的返回值为一个node*类型的指针。
binarytree(const t* a, size_t size,int index, const t& invalid)
{
_root = _maketree(a,size,index,invalid);
}
我们先来观察一个树：
你会看到上面有许多null，这些null我们就可以理解为非法值invalid。这棵树的前序遍历为:
1 2 3 null null 4 null null 5 6
最后一个结点不需要非法值，到时候直接创建即可。
与上对应，我们传数组时，应该传的值即为 int a[10] = {1,2,3,'#','#',4,'#','#',5,6}。非法值的值可以随意设，这里我设为‘#’，注意，你向以什么的样的顺序建树，就以什么样的顺序传参，事先要约定好。（这里我用的是前序）
递归：当我们从数组读取到一个数据时，我们先要判断这个值是不是合法，如果合法则new出一个结点并初始化作为当前结点，此时，进入左孩子递归函数读取下一个数据（++index），并把这个函数的返回值链到当前结点root的left，同理，将右孩子递归函数的返回值链到当前结点的right。如果不合法则return，返回上一层函数。最后我们会得到一个根节点，例图中的1。
_maketree函数实现:
node* _maketree(const t* a, size_t size, int& index, const t& invalid)
{
node *root = null;
if (index < size && a[index] != invalid)
{
root = new node(invalid);
root->_data = a[index];
root->_left = _maketree(a, size, ++index, invalid);
root->_right = _maketree(a, size, ++index, invalid);
}
return root;
}
同上，同样实现一个递归函数，返回值仍为node*
binarytree(const binarytree& t)
{
_root = copytree(t._root);
}
递归：同样为前序，从根节点开始，先访问当前结点，判断，若当前结点为空，则返回一个空。若当前结点不为空，则拷贝当期结点。然后递归进入当前结点的左子树，同样进行之前的步骤。左子树处理完之后递归处理右子树。然后返回当前结点（每一层的根节点）。
注意：上文提到的当前结点，在每一层的递归中值都是不一样的。每递归一层，当前结点就会变成传入的参数root。包括下文
copytree实现代码：
node* copytree(const binarytreenode* _root)3、
{
if (_root == null)
{
return null;
}
node* root = new node(_root->_data);
root->_left = copytree(_root->_left);
root->_right = copytree(_root->_right);
return root;
}
同上，但是析构函数不需要返回值。
~binarytree()
{
destroy(_root);
}
递归的道理都与上面两个相同，这里直接给出代码：
void destroy( node* _root)
{
node* tmp = _root;
if (tmp == null)//如果根结点为空，则不需要delete，直接return。
return;
destroy(tmp->_left);
destroy(tmp->_right);
delete tmp;
tmp = null;
}
4、赋值运算符重载（=）
当我们写任何赋值运算符重载时，都会有两种写法
①传统写法，一个元素一个元素的拷贝，传参时传的是const的引用。
这样赋值有个麻烦的地方，我们知道，当给一个结点赋值的时候，这个结点原本的内容，空间就要被销毁掉。就是说我们既要new又要delete。当这个树有1个亿结点时，我们岂不是要重复1亿次？有没有一种更简单的方法呢？
②现代写法（建议使用，很巧妙），调用swap函数，交换两个树的root。传参时用的值传递。
binarytree& operator=(binarytree t)
{
if (this != &t)//自赋值的优化
{
std::swap(_root, t._root);
}
return *this;
}
我们都知道，值传递传的是一份临时拷贝（t为一份临时拷贝），临时拷贝的特性就是，它的存活周期只限于这个函数，当函数调用完毕时，它会自动销毁，而我们也恰恰利用了这个特性。当我们运行std::swap(_root,t._root)这个语句的时候，临时拷贝t的_root 和 本树的(this)_root发生了交换。_root原本的值被赋给了临时拷贝t._root，t._root的值被赋给了_root。当我们执行完这个程序的时候t自动销毁，帮我们完成了销毁_root原本内容的工作。我们即完成了赋值，又省去了一大部分工作，一举两得。
5、前中后序遍历（递归）
①前序
这个我就不再多说了，构造，拷贝构造，析构，都是利用前序遍历的道理来做的。当前结点-->左子树-->右子树。
代码：
void prevorder()
{
_prevorder(_root);
cout << endl;
}
void _prevorder(node* _root)
{
node* tmp = _root;
if (tmp == null)
{
return;
}
cout << tmp->_data << " ";
_prevorder(tmp->_left);
_prevorder(tmp->_right);
}
②中序
判断当前结点是否为空，为空的话，不处理，直接返回。先递归访问当前结点左子树，当左子树处理完毕，再依次返回处理当前结点，再递归访问当前结点右子树。
void inorder()
{
_inorder(_root);
cout << endl;
}
_inorder()
void _inorder(node* _root)
{
node* tmp = _root;
if (tmp == null)
{
return;
}
_inorder(tmp->_left);
cout << tmp->_data << " ";
_inorder(tmp->_right);
}
判断当前结点是否为空，为空的话，不处理，直接返回。不为空的话，先递归访问当前结点节点的左子树，再递归访问当前结点根节点的右子树，最后访问当前结点。
void postorder()
{
_postorder(_root);
cout << endl;
}
_postorder()
void _postorder(node* _root)
{
node* tmp = _root;
if (tmp == null)
{
return;
}
_postorder(tmp->_left);
_postorder(tmp->_right);
cout << tmp->_data << " ";
}
6、前中后序非递归。
这里我告诉大家一个真理，任何的递归都可以用栈来替换实现。这里我就用一个辅助栈来实现前中后序的非递归。
①前序
代码：
void prevorder_nonr()
{
node* cur = _root;
stack s;
if (cur == null)
{
return;
}
while (cur || !s.empty())
{
while (cur)
{
s.push(cur);
cout << cur->_data << " ";
cur = cur->_left;
}
node* top = s.top();
s.pop();
cur = top->_right;
}
cout << endl;
}
②中序（非递归）
void inorder_nonr()
{
node* cur = _root;
stack s;
if (cur == null)
{
return;
}
while (cur || !s.empty())
{
while (cur)
{
s.push(cur);
cur = cur->_left;
}
node* top = s.top();
cout << top->_data << " ";
s.pop();
cur = top->_right;
}
cout << endl;
}
③后序（非递归）
后序的非递归较上面两个多了一个变量，prev，它记录了上一次访问的节点。因为后序是最后访问当前节点的，当我们访问一个节点，我们不知道这个节点的右树是否被访问过。所以我们需要记录一下上一个访问的节点。以便访问右树时做判断。
void postorder_nonr()
{
node* cur = _root;
node* prev = null;
stack s;
while (cur || s.empty())
{
while (cur)
{
s.push(cur);
cur = cur->_left;
}
node* top = s.top();
//如果右树为空或者右树已经访问过，则访问当前结点，并出栈
//如果右树不为空并且没有访问过，则访问右树
if (top->_right == null || prev == top->_right)
{
cout << top->_data << " ";
prev = top;
s.pop();//返回父节点
}
else
{
cur = top->_right;
}
}
cout << endl;
}
顾名思义。层序遍历就是按层来访问一颗树，一次访问一层。这里我们用到了一个队列。
代码：
void _levelorder(node* _root)
{
node *tmp = _root;
queue q;
q.push(tmp);
while (!q.empty())
{
node* top = q.front();
q.pop();
cout << top->_data << " ";
if (top->_left)
{
q.push(top->_left);
}
if (top->_right)
{
q.push(top->_right);
}
}
}
8、查找第k层节点个数
这个问题，我们只需要查找第k-1层有多少个孩子就行了。
同样为递归，前序。
size_t findklevel(size_t k)
{
return _findklevel(_root,k);
}
size_t _findklevel(node* _root,size_t k)
{
node *cur = _root;
if (cur == null || k < 0)
{
return 0;
}
if (k == 1)
{
return 1;
}
size_t left = _findklevel(cur->_left, k-1);
size_t right = _findklevel(cur->_right, k-1);
return left + right;
}
9、精确查找值为x的结点
前序递归查找，如果根节点为空，返回null，如果当前节点等于x，返回当前节点的指针。如果当前节点不等于x，则递归进入左子树查找，若左子树没有，则递归进入右子树查找，若这棵树中没有x，返回null。
node* find(const t& x)
{
return _find(_root,x);
}
_find()
node* _find(node* _root,const t& x)
{
node* ret = null;
node* cur = _root;
if (cur == null)
{
return null;
}
if (cur->_data == x)
{
ret = cur;
}
else
{
ret = _find(cur->_left,x);
if (ret == null)
{
ret = _find(cur->_right,x);
}
}
return ret;
}
结点总个数 = 当前节点个数+左子树节点个数+右子树节点个数。
前序递归查找，若当前节点为空，返回，不为空则加1，--->递归左子树----->递归右子树。
size_t size()
{
return _size(_root);
}
_size()
size_t _size( binarytreenode* _root )
{
size_t ret = 0;
if (_root == null)
{
return ret;
}
ret++;
ret += _size(_root->_left);
ret += _size(_root->_right);
}
11、计算树的深度
树的深度取左子树深度+1和右子树深度+1的最大值。(+1为根节点的深度)
size_t depth()
{
return _depth(_root);
}
_depth()
size_t _depth(node* _root)
{
if (_root == null)
{
return 0;
}
int left = _depth(_root->_left) + 1;
int right = _depth(_root->_right) + 1;
return left > right ? left : right;
}
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论