二叉树实现
#pragma once
#include <queue>
#include <stack>
using namespace std;
template<class T>
struct BinaryTreeNode //树节点
{
T _data;
BinaryTreeNode<T>* _left;
BinaryTreeNode<T>* _right;
BinaryTreeNode(const T& x)
:_data(x)
, _left(NULL)
, _right(NULL)
{}
};
template<class T>
class BinaryTree
{
public:
BinaryTree()
:_root(NULL)
{}
BinaryTree(const T* a, size_t size)
{
size_t index = 0;
_root = _CreateTree(a, size, index);
}
~BinaryTree()
{
_Destroy(_root);
_root = NULL;
}
BinaryTree(const BinaryTree<T>& t)
{
_root = _Copy(t._root);
}
BinaryTree<T>& operator=(BinaryTree<T> t)
{
swap(_root, t._root);
return *this;
}
void PrevOrder()
{
_PrevOrder(_root);
cout << endl;
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
void PostOrder()
{
_PostOrder(_root);
cout << endl;
}
//二叉树的层次遍历
void LevelOrder()
{
queue<BinaryTreeNode<T>*> q; //定义一个队列q
if (_root) //判断_root是否为空
{
q.push(_root);
}
while (!q.empty())
{
BinaryTreeNode<T>* front = q.front();
q.pop();
cout << front->_data << " ";
if (front->_left) //由左向右依次进入队列，依次输出
{
q.push(front->_left);
}
if (front->_right)
{
q.push(front->_right);
}
}
cout << endl;
}
int Size()
{
int size = 0;
_Size(_root, size);
return size;
}
int Depth()
{
return _Depth(_root);
}
BinaryTreeNode<T>* Find(const T& x)
{
return _Find(_root, x);
}
//二叉树前序遍历
void PrevOrder_NonR()
{
stack<BinaryTreeNode<T>*> s;
if (_root)
{
s.push(_root); //将树入栈
}
while (!s.empty()) //栈不为空，根节点先出栈
{
BinaryTreeNode<T>* top = s.top();
s.pop();
cout << top->_data << " ";
if (top->_right) //压入右子树
{
s.push(top->_right);
}
if (top->_left) //压入左子树
{
s.push(top->_left);
}
}
cout << endl;
}
void InOrder_NonR()
{
stack<BinaryTreeNode<T>*> s;
BinaryTreeNode<T>* cur = _root;
while (cur || !s.empty())
{
while (cur)
{
s.push(cur);
cur = cur->_left;
}
if (!s.empty())
{
BinaryTreeNode<T>* top = s.top();
cout << top->_data << " ";
s.pop();
cur = top->_right;
}
}
cout << endl;
}
void PostOrder_NonR()
{
stack<BinaryTreeNode<T>*> s;
BinaryTreeNode<T>* cur = _root;
BinaryTreeNode<T>* prevVisited = NULL;
while (cur || !s.empty())
{
while (cur)
{
s.push(cur);
cur = cur->_left;
}
BinaryTreeNode<T>* top = s.top();
if (top->_right == NULL || top->_right == prevVisited)
{
cout << top->_data << " ";
prevVisited = top;
s.pop();
}
else
{
cur = top->_right;
}
}
cout << endl;
}
int GetLeafNum()
{
int num = 0;
_GetLeafNum(_root, num);
return num;
}
protected:
BinaryTreeNode<T>* _Copy(BinaryTreeNode<T>* root)
{
if (root == NULL)
{
return NULL;
}
BinaryTreeNode<T>* newRoot = new BinaryTreeNode<T>(root->_data);
newRoot->_left = _Copy(root->_left);
newRoot->_right = _Copy(root->_right);
return newRoot;
}
void _Destroy(BinaryTreeNode<T>*& root)
{
if (root == NULL)
{
return;
}
if (root->_left == NULL && root->_right == NULL)
{
delete root;
root = NULL;
return;
}
_Destroy(root->_left);
_Destroy(root->_right);
delete root;
}
BinaryTreeNode<T>* _CreateTree(const T* a, size_t size, size_t& index)
{
BinaryTreeNode<T>* root = NULL;
if (index < size && a[index] != ‘#‘)
{
root = new BinaryTreeNode<T>(a[index]);
root->_left = _CreateTree(a, size, ++index);
root->_right = _CreateTree(a, size, ++index);
}
return root;
}
void _PrevOrder(BinaryTreeNode<T>* root)
{
if (root == NULL)
{
return;
}
cout << root->_data << " ";
_PrevOrder(root->_left);
_PrevOrder(root->_right);
}
void _InOrder(BinaryTreeNode<T>* root)
{
if (root == NULL)
{
return;
}
_InOrder(root->_left);
cout << root->_data << " ";
_InOrder(root->_right);
}
void _PostOrder(BinaryTreeNode<T>* root)
{
if (root == NULL)
{
return;
}
_PostOrder(root->_left);
_PostOrder(root->_right);
cout << root->_data << " ";
}
void _Size(BinaryTreeNode<T>* root, int& size)
{
if (root == NULL)
{
return;
}
else
{
size++;
}
_Size(root->_left, size);
_Size(root->_right, size);
}
int _Depth(BinaryTreeNode<T>* root)
{
if (root == NULL)
{
return 0;
}
int leftDepth = _Depth(root->_left);
int rightDepth = _Depth(root->_right);
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
BinaryTreeNode<T>* _Find(BinaryTreeNode<T>* root, const T& x)
{
if (root == NULL)
{
return NULL;
}
else if (root->_data == x)
{
return root;
}
else
{
BinaryTreeNode<T>* ret = _Find(root->_left, x);
if (ret)
{
return ret;
}
else
{
return _Find(root->_right, x);
}
}
}
void _GetLeafNum(BinaryTreeNode<T>* root, int& num)
{
if (root == NULL)
{
return;
}
if (root->_left == NULL&&root->_right == NULL)
{
++num;
return;
}
_GetLeafNum(root->_left, num);
_GetLeafNum(root->_right, num);
}
protected:
BinaryTreeNode<T>* _root;
};
简单测试：
s
void Test1()
{
int a[10] = { 1, 2, 3, ‘#‘, ‘#‘, 4, ‘#‘, ‘#‘, 5, 6 };
BinaryTree<int>t1(a, 10);
t1.PrevOrder();
t1.InOrder();
t1.PostOrder();
t1.LevelOrder();
cout << "size:" << t1.Size() << endl;
cout << "depth:" << t1.Depth() << endl;
int b[15] = { 1, 2, ‘#‘, 3, ‘#‘, ‘#‘, 4, 5, ‘#‘, 6, ‘#‘, 7, ‘#‘, ‘#‘, 8 };
BinaryTree<int>t2(b, 15);
t2.PrevOrder();
cout << "size:" << t2.Size() << endl;
cout << "depth:" << t2.Depth() << endl;
cout << t2.Find(8)->_data << endl;
cout << t2.Find(6)->_data << endl;
t2.PrevOrder();
t2.PrevOrder_NonR();
t2.InOrder();
t2.InOrder_NonR();
t2.PostOrder();
t2.PostOrder_NonR();
cout << "叶子节点的个数：" << t2.GetLeafNum() << endl;
}本文出自 “木木侠” 博客，谢绝转载！
原文：http://10324228.blog.51cto.com/10314228/1757214