亲宝软件园·资讯

展开

Java二叉树的四种遍历(递归和非递归)

灯塔先生 人气:0

二叉树的遍历可以分为前序、中序、后序、层次遍历。

前中后是指何时访问中间节点,即前序遍历,遍历节点的顺序为:中—>左—>右;

中序遍历,遍历节点的顺序为:左—>中—>右;

后序遍历,遍历节点的顺序为:左—>右—>中。

前序遍历

递归实现

public void preorder_Traversal(TreeNode root)
  {
    if(root==null)return;
    
    //访问节点的逻辑代码块
    System.out.print(root.val+" ");
    
    preorder_Traversal(root.left);
    preorder_Traversal(root.right);
  }

非递归过程如下:

1.每遍历一个节点的时候,先节点入栈,然后寻找当前节点的左子节点。(因为是前序遍历,所以在节点入栈之前就可以对节点进行访问)

2.当某个节点的左子节点,当左子节点不为空的时候,重复过程1.

3.当左子节点为空的时候将当前节点出栈,并且通过其寻找右子节点,右子节点不为空的时候,重复过程1-2

4.当右子节点也为空的时候,则跳回上一个该节点的父节点(即因为当前节点已经出栈,所以现在在栈中最上层的节点是当前节点的父节点)

非递归实现

public void preorder(TreeNode root)
  {
    Stack<TreeNode>  stack=new Stack<>();
    while(root!=null||!stack.isEmpty())
    {
      //当前节点不为空,则入栈,确保最后遍历到的节点没有左子节点
      //因为是前序遍历,所以再遍历到每个节点的时候,都可以先访问,再寻找其左右子节点。
      while(root!=null)
      {
        System.out.print(root.val+" ");
        stack.push(root);
        root=root.left;
      }
      if(!stack.empty())
      {
        //把这两步看成是一步,找到右节点,并把已处理的中节点从stack当中去除
        root=stack.pop();
        root=root.right;
      }
    }
  }

中序遍

递归实现

public void inorder_Traversal(TreeNode root)
  {
    if(root==null)return;
    inorder_Traversal(root.left);
    
     //访问节点的逻辑代码块
    System.out.print(root.val+" ");
    
    inorder_Traversal(root.right);
  }

非递归

对比前序、中序,发现代码几乎一模一样,但唯一的不同的是,访问节点的位置不一样,中序遍历是当左子节点被访问过,或者不存在的时候,才可以访问中间节点,所以再该处,访问节点的位置放在了当左子节点不存在的时候,即节点出栈的时候,即是左子节点不存在的时候进行访问。

非递归实现

public void Inorder(TreeNode root)
  {
    Stack<TreeNode> stack=new Stack<>();
    while(root!=null||!stack.isEmpty())
    {
      //当前节点不为空,则入栈,确保最后遍历到的节点没有左子节点
      while(root!=null)
      {
        stack.push(root);
        root=root.left;
      }
      //通过当前节点,跳到当前节点的右节点,因为是中序遍历,所以当前节点没有左节点的时候,就 
       可以访问当前节点
      if(!stack.empty())
      {
        root=stack.pop();
        System.out.print(root.val+" ");
        root=root.right;
      }
    }
  }

后序遍历

递归实现

public void postorder_Traversal(TreeNode root)
  {
    if(root==null)return;
    postorder_Traversal(root.left);
    postorder_Traversal(root.right);
    
     //访问节点的逻辑代码块
    System.out.print(root.val+" ");
  }

非递归版本一

借助两个栈来存储我们的节点以及标示位,过程如下:

1.每遍历一个节点的时候,先节点入栈s,并且s2入栈一个标识位0,然后寻找当前节点的左子节点。

2.当某个节点的左子节点,当左子节点不为空的时候,重复过程1.

3.当左子节点为空的时候将当前节点peek出(即将节点拿出,但栈中还是有该节点),并且此时将s2对应栈顶的标识位改为1,通过其寻找右子节点,右子节点不为空的时候,重复过程1-2

4.当右子节点也为空的时候,并且s2对应的标识符为1的时候,则弹出s1栈顶的当前节点,并且将s2的标识符弹出(即因为当前节点还没有出栈,所以现在在栈中最上层的节点是当前节),注意s1弹出当前节点并访问,但是不赋值给root,在这个root此时还是null

5.进入过程3,此时root被peek赋值到当前节点的父节点(因为在过程4当中,已经pop出了当前节点,所以s1栈顶是当前节点的父节点)的右子节点。

6.重复过程1-5

public void Postorder(TreeNode root)
  {
    Stack<TreeNode> s =new Stack<>(); 
    Stack<Integer> s2 =new Stack<>();
    Integer i=new Integer(1);
    while(root!=null||!s.isEmpty())
    {
      //只要当前节点非空,就入栈
      while(root!=null)
      {
        s.push(root);
        s2.push(new Integer(0));
        root=root.left;
      }
      //s2当中如果存1,则意味着当前s1对应的节点的左右子节点都已经遍历过了。
      while(!s.empty()&&s2.peek().equals(i))
      {
        s2.pop();
        System.out.print(s.pop().val+" ");
      }
      if(!s.isEmpty())
      {
        s2.pop();
        s2.push(new Integer(1));
        root=s.peek();
        root=root.right;
      }
      
    }
  }

非递归版本二

实现思路:

在进行后序遍历的时候是先要遍历左子树,然后在遍历右子树,最后才遍历根节点。所以在非递归的实现中要先把根节点入栈,然后再把左子树入栈直到左子树为空,此时停止入栈。此时栈顶就是需要访问的元素,所以直接取出访问p。在访问结束后,还要判断被访问的节点p是否为栈顶节点的左子树,如果是的话那么还需要访问栈顶节点的右子树,所以将栈顶节点的右子树取出赋值给p。如果不是的 话则说明栈顶节点的右子树已经访问完了,那么现在可以访问栈顶节点了,所以此时将p赋值为null。判断结束的条件是p不为空或者栈不为空,若果两个条件都不满足的话,说明所有节点都已经访问完成。

非递归实现

public void postOrder(Node root) {
		
	Stack<Node> s = new Stack<Node>();
	Node p = root;
	while (p != null || !s.empty()) {
		while(p != null) {
			s.push(p);
			p = p.left;
		}
		p = s.pop();
		System.out.print(p.val+" ");
	//这里需要判断一下,当前p是否为栈顶的左子树,如果是的话那么还需要先访问右子树才能访问根节点
	//如果已经是不是左子树的话,那么说明左右子书都已经访问完毕,可以访问根节点了,所以讲p复制为NULL
	//取根节点
		if (!s.empty() && p == s.peek().left) {
			p = s.peek().right;
		}
		else p = null;
	}
}
 

层次遍历

用队列实现,步骤是:

1.对于不为空的结点,先把该结点加入到队列中;

2.从队中拿出结点,如果该结点的左右结点不为空,就分别把左右结点加入到队列中;

3.重复以上操作直到队列为空;

public void LaywerTraversal(TreeNode root){
  if(root==null) return;
  LinkedList<TreeNode> list = new LinkedList<TreeNode>(); 
  list.add(root);
  TreeNode currentNode;
  while(!list.isEmpty()){
    currentNode=list.poll();
    System.out.println(currentNode.val);
    if(currentNode.left!=null){
      list.add(currentNode.left);
    }
    if(currentNode.right!=null){
      list.add(currentNode.right);
    }
  }
}

加载全部内容

相关教程
猜你喜欢
用户评论