二叉树的三种遍历(递归算法)

 1 struct Node
 2 {
 3     int data;
 4     Node* lchild;
 5     Node* rchild;
 6 }
 7 void preorder(Node* parent)
 8 {
 9     if (parent!=NULL)
10     {
11         cout<<parent->data<<endl;
12         preorder(parent->lchild);
13         preorder(parent->rchild);
14     }
15 }
16 void inorder(Node* parent)
17 {
18     if (parent!=NULL)
19     {
20         inorder(parent->lchild);
21         cout<<parent->data<<endl;
22         inorder(parent->rchild);
23     }
24 }
25 void postorder(Node* parent)
26 {
27     if (parent!=NULL)
28     {
29         postorder(parent->lchild);
30         postorder(parent->rchild);
31         cout<<parent->data<<endl;
32     }
33 }

重新又看了一遍二叉树(Binary Tree),发现很多东西自己还没有弄明白,原来三种遍历方式还不是自己想象中的那样

前序遍历(PreOrder)是先输出自己,然后左,最后右。

中序遍历(InOrder)是先左,再输出自己,最后右。

后序遍历(PostOrder)是先左,再右,最后输出自己。

所谓的XX遍历就是指把自己放在哪个优先位置上,而不是指从哪里开始遍历。

算下来其实搜索匹配也可以用这个方法,基本上就是以递归形成的。

另外还需要研究一下DFS(Depth First Search)以及BFS(Breadth First Search)的算法。





posted on 2012-11-09 10:04 Beatles 阅读(1122) 评论(0)  编辑 收藏 引用 所属分类: C++


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2012年11月>
28293031123
45678910
11121314151617
18192021222324
2526272829301
2345678

导航

统计

常用链接

留言簿

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜