二叉樹用C++實(shí)現(xiàn)

template<class T>

struct BinaryTreeNode//二叉樹的節(jié)點(diǎn)結(jié)構(gòu)

{

T _data;

BinaryTreeNode<T>* _left;

BinaryTreeNode<T>* _right;

BinaryTreeNode(const T& x)

:_data(x._data)

, _left(NULL)

, _right(NULL)

{}

};

template<class T>

class BinaryTree

{

public:

BinaryTree()

:_root(NULL)

{}

BinaryTree(const T* a, size_t size)//構(gòu)建一棵樹

{

size_t index = 0;

_root = _createTree(a, size, index);

}

void PrevOrder()

{

_PervOrder(_root);

cout << endl;

}

void InOrder()

{

_InOrder(_root);

cout << endl;

}

void PostOrder()

{

_PostOrder(_root);

cout << endl;

}

void LevelOrder()

{

queue<BinaryTreeNode<T>*> q;

if (_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()

{

return _Size(_root);

}

int Depth(BinaryTreeNode<T>* root)

{

int ret = _Depth(root);

return ret;

}

BinaryTreeNode<T>* Find(BinaryTreeNode<T>* root,T data)

{

if (root == NULL)

return;

if (data == root->_data)

{

return root;

}

BinaryTreeNode<T>* ret = Find(root->_left, data);

if (ret)

return ret;

return Find(root->_right, data);;

}

protected:

BinaryTreeNode<T>* _CreateTree(const T* a, size_t size, size_t& index)

{

BinaryTreeNode* 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 << " ";

}

int _Size(BinaryTreeNode<T>* root)

{

if (root == NULL)

{

return 0;

}

return _Size(root->_left) + _Size(root->_right) + 1;

}

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;

}

void _GetLeafNum(BinaryTreeNode<T>* root, int& num)

{

if (root == NULL)

return;

if (root->_left == NULL && root->_right == NULL)

{

++num;

return;

}

_GetLeafNum(root->_left);

_GetLeafNum(root->_right);

}

protected:

BinaryTreeNode<T>* _root;

};