首页 / 操作系统 / Linux / N叉树一 基本实现

丢了一次以前写的算法的文档和源代码，Ubuntu One不可靠啊！只好从头再写一遍。本文实现了一个树，不是二叉树，是N叉树。也就是允许一个节点拥有多个子节点。不是为了做题目糊弄人，所以内存管理不允许泄漏，用了C++11的shared_ptr。先看看调用代码：

1. #include <iostream>   
2. #include <memory>   
3.   
4. using namespace std;  
5.   
6. #include "tree.h"   
7. using namespace freebird;  
8.   
9.   
10. using node_type = shared_ptr<node<int>>;  
11. using node_iterator = vector<shared_ptr<node<int>>>::iterator;  
12.   
13. tree<node_type> t;  
14.   
15. void init（）{  
16.   node_type n1（new node<int>（1））;  
17.   t.root（n1）;  
18.   
19.   node_type n2（new node<int>（2））;  
20.   node_type n3（new node<int>（3））;  
21.   node_type n4（new node<int>（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.   cout<<"the 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.     cout<<"the value of root"s 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。

1. using node_type = shared_ptr<node<int>>;