8
/ \
6 10
/ \ / \
5 7 9 11
层次遍历输出结果： 8,6,10,5,7,9,11
#include <deque>
using std::deque;
#include <iostream>
using namespace std;
template<typename T>
struct TreeNode
{
public:
TreeNode(T value);
void setLeftChild( TreeNode *lChild );
void setRightChild( TreeNode *rChild );
TreeNode *getLeftChild ();
TreeNode *getRightChild();
void print();
private:
TreeNode *mLchild;
TreeNode *mRchild;
T mValue;
};
template<typename T>
TreeNode<T>::TreeNode(T value):mValue(value),mLchild(0),mRchild(0)
{
}
template<typename T>
void TreeNode<T>::setLeftChild( TreeNode *lChild )
{
mLchild = lChild;
}
template<typename T>
void TreeNode<T>::setRightChild( TreeNode *rChild )
{
mRchild = rChild;
}
template<typename T>
TreeNode<T> *
TreeNode<T>::getLeftChild ( )
{
return mLchild;
}
template<typename T>
TreeNode<T> *
TreeNode<T>::getRightChild ( )
{
return mRchild;
}
template<typename T>
void
TreeNode<T>::print()
{
cout << mValue <<endl;
}
template<typename T>
TreeNode<T> *
BuildTree()
{
TreeNode<int> *r8 = new TreeNode<int> ( 8 );
TreeNode<int> *r6 = new TreeNode<int> ( 6 );
TreeNode<int> *r10 = new TreeNode<int> ( 10 );
TreeNode<int> *r5 = new TreeNode<int> ( 5 );
TreeNode<int> *r7 = new TreeNode<int> ( 7 );
TreeNode<int> *r9 = new TreeNode<int> ( 9 );
TreeNode<int> *r11 = new TreeNode<int> ( 11 );
r8->setLeftChild(r6);
r8->setRightChild(r10);
r6->setLeftChild(r5);
r6->setRightChild(r7);
r10->setLeftChild(r9);
r10->setRightChild(r11);
return r8;
}
template<typename T>
void printTree(TreeNode<T> *node)
{
deque<TreeNode<T>*> fifo;
fifo.push_back(node);
while ( fifo.size() )
{
TreeNode<T> *front = fifo.front();
fifo.pop_front();
front->print();
if ( front->getLeftChild() )
{
fifo.push_back(front->getLeftChild());
}
if ( front->getRightChild() )
{
fifo.push_back(front->getRightChild());
}
}
}
int main()
{
TreeNode<int> *node = BuildTree<int>();
printTree(node);
return 0;
}