N叉树一 基本实现.pdf

丢了一次以前写的算法的文档和源代码 ，Ubuntu One不可靠啊 ！只好从头再写一遍。 本文实现了一个树 ，不是二叉树 ，是N叉树。也就是允许一个节点拥有多个子节点。 不是为了做题 目糊弄人 ，所以内存管理不允许泄漏 ，用了C++11的shared_ptr。先看看调用代码 ： 源码 打印 ？ 01. #include iostream 02. #include memory 03. 04. using namespace std; 05. 06. #include tree.h 07. using namespace freebird; 08. 09. 10. using node_type = shared_ptrnodeint; 11. using node_iterator = vectorshared_ptrnodeint::iterator; 12. 13. treenode_type t; 14. 15. void init(){ 16. node_type n1(new nodeint(1)); 17. t.root(n1); 18. 19. node_type n2(new nodeint(2)); 20. node_type n3(new nodeint(3)); 21. node_type n4(new nodeint(4)); 22. 23. n1-push_back(n2); 24. n1-push_back(n3); 25. n1-push_back(n4); 26. 27. } 28. 29. void view_root(){ 30. node_type r = t.root(); 31. coutthe value of root:r-value()endl; 32. 33. node_iterator itor = r-begin(); 34. node_iterator last = r-end(); 35. for(;itor!=last;++itor){ 36. node_type cur_node = *itor; 37. coutthe value of roots one child:cur_node-value()endl; 38. } 39. 40. } 41. 42. int main(int args,char* argv[]){ 43. 44. init(); 45. 46. view_root(); 47. 48. 49. 50. } init函数初始化tree,放了一个根节点 ，然后加入三个子节点。 view_root将四个节点数据遍历出来。 tree这个类看上去可有可无 ，其实不然。今后会将查找 ，遍历等算法封装在tree类里面 ，方便使用。 注意using的用法 ，是C++11的template aliases。 using node_type shared_ptrnodeint; 我用的是GCC4.7.0,Ubuntu 12.04,CMake. 现在看看tree.h中的实现。 源码 打印 ？ 01. #ifndef _TREE_H 02. #define _TREE_H 03. 04. #include vector 05. #include memory 06. 07. namespace freebird { 08. 09. templatetypename T 10. class node{ 11. public: 12. node(T value):value_(value){ 13. } 14. 15. 16. 17. /** 18. * insert child node to the end 19. */ 20. void