二叉树用C++实现

template

创新互联公司是一家集网站建设,根河企业网站建设,根河品牌网站建设,网站定制,根河网站建设报价,网络营销,网络优化,根河网站推广为一体的创新建站企业，帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿，时刻以成就客户成长自我，坚持不断学习、思考、沉淀、净化自己，让我们为更多的企业打造出实用型网站。

struct BinaryTreeNode//二叉树的节点结构

{

T _data;

BinaryTreeNode* _left;

BinaryTreeNode* _right;

BinaryTreeNode(const T& x)

:_data(x._data)

, _left(NULL)

, _right(NULL)

{}

};

template

class BinaryTree

{

public:

BinaryTree()

:_root(NULL)

{}

BinaryTree(const T* a, size_t size)//构建一棵树

{

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*> q;

if (_root)

{

q.push(_root);

}

while (!q.empty())

{

BinaryTreeNode* 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* root)

{

int ret = _Depth(root);

return ret;

}

BinaryTreeNode* Find(BinaryTreeNode* root,T data)

{

if (root == NULL)

return;

if (data == root->_data)

{

return root;

}

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

if (ret)

return ret;

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

}

protected:

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

{

BinaryTreeNode* root = NULL;

if (index < size && a[index] != "#")

{

root = new BinaryTreeNode(a[index]);

root->_left = _CreateTree(a, size, ++index);

root->_right = _CreateTree(a, size, ++index);

}

return root;

}

void _PrevOrder(BinaryTreeNode* root)

{

if (root == NULL)

{

return;

}

cout << root->_data << " ";

_PrevOrder(root->_left);

_prevOrder(root->_right);

}

void _InOrder(BinaryTreeNode* root)

{

if (root == NULL)

{

return;

}

_InOrder(root->_left);

cout << root->_data << " ";

_InOrder(root->_right);

}

void _PostOrder(BinaryTreeNode* root)

{

if (root == NULL)

{

return;

}

_PostOrder(root->_left);

_PostOrder(root->_right);

cout << root->_data << " ";

}

int _Size(BinaryTreeNode* root)

{

if (root == NULL)

{

return 0;

}

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

}

int _Depth(BinaryTreeNode* 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* root, int& num)

{

if (root == NULL)

return;

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

{

++num;

return;

}

_GetLeafNum(root->_left);

_GetLeafNum(root->_right);

}

protected:

BinaryTreeNode* _root;

};