void TreeNode::insertChildNode(TreeNode *treeNode)
{
if (NULL==treeNode)
{
cout<<"treeNode is null !"<<endl;
return;
}
if (isLeaf())
{
p_childList = new list<TreeNode*>;
}
p_childList->push_back((TreeNode*)treeNode);
}
/*遍历树，层次遍历*/
void TreeNode::LevelTraverse()
{
queue<TreeNode*> queue ;
queue.push((TreeNode*)this);
TreeNode *p = NULL;
while (!queue.empty())
{
p = queue.front();
queue.pop();
cout<<"treenode is: "<<p->getSelfId()<<endl;
if (NULL!= p->getChildList())
{
list<TreeNode*>::iterator it = (p->getChildList())->begin();
while(it!= (p->getChildList())->end())
{
queue.push((*it));
++it;
}
}
}
}
测试代码:
#include "stdafx.h"
#include "TreeNode.h"
int main(int argc, char* argv[])
{
TreeNode root;
root.setSelfId(0);
TreeNode *node1 = new TreeNode();
TreeNode *node2 = new TreeNode();
TreeNode *node3 = new TreeNode();
TreeNode *node10 = new TreeNode();
node10->setSelfId(10);
node1->setSelfId(1);
node2->setSelfId(2);
node3->setSelfId(3);
root.insertChildNode(node1);
root.insertChildNode(node2);
root.insertChildNode(node3);
root.insertChildNode(node10);
TreeNode *node4 = new TreeNode();
TreeNode *node5 = new TreeNode();
node4->setSelfId(4);
node5->setSelfId(5);
node1->insertChildNode(node4);
node1->insertChildNode(node5);
TreeNode *node6 = new TreeNode();
TreeNode *node7 = new TreeNode();
TreeNode *node8 = new TreeNode();
node6->setSelfId(6);
node7->setSelfId(7);
node8->setSelfId(8);
node4->insertChildNode(node6);
node4->insertChildNode(node7);
node4->insertChildNode(node8);
//遍历
root.LevelTraverse();
delete node1;
delete node2;
delete node3;
delete node4;
delete node5;
delete node6;
delete node7;
delete node8;
return 0;
}
打印出来的结果是:
0 1 2 3 10 4 5 6 7 8 (其中10是故意用来测试的)
这个只是简单的测试,大家可以用模板来实现.
这个算法有几个关键的地方:
1. list 中存放的是指针,好处就不用说了.如果不用指针的话,在delete时候会出现问题.原因大家也清楚.
2. 用队列比栈实现起来要方便。
3COME考试频道为您精心整理，希望对您有所帮助，更多信息在http://www.reader8.com/exam/
