《多叉树的层次遍历算法》由会员分享,可在线阅读,更多相关《多叉树的层次遍历算法(7页珍藏版)》请在金锄头文库上搜索。
1、多叉树的层次遍历算法疯狂代码 http:/CrazyC j:http:/CrazyC 多叉树层次遍历这个在网上有完整好像不多这次我就把写贴出来, 有兴趣朋友起来硏究下.TreeNode.h 文件# ndef_TREENODE_# _TREENODE_# -StdAfx.h# v# # v iostream a# vqueueusing std;TreeNodeprivate:long selfID;nodeName;list *p_childList;public:TreeNode;TreeNode;/*向当前节点中插入个子节点*/void insertChildNode(TreeNode *
2、treeNode);广遍历树层次遍历*/void Level Traverse;判断某个节点是否为叶子节点bool isLeaf;返回当前节点孩子集合list * getChildList;long getSelfld;void Selfld(long selfID);getNodeName;void NodeName( &nodeName);;返回当前节点孩子集合inline list * TreeNode:getChildListp_childList;inline long TreeNode:getSelfIdselfID;inline void TreeNode:SelfId(long
3、 self ID)this-selfID = self ID;inline TreeNode:getNodeNamenodeName;inline void Tr0eNode:NodeName( &nodeName)this nodeName = nodeName;#endTreeNode.cpp 文件# stdafx.h# TreeNode.hTreeNode:TreeNode selfID = 0;no deName =: p_childList = NULL;1TreeNode:TreeNodedelete p_childList; _判断某个节点是否为叶子节点bool TreeNode
4、:isLeaf(NULL p_childList)true;false;/*向当前节点中插入个子节点*/void TreeNode:insertChildNode(TreeNode *treeNode)(NULLtreeNode)couttreeNode is null !endl;(isLeaf)p_childList = list;p_childList-push_back(TreeNode*)treeNode);/*遍历树层次遍历*/void TreeNode:LevelTraversequeue queue ;queue.push(TreeNode*)this);TreeNode *p
5、 = NULL;while (Iqueue.empty)p = queue.front;queue.pop;cout treenode is:B getSelfld getChildList)list:iterator it = (p-getChildList)-begin;while(it!= (p-getChildList)-end)queue.push(*it);it;测试代码:# stdafx.h# TreeNode.h(argc, char* argv)TreeNode root;root.Selfld(O);TreeNode *nodel = TreeNode;TreeNode *
6、node2 = TreeNode;TreeNode *node3 = TreeNode; TreeNode *nodelO = TreeNode;nodel0-SelfId(10);nodel-SelfId(l);node2-SelfId(2);node3-SelfId(3);root.insertChildNode(nodel);root.insertChildNode(node2);root.insertChildNode(node3); root.insertChildNode(nodelO);TreeNode *node4 = TreeNode;TreeNode *node5 = Tr
7、eeNode;node4-SelfId(4);node5-SelfId(5);nodel-insertChildNode(node4); nodel-insertChildNode(node5);TreeNode *node6 = TreeNode;TreeNode *node7 = TreeNode;TreeNode *node8 = TreeNode;node6-SelfId (6);node7-SelfId(7);node8-Selfld(8);node4-insertChildNode(node6); node4- insertchild Node(node7); node4-inse
8、rtChildNode(node8);遍历root Level Traverse;delete nodel;delete node2;delete node3;delete node4;delete node5;delete node6;delete node7;delete node8;0;1打印出来结果是:0123104567 8 (其中10是故意用来测试)这个只是简单测试,大家可以用模板来实现.这个算法有几个关键地方:1. list中存放是指针,好处就不用说了.如果不用指针话,在delete时候会出现问题原因大家也清楚.2. 用队列比栈实现起来要方便 2009-2-12 4:00:36疯狂代码 h ttp:/CrazyC od er.c n/