树的遍历

package dataStucture;

/**
 * 树的节点类。这里是简单创建一个二叉树
 * @author lxt
 *
 */
public class BitTree {
 
 int data;
 
 /**
  *左树指针
  */
 BitTree lchild;
 /**
  * 右树指针
  */
 BitTree rchild;
 
 
 public BitTree(int data) {
  super();
  this.data = data;
 }

 /**
  * 先序遍历，访问根，再先序遍历左子树，先序遍历右子树
  * @param root
  */
 public static void preOrder(BitTree root){
  
  if(root==null) return ;
  else {
   System.out.printf("%7d",root.data);
   preOrder(root.lchild);
   preOrder(root.rchild);
  }
   
 }
 
 /**
  * 二叉树的中序遍历,先中序遍历左子树，再访问根，再中序遍历右子树
  * @param root
  */
 public static void inOrder(BitTree root){
  if(root==null) return ;
  else {
   inOrder(root.lchild);
   System.out.printf("%7d",root.data);
   inOrder(root.rchild);
  }
 }
 /**
  * 后序遍历。
  *  先后序遍历左子树，后序遍历右子树，最后访问根节点。
  * @param root
  */
 public static void postOrder(BitTree root){
  if(root==null) return ;
  else {
   inOrder(root.lchild);
   System.out.printf("%7d",root.data);
   inOrder(root.rchild);
  }
  
 } 
}

 

 

package dataStucture;

/**
 * 树的节点类。这里是简单创建一个二叉树
 * @author lxt
 *
 */
public class TestBitTree {
 
 public static void main(String[] args) {
  
  BitTree root=new BitTree(1);
     root.lchild=new BitTree(2);
  root.rchild=new BitTree(3);
  root.lchild.lchild=new BitTree(4);
  root.lchild.rchild=new BitTree(5);
  root.rchild.lchild=new BitTree(6);
  root.rchild.rchild=new BitTree(7);
  
  BitTree.preOrder(root);
  System.out.println();
  BitTree.inOrder(root);
  System.out.println();
  BitTree.postOrder(root);
  
  
 
 }
}

 

 

评论

3 楼 Heart.X.Raid 2010-05-10  

//非递归后序遍历二叉树
void aftorder_traverser_nonrec(BiTree root){

   TreeNode *p,*q;
   p=q=root;
   //指针栈，用于存储树中的结点地址
   TreeNode *stack[100];
   //栈顶位置
   int top=0;

   while(top>-1){
        //堆栈所有可能的左孩子，直到没有左孩子或左或右孩子已经输出
        while(p->lchild!=NULL&&q!=p->lchild&&q!=p->rchild){
             stack[top++]=p;
             p=p->lchild;
        }
        //当前结点没有右孩子或右孩子已经输出完毕
        if(p->rchild==NULL||q==p->rchild){
             visit(p); //输出结点
             if(top==0) --top;//说明栈中的结点全部处理完
             else{
                  q=p;
                  p=stack[--top];
             }
        }else{//向右孩子前进一步
            stack[top++]=p
            p=p->rchild;
        }
   }
}

程序没有编译，随手写了一下，应该没有逻辑错误

2 楼 yysolo 2009-08-26  

 50     def left?()
 51         @left != nil
 52     end
 53     def right?()
 54         @right != nil
 55     end
 56     def is_left?(parent)
 57         self == parent.left
 58     end
 59     def is_right?(parent)
 60         self == parent.right
 61     end

127     def visit_post()
128         stack = []
129         node = self
130         while true
131             while node.left?
132                 stack.push(node)
133                 node = node.left
134             end
135             if node.right?
136                 stack.push(node)
137                 node = node.right
138             else
139                 while not stack.empty?
140                     yield node
141                     last = stack.last()
142                     if not last.right? or node.is_right?(last)
143                         node = stack.pop()
144                     else
145                         node = last.right
146                         break
147                     end
148                 end
149                 if stack.empty?
150                     yield node
151                     break
152                 end
153             end
154         end
155     end

1 楼 wantdrink 2009-08-18  

期待楼主放出后序遍历的非递归