template

創(chuàng)新互聯(lián)公司是一家集網(wǎng)站建設(shè),根河企業(yè)網(wǎng)站建設(shè),根河品牌網(wǎng)站建設(shè),網(wǎng)站定制,根河網(wǎng)站建設(shè)報(bào)價(jià),網(wǎng)絡(luò)營(yíng)銷,網(wǎng)絡(luò)優(yōu)化,根河網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強(qiáng)企業(yè)競(jìng)爭(zhēng)力?？沙浞譂M足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時(shí)我們時(shí)刻保持專業(yè)、時(shí)尚、前沿，時(shí)刻以成就客戶成長(zhǎng)自我，堅(jiān)持不斷學(xué)習(xí)、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實(shí)用型網(wǎng)站。

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

{

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)//構(gòu)建一棵樹(shù)

{

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;

};