#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;
}