这篇文章主要为大家展示了“编程语言中数据结构之二叉树递归与非递归的示例分析”，内容简而易懂，条理清晰，希望能够帮助大家解决疑惑，下面让小编带领大家一起研究并学习一下“编程语言中数据结构之二叉树递归与非递归的示例分析”这篇文章吧。
成都创新互联服务项目包括双塔网站建设、
双塔网站制作、双塔网页制作以及双塔网络营销策划等。多年来，我们专注于互联网行业，利用自身积累的技术优势、行业经验、深度合作伙伴关系等，向广大中小型企业、政府机构等提供互联网行业的解决方案，
双塔网站推广取得了明显的社会效益与经济效益。目前，我们服务的客户以成都为中心已经辐射到双塔省份的部分城市，未来相信会继续扩大服务区域并继续获得客户的支持与信任！
数据结构 二叉树的递归与非递归
实例代码：
#include
#include
#include
#include
using namespace std;
template
struct BinaryTreeNode
{
BinaryTreeNode* _left;
BinaryTreeNode* _right;
T _data;
BinaryTreeNode(const T& x)
:_left(NULL)
, _right(NULL)
, _data(x)
{}
};
template
class BinaryTree
{
typedef BinaryTreeNode Node;
public:
BinaryTree()
:_root(NULL)
{}
BinaryTree(T* a, size_t n, const T& invalid)
{
size_t index = 0;
_root=CreateTree(a, n, invalid, index);
}
BinaryTree(const BinaryTree& t)
{
_root = _Copy(t._root);
}
BinaryTree& operator=( BinaryTree& t)
{
swap(_root,t._root);
return *this;
}
~BinaryTree()
{
_DestroyTree(_root);
}
Node* CreateTree(const T* a, size_t n, const T& invalid, size_t& index)
{
assert(a);
Node* root = NULL;
if (index < n && a[index] != invalid)
{
root = new Node(a[index]);
root->_left = CreateTree(a, n, invalid, ++index);
root->_right = CreateTree(a, n, invalid, ++index);
}
return root;
}
先序遍历(递归法)
void PrevOrder()
{
_PrevOrder(_root);
cout << endl;
}
//先序遍历非递归
void PrevOrderNorR( )
{
Node* cur = _root;
stack< Node* >s;
while (cur||!s.empty())
{
while (cur)
{
cout << cur->_data << " ";
s.push(cur);
cur = cur->_left;
}
Node* top = s.top();
s.pop();
cur = top->_right;
}
cout << endl;
}后序遍历
void PostOrder()
{
_PostOrder(_root);
cout << endl;
}
//后序遍历非递归
void PostOrderNorR()
{
Node* cur = _root;
Node* prev = NULL;
stack< Node* >s;
while (cur || !s.empty())
{
while (cur)
{
s.push(cur);
cur = cur->_left;
}
Node* top = s.top();
if (NULL==top->_right && prev==top->_right)
{
cout << top->_data << " ";
s.pop();
prev = top;
}
cur = top->_right;
}
cout << endl;
}
//中序遍历
void InOrder()
{
_InOrder(_root);
cout << endl;
}
//中序遍历非递归
void InOrderNorR()
{
Node* cur = _root;
stack< Node* >s;
while (cur || !s.empty())
{
while (cur)
{
s.push(cur);
cur = cur->_left;
}
Node* top = s.top();
s.pop();
cout << top->_data << " ";
cur = top->_right;
}
cout << endl;
}
//节点个数
size_t Size()
{
return _Size(_root);
}
//叶子节点个数
size_t LeafSize()
{
return _LeafSize(_root);
}
//树的深度
size_t Depth()
{
return _Depth(_root);
}
size_t GetKLevel(size_t k)
{
return _GetKLevel(_root,k);
}
// 查找
Node* Find(size_t x)
{
return _Find(_root,x);
}
//层序遍历
void LevelOrder()
{
queue q;
if (_root)
{
q.push(_root);
}
while (!q.empty())
{
Node* front = q.front();
cout << front->_data << " ";
q.pop();
if (front->_left)
{
q.push(front->_left);
}
if (front->_right)
{
q.push(front->_right);
}
}
cout << endl;
}
protected:
Node* _Copy(Node* root)
{
if (root==NULL)
{
return NULL;
}
Node* NewRoot = new Node(root->_data);
NewRoot->_left = _Copy(root->_left);
NewRoot->_right = _Copy(root->_right);
return NewRoot;
}
void _DestroyTree(Node* root)
{
if (NULL==root)
{
return;
}
_DestroyTree(root->_left);
_DestroyTree(root->_right);
delete root;
}
void _PrevOrder(BinaryTreeNode* root)
{
if (root)
{
cout << root->_data << " ";
_PrevOrder(root->_left);
_PrevOrder(root->_right);
}
}
void _PostOrder(BinaryTreeNode* root)
{
if (root)
{
_PostOrder(root->_left);
_PostOrder(root->_right);
cout << root->_data << " ";
}
}
void _InOrder(BinaryTreeNode* root)
{
if (root)
{
_InOrder(root->_left);
cout << root->_data << " ";
_InOrder(root->_right);
}
}
int _Size(BinaryTreeNode* root)
{
if (root==0)
{
return 0;
}
return _Size(root->_left) + _Size(root->_right) + 1;
}
int _LeafSize(BinaryTreeNode* root)
{
if (root==NULL)
{
return 0;
}
else if (root->_left == NULL&&root->_right == NULL)
{
return 1;
}
return _LeafSize(root->_left) + _LeafSize(root->_right);
}
int _Depth(Node* root)
{
if (root==NULL)
{
return 0;
}
int left = _Depth(root->_left);
int right = _Depth(root->_right);
return left > right ? left + 1 : right + 1;
}
int _GetKLevel(Node* root, size_t k)
{
assert(k>0);
if (root==NULL)
{
return 0;
}
else if (k==1)
{
return 1;
}
return _GetKLevel(root->_left, k - 1) + _GetKLevel(root->_right, k - 1);
}
Node* _Find(Node* root, const T& x)
{
if (root==NULL)
{
return NULL;
}
if (root->_data==x)
{
return root;
}
Node* ret = _Find(root->_left,x);
if (ret != NULL)
return ret;
return _Find(root->_right, x);
}
private:
BinaryTreeNode* _root;
};void TestBinaryTree()
{
int array[10] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6 };
BinaryTree t1(array,sizeof(array)/sizeof(array[0]),'#');
BinaryTreet2(t1);
BinaryTree t3;
t3 = t2;
t2.LevelOrder();
t3.LevelOrder();
t1.LevelOrder();
t1.PrevOrder();
t1.PrevOrderNorR();
t1.InOrder();
t1.InOrderNorR();
t1.PostOrder();
t1.PostOrderNorR();
cout << endl;
cout << t1.Size() << endl;
cout << t1.LeafSize() << endl;
cout << t1.Depth() << endl;
cout << t1.GetKLevel(2) << endl;
cout << t1.Find(2) << endl;
}以上是“编程语言中数据结构之二叉树递归与非递归的示例分析”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注创新互联行业资讯频道！
文章名称：编程语言中数据结构之二叉树递归与非递归的示例分析-创新互联
文章来源：
http://bzwzjz.com/article/dcicse.html
