二叉树的建立和各种遍历(java版)

这是个常见的面试题,比如说通过二叉树的先序和中序遍历,得到二叉树的层序遍历等问题

先序+中序 ->建树

假设现在有个二叉树,如下:

此时遍历顺序是:

PreOrder: GDAFEMHZ InOrder: ADEFGHMZ PostOrder: AEFDHZMG

现在给出先序(preOrder)和中序(InOrder),建立一颗二叉树 或者给出中序(InOrder)和后序(PostOrder), 建立二叉树,其实是一样的

树节点的定义:

class Tree{
    char val;
    Tree left;
    Tree right;

    Tree(char val, Tree left, Tree right){
        this.val = val;
        this.left = left;
        this.right = right;
    }
    Tree(){

    }
    Tree(char val){
        this.val = val;
        this.left = null;
        this.right =null;
    }
}

建树:

public static Tree buildTree(char[] preOrder, char[] inOrder){
        //preOrder是先序序列
        //inOrder是中序序列
        if(preOrder == null || preOrder.length == 0){
            return null;
        }

        Tree root = new Tree(preOrder[0]);
        //找到inOrder中的root的位置
        int inOrderIndex = 0;
        for(char i = 0; i < inOrder.length; i++){
            if(inOrder[i] == root.val){
                inOrderIndex = i;
            }
        }
        //preOrder的左子树和右子树部分
        char[] preOrderLeft = Arrays.copyOfRange(preOrder, 1, 1+inOrderIndex);
        char[] preOrderRight = Arrays.copyOfRange(preOrder, 1+inOrderIndex, preOrder.length);

        //inOrder的左子树和右子树部分
        char[] inOrderLeft = Arrays.copyOfRange(inOrder, 0, inOrderIndex);
        char[] inOrderRight = Arrays.copyOfRange(inOrder, inOrderIndex+1, inOrder.length);

        //递归建立左子树和右子树
        Tree leftChild = buildTree(preOrderLeft, inOrderLeft);
        Tree rightChild = buildTree(preOrderRight, inOrderRight);
        root.left = leftChild;
        root.right = rightChild;

        return root;
    }

中序+后序去建树其实是一样的,此处不写了

各种遍历

后序遍历

public static void postOrderPrint(Tree root){
        //后续遍历
        //左右根
        if(root.left != null){
            postOrderPrint(root.left);
        }
        if(root.right != null){
            postOrderPrint(root.right);
        }
        System.out.print(root.val + " ");
    }

举一反三,先序和中序是一样的,此处不写了

层序遍历

可以用一个队列Queue,初始先把root节点加入到队列,当队列不为空的时候取队列头的节点node,打印node的节点值,如果node的左右孩子不为空将左右孩子加入到队列中即可

public static void layerOrderPrint(Tree root){
        if(root == null){
            return;
        }
        //层序遍历
        Queue<Tree> qe = new LinkedList<Tree>();
        qe.add(root);
        while(!qe.isEmpty()){
            Tree node  = qe.poll();
            System.out.print(node.val + " ");
            if(node.left != null){
                qe.add(node.left);
            }
            if(node.right != null){
                qe.add(node.right);
            }
        }
    }

深度优先和广度优先

其实就是换个说法而已,深度优先不就是先序遍历嘛,广度优先就是层序遍历

public static void deepFirstPrint(Tree root){
        //深度优先遍历等价于先序遍历
        //所以可以直接使用先序遍历
        if(root == null){
            return;
        }
        System.out.print(root.val + " ");
        if(root.left != null){
            deepFirstPrint(root.left);
        }
        if(root.right != null){
            deepFirstPrint(root.right);
        }
    }

public static void deepFirstPrintNoneRec(Tree root){
        //深度优先遍历的非递归形式
        if(root == null){
            return;
        }
        Stack<Tree> st = new Stack<Tree>();
        st.add(root);
        while(!st.isEmpty()){
            Tree node = st.pop();
            System.out.print(node.val + " ");
            //栈是后进先出的
            //先加右孩子后加左孩子
            if(node.right != null){
                st.add(node.right);
            }
            if(node.left != null){
                st.add(node.left);
            }
        }
    }

main函数:

public static void main(String[] args) {
        char[] preOrder = "GDAFEMHZ".toCharArray();
        char[] inOrder = "ADEFGHMZ".toCharArray();
        Tree root = Main.buildTree(preOrder, inOrder);
//      Main.postOrderPrint(root); //后序遍历
//      Main.layerOrderPrint(root); //层序遍历
//      Main.deepFirstPrint(root); //深度优先遍历
//      Main.deepFirstPrintNoneRec(root); //深度优先遍历的非递归版本
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏有趣的Python

数据结构探险之树篇数据结构探险之树篇

数据结构探险之树篇 什么是树? 树是节点的有限结合。 ? 1正2倒 ? 概念 根节点:A 双亲:A 孩子:A :b,c,d 度:A的度为3,因为它接着三个节点...

2674
来自专栏大闲人柴毛毛

剑指offer代码解析——面试题25二叉树中和为某一值的路径

题目:输入一棵二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。PS:从根结点开始,一直到叶子结点形式一条路径。 分析:要找出路径之和为指定整...

2695
来自专栏拭心的安卓进阶之路

重温数据结构:二叉树的常见方法及三种遍历方式 Java 实现

树的分类有很多种,但基本都是 二叉树 的衍生,今天来学习下二叉树。 ? 什么是二叉树 Binary Tree 先来个定义: 二叉树是有限个节点的集合,这个集合...

2136
来自专栏Java技术栈

二叉树实战 22 题,速度收藏吧!

深刻的理解这些题的解法思路,在面试中的二叉树题目就应该没有什么问题,甚至可以怒他,哈哈。

353
来自专栏LinkedBear的个人空间

【挑战剑指offer】系列04:重建二叉树 原

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6...

542
来自专栏xcywt

《大话数据结构》树以及赫夫曼编码的例子

第六章 树 6.2 树的定义 树(Tree)的n个结点的有限集。当n=0时,称为空树。 任意一个非空树中: 1)有且仅有一个特定的称为根(root)的结点 2)...

3836
来自专栏Android机动车

数据结构——遍历二叉树

二叉树的遍历:是指从根结点出发,按照某种次序依次访问二叉树中的所有结点,使得每个结点被访问一次且仅被访问一次。

671
来自专栏赵俊的Java专栏

镜像二叉树

1243
来自专栏Python专栏

【数据结构与算法】一起搞定面试中的二叉树题目(二)

1203
来自专栏肖洒的博客

数据结构笔记(二)

栈是限定仅在表尾进行插入和删除操作的线性表。 队列是只允许在一段进行插入操作、而在另一端进行删除操作的线性表。

733

扫码关注云+社区