二叉树用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;

};

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。