Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1528721
  • 博文数量: 399
  • 博客积分: 8508
  • 博客等级: 中将
  • 技术积分: 5302
  • 用 户 组: 普通用户
  • 注册时间: 2009-10-14 09:28
个人简介

能力强的人善于解决问题,有智慧的人善于绕过问题。 区别很微妙,小心谨慎做后者。

文章分类

全部博文(399)

文章存档

2018年(3)

2017年(1)

2016年(1)

2015年(69)

2013年(14)

2012年(17)

2011年(12)

2010年(189)

2009年(93)

分类:

2009-10-14 15:46:29

左孩子右兄弟存储方式:    
struct tree_node
{
  int data;
  tree_node* first_child;
  tree_node* sibling;
}

一个观念必须要有: root没有兄弟sibling,根是独立的,代表这一棵树---------忘记了绝不会写递归了。


(A) 深度遍历:       
    (1)递归算法:
       先根遍历 void   preOrder(tree_node * root)
                      {
                         if (!root)
                             return;
                         printf(root->data);
                         tree_node* p;
                         for(p=root->first_child;p,p=p->sibling)
                         {
                             preOrder(p);
                         }
                      }
       后根遍历 void   postOrder(tree_node * root)
                      {
                         if (!root)
                             return;
                         tree_node* p;
                         for(p=root->first_child;p,p=p->sibling)
                         {
                             preOrder(p);
                         }
                         printf(root->data);
                      }
    (2)非递归算法:     
                    记忆技巧是将节点看成是二叉树,因为树对应的二叉树的        
                    先序与树的先根遍历序列是一致的,这是公认的事实。
        先根遍历 void  preOrder(tree_node* root)
                      {
                         stack sk;
                         while(root  ||  !sk.empty())
                         {
                              while(root)
                              {
                                  printf(root->data);
                                  sk.push(root);
                                  root=root->first_child;
                              }
                              root=sk.top(); sk.pop();//STL要求这样做的
                              root=root->sibling; //root可以为空的
                         }
                      }
                    记忆技巧是将节点看成是二叉树,因为树对应的二叉树的        
                    中序与树的后根遍历序列是一致的,这是公认的事实。
        后根遍历 void  postOrder(tree_node* root)
                      {
                         stack sk;
                         while(root  ||  !sk.empty())
                         {
                              while(root)
                              {                                 
                                  sk.push(root);
                                  root=root->first_child;
                              }
                              root=sk.top();sk.pop();//STL要求这样做的
                              printf(root->data);
                              root=root->sibling;//root可以为空的
                         }
                      }

(B)广度遍历(按层次次序遍历树的算法)
   用队列实现
   void levelOrde(tree_node* root)
   {
      queue q;
      q.push(root);

      while(!q.empty())
      {
                  root=q.font();q.pop();
                  printf(root->data);
                  root=root->first_child;
                  while(!root)
                  {
                      q.push(root);
                      root=root->sibling;
                   }
      }
   }
阅读(8005) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~