二叉树(前序、中序、后序遍历图片步骤详解)

二叉树(前序、中序、后序遍历图片步骤详解)首先我们有这么一颗二叉树:前序遍历:根结点—>左子树—>右子树这棵树的前序遍历为:ABDEGHCF中序遍历:左子树—>根结点—>右子树这棵树的前序遍历为:DBGEHACF后序遍历:左子树—>右子树—>根结点这棵树的前序遍历为:DGHEBFCA层次遍历:按层次遍历这棵树的前序遍历为:ABCDEF…

大家好,又见面了,我是你们的朋友全栈君。

首先我们有这么一颗二叉树:
在这里插入图片描述

public class TreeNode { 
   
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() { 
   
    }

    TreeNode(int val) { 
   
        this.val = val;
    }
}
  • 前序遍历:根结点 —> 左子树 —> 右子树(先遍历根节点,然后左右)

这棵树的前序遍历为:ABDEGHCF

代码实现:

public List<Integer> preorderTraversal(TreeNode root) { 
   
        List<Integer> res = new ArrayList<Integer>();
        preorder(root, res);
        return res;
    }

    public void preorder(TreeNode root, List<Integer> res) { 
   
        if (root == null) { 
   
            return;
        }
        res.add(root.val);
        preorder(root.left, res);
        preorder(root.right, res);
    }
  • 中序遍历:左子树—> 根结点 —> 右子树(在中间遍历根节点)

这棵树的中序遍历为:DBGEHACF

代码实现:

public List<Integer> inorderTraversal(TreeNode root) { 
   
        List<Integer> res = new ArrayList<Integer>();
        inorder(root, res);
        return res;
    }

public void inorder(TreeNode root, List<Integer> res) { 
   
        if (root == null) { 
   
            return;
        }
        inorder(root.left, res);
        res.add(root.val);
        inorder(root.right, res);
    }
  • 后序遍历:左子树 —> 右子树 —> 根结点(最后遍历根节点)

这棵树的后序遍历为:DGHEBFCA

代码实现:

public List<Integer> postorderTraversal(TreeNode root) { 
   
        List<Integer> res = new ArrayList<Integer>();
        postorder(root, res);
        return res;
    }

public void postorder(TreeNode root, List<Integer> res) { 
   
        if (root == null) { 
   
            return;
        }
        postorder(root.left, res);
        postorder(root.right, res);
        res.add(root.val);
    }
  • 层次遍历:按层次遍历

这棵树的层次遍历为:ABCDEFGH

代码实现

public List<List<Integer>> levelOrder(TreeNode root) { 
   
		if(root == null) { 
   
			return new ArrayList<List<Integer>>();
		}
		
		List<List<Integer>> res = new ArrayList<List<Integer>>();
		LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
		//将根节点放入队列中,然后不断遍历队列
		queue.add(root);
		while(queue.size()>0) { 
   
			//获取当前队列的长度,这个长度相当于 当前这一层的节点个数
			int size = queue.size();
			ArrayList<Integer> tmp = new ArrayList<Integer>();
			//将队列中的元素都拿出来(也就是获取这一层的节点),放到临时list中
			//如果节点的左/右子树不为空,也放入队列中
			for(int i=0;i<size;++i) { 
   
				TreeNode t = queue.remove();
				tmp.add(t.val);
				if(t.left!=null) { 
   
					queue.add(t.left);
				}
				if(t.right!=null) { 
   
					queue.add(t.right);
				}
			}
			//将临时list加入最终返回结果中
			res.add(tmp);
		}
		return res;
	}

ps: 所谓的前序、中序、后续,就是对根节点而言的,左右的遍历顺序不变,前序就是根节点最先遍历,然后左右;中序就是把根节点放在中间遍历;后序则是把根节点放在最后遍历。


  • 笔试题:已知二叉树前序遍历为:ABDEGHCF,中序遍历为:DBGEHACF,求后序遍历

分析:

  1. 首先我们由前序遍历可知根节点为A
  2. 已知根节点为A,由中序遍历可知左子树为DBGEH,右子树为CF

确定这两点后就很容易推算出原来的二叉树的样子了。
我们看到右子树节点为CF,中序遍历也是CF,那么就可以推断出现在的二叉树右边是这个样子:
在这里插入图片描述
为什么F不是左子树呢,因为如果F在左边,中序遍历的顺序就变成FC了

由前序遍历AB可以知,A的左子树肯定是B,那么现在的树就是这样的:
在这里插入图片描述
再由中序遍历DB可知,D为B的左子树
在这里插入图片描述

现在只剩下EGH没确定了
首先我们要确定的是D肯定没有子树,如果有,中序遍历就不会是DB了
由前序遍历可知E节点只能是B的右子树了
在这里插入图片描述
,最后由中序遍历GEH可知完整的二叉树为:
在这里插入图片描述

推断出整棵树后其他的遍历就都很容易写出来了。

这种题的关键是确定根节点和左右子树。如果是已知后序遍历,也是一样的最后一个就是根节点。

关于我

觉得文章不错请扫码关注我吧

weichat

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/132889.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号