首页 / C++ / c++实现二叉树（递归）
c++实现二叉树（递归）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了c++实现二叉树（递归），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5873字，纯文字阅读大概需要9分钟。
内容图文
首先先来看一下树的结构：
树是n（n>=0）个有限个数据的元素集合，形状像一颗倒过来的树。
650) this.width=650;" src="/upload/getfiles/default/2022/11/28/20221128101249224.jpg" />
650) this.width=650;" src="/upload/getfiles/default/2022/11/28/20221128101249506.jpg" title="QQ截图20160423101338.png" />
650) this.width=650;" src="/upload/getfiles/default/2022/11/28/20221128101249633.jpg" title="QQ截图20160423101418.png" />而二叉树就是树的一种特殊结构：
-
完全二叉树的数组表示
-
链表存储表示
650) this.width=650;" src="/upload/getfiles/default/2022/11/28/20221128101249855.jpg" title="QQ截图20160423101604.png" />
650) this.width=650;" src="/upload/getfiles/default/2022/11/28/20221128101250098.jpg" title="QQ截图20160423101812.png" />下面我就实现一下二叉链的这种结构：
首先是它的节点的结构：
template <typename T>
struct BinaryTreeNode
{
public:
BinaryTreeNode(const T &data)//构造函数
:_left(NULL)
,_right(NULL)
,_data(data)
{}
public:
BinaryTreeNode<T> * _left;//左子树
BinaryTreeNode<T> * _right;//右子树
T _data;//数据项
};
然后是它的基本成员函数：
template <typename T>
class BinaryTree
{
typedef BinaryTreeNode<T> Node;//重命名struct结构
public:
BinaryTree()//无参的构造函数
:_root(NULL)
{}
BinaryTree(const T* a, size_t size, const T& invalid)//有参构造函数
:_root(NULL)
{
size_t index = 0;
_root = _CreatBinaryTree(a, size, invalid, index);
}
BinaryTree(const BinaryTree<T> & t)//拷贝构造
:_root(NULL)
{
_root = _Copy(t._root);
}
BinaryTree<T>& operator=(BinaryTree<T> t)//赋值运算符的重载
{
if (this != &t)//防止自赋值
{
swap(_root, t._root);
}
return *this;
}
~BinaryTree()//析构函数
{
if (_root)
{
_Delete(_root);
}
}
void PrevOrder()//前序遍历
{
_PrevOrder(_root);
cout << "over"<<endl;
}
void InOrder()//中序遍历
{
_InOrder(_root);
cout << "over" << endl;
}
void PostOrder()//后序遍历
{
_PostOrder(_root);
cout << "over" << endl;
}
void LevelOredr()//层次遍历
{
_LevelOrder(_root);
cout << "over" << endl;
}
size_t Size()//节点数
{
return _Size(_root);
}
size_t Depth()//深度
{
return _Depth(_root);
}
size_t LeafSize()//叶子节点数
{
return _LeafSize(_root);
}
protected:
//创建二叉树
Node* _CreatBinaryTree(const T *a, size_t size, const T& invalid,size_t& index)
{
Node * cur = NULL;
if (index < size&&a[index] != invalid)//不能越界
{
cur = new Node(a[index]);//开辟节点
cur->_left = _CreatBinaryTree(a, size, invalid, ++index);//递归创建左子树
cur->_right = _CreatBinaryTree(a, size, invalid, ++index);//递归创建右子树
}
return cur;
}
//复制二叉树
Node* _Copy(Node * root)
{
Node * cur = NULL;
if (root == NULL)
{
return NULL;
}
cur = new Node(root->_data);//创建该节点
cur->_left = _Copy(root->_left);
cur->_right = _Copy(root->_right);
return cur;
}
//删除
void _Delete(Node * &root)
{
if (root == NULL)
{
return;
}
if (root->_left == NULL && root->_right == NULL)//该节点没有左右孩子
{
delete root;//释放该节点
root = NULL;
return;
}
_Delete(root->_left);
_Delete(root->_right);
}
//前序遍历：根节点--左子树--右子树
void _PrevOrder(Node * root)
{
if (root == NULL)
{
return;
}
cout << root->_data << "->";
_PrevOrder(root->_left);
_PrevOrder(root->_right);
}
//中序遍历：左子树--根节点--右子树
void _InOrder(Node * root)
{
if (root == NULL)
{
return;
}
_PrevOrder(root->_left);
cout << root->_data << "->";
_PrevOrder(root->_right);
}
//后序遍历：左子树--右子树--根节点
void _PostOrder(Node * root)
{
if (root == NULL)
{
return;
}
_PrevOrder(root->_left);
_PrevOrder(root->_right);
cout << root->_data << "->";
}
//层次遍历
void _LevelOrder(Node* root)
{
queue<Node*> q;
if (root == NULL)
{
return;
}
q.push(root);
while (!q.empty())
{
if (q.front()->_left != NULL)
{
q.push(q.front()->_left);
}
if (q.front()->_right != NULL)
{
q.push(q.front()->_right);
}
cout << q.front()->_data << "->";
q.pop();
}
}
//节点个数
size_t _Size(Node * root)
{
if (root == NULL)
{
return 0;
}
return _Size(root->_left) + _Size(root->_right) + 1;//当左子树或者右子树不为空时，该节点有数据
}
//二叉树的深度
size_t _Depth(Node * root)
{
if (root==NULL)
{
return 0;
}
size_t leftDepth = _Depth(root->_left);
size_t rightDepth = _Depth(root->_right);
/*if (leftDepth >= rightDepth)
{
return leftDepth + 1;
}
else
return rightDepth + 1;*/
return leftDepth > rightDepth?leftDepth + 1 : rightDepth+1;
}
//叶子节点个数
size_t _LeafSize(Node * root)
{
size_t size = 0;
if (root == NULL)
{
return size;
}
if (root->_left == NULL&&root->_right == NULL)
{
size++;
return size;
}
return _LeafSize(root->_left)+_LeafSize(root->_right);
}
private:
Node * _root;//根节点
};
测试用例以及结果如下：
void Test()
{
int array1[10] = { 1, 2, 3, ‘#‘, ‘#‘, 4, ‘#‘ , ‘#‘, 5, 6 };
BinaryTree<int> b1(array1, 10, ‘#‘);
cout << "前序遍历：";
b1.PrevOrder();
cout << "中序遍历：";
b1.InOrder();
cout << "后序遍历：";
b1.PostOrder();
cout << "层次遍历：";
b1.LevelOredr();
cout << endl;
cout << "节点数：" << b1.Size() << endl;
cout << "深度：" << b1.Depth() << endl;
cout << "叶子节点数：" << b1.LeafSize() << endl;
cout << endl;
BinaryTree<int> b2(b1);
cout << "前序遍历：";
b2.PrevOrder();
cout << "中序遍历：";
b2.InOrder();
cout << "后序遍历：";
b2.PostOrder();
cout << "层次遍历：";
b2.LevelOredr();
cout << endl;
cout << "节点数：" << b2.Size() << endl;
cout << "深度：" << b2.Depth() << endl;
cout << "叶子节点数：" << b2.LeafSize() << endl;
cout << endl;
BinaryTree<int> b3;
b3 = b1;
cout << "前序遍历：";
b3.PrevOrder();
cout << "中序遍历：";
b3.InOrder();
cout << "后序遍历：";
b3.PostOrder();
cout << "层次遍历：";
b3.LevelOredr();
cout << endl;
cout << "节点数：" << b3.Size() << endl;
cout << "深度：" << b3.Depth() << endl;
cout << "叶子节点数：" << b3.LeafSize() << endl;
}
本文出自 “不断进步的空间” 博客，请务必保留此出处http://10824050.blog.51cto.com/10814050/1766978
原文：http://10824050.blog.51cto.com/10814050/1766978
内容总结
以上是互联网集市为您收集整理的c++实现二叉树（递归）全部内容，希望文章能够帮你解决c++实现二叉树（递归）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】