数据结构 二叉树的递归与非递归
实例代码：
我要评论
#include <iostream>
#include <queue>
#include <stack>
#include <assert.h>
using namespace std;
template<class t>
struct binarytreenode
{
binarytreenode<t>* _left;
binarytreenode<t>* _right;
t _data;
binarytreenode(const t& x)
:_left(null)
, _right(null)
, _data(x)
{}
};
template <class t>
class binarytree
{
typedef binarytreenode<t> 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>& t)
{
_root = _copy(t._root);
}
binarytree<t>& operator=( binarytree<t>& 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<node*> 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<t>* root)
{
if (root)
{
cout << root->_data << " ";
_prevorder(root->_left);
_prevorder(root->_right);
}
}
void _postorder(binarytreenode<t>* root)
{
if (root)
{
_postorder(root->_left);
_postorder(root->_right);
cout << root->_data << " ";
}
}
void _inorder(binarytreenode<t>* root)
{
if (root)
{
_inorder(root->_left);
cout << root->_data << " ";
_inorder(root->_right);
}
}
int _size(binarytreenode<t>* root)
{
if (root==0)
{
return 0;
}
return _size(root->_left) + _size(root->_right) + 1;
}
int _leafsize(binarytreenode<t>* 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<t>* _root;
};
void testbinarytree()
{
int array[10] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6 };
binarytree<int> t1(array,sizeof(array)/sizeof(array[0]),'#');
binarytree<int>t2(t1);
binarytree<int> 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;
}
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
如对本文有疑问， 点击进行留言回复！！
网友评论