Java实现二叉树的前序遍历、中序遍历、后续遍历


二叉树的遍历方式有很多,如果我们按照从左到右的习惯进行限制,则主要分为4种:

  • 前序遍历
  • 中序遍历
  • 后序遍历
  • 层序遍历

下面以Java语言描述几种遍历方式。

  • 树形结构


    树形结构
  • 树形结构代码
/**
 * 树结构,包括节点值,左子树节点指针,右子树节点指针
 */
public class TreeNode {

    private String value;
    private TreeNode left;
    private TreeNode right;

    public String getValue() {
        return value;
    }

    public void setValue(String value) {
        this.value = value;
    }

    public TreeNode getLeft() {
        return left;
    }

    public void setLeft(TreeNode left) {
        this.left = left;
    }

    public TreeNode getRight() {
        return right;
    }

    public void setRight(TreeNode right) {
        this.right = right;
    }

}
  • 初始化树
/**
 * 初始化树的节点信息
 */
public class InitTree {

    public static TreeNode[] initTree() {
        TreeNode[] treeNode = new TreeNode[11];
        createInstance(treeNode);
        initNodeValue(treeNode);
        buildTree(treeNode);
        return treeNode;
    }

    // 创建节点对象
    private static void createInstance(TreeNode[] treeNode) {
        if (null != treeNode) {
            for (int i = 0; i < treeNode.length; i++) {
                treeNode[i] = new TreeNode();
            }
        }
    }

    // 初始化节点值
    private static void initNodeValue(TreeNode[] treeNode) {
        // 设置节点0-10的值
        treeNode[0].setValue("A");
        treeNode[1].setValue("B");
        treeNode[2].setValue("C");
        treeNode[3].setValue("D");
        treeNode[4].setValue("E");
        treeNode[5].setValue("F");
        treeNode[6].setValue("G");
        treeNode[7].setValue("H");
        treeNode[8].setValue("I");
        treeNode[9].setValue("J");
        treeNode[10].setValue("K");
    }

    // 构建树
    private static void buildTree(TreeNode[] treeNode) {
        // 初始化节点0的左子树和右子树
        treeNode[0].setLeft(treeNode[1]);
        treeNode[0].setRight(treeNode[2]);
        // 初始化节点1的左子树和右子树
        treeNode[1].setLeft(treeNode[3]);
        treeNode[1].setRight(treeNode[4]);
        // 初始化节点2的左子树和右子树
        treeNode[2].setLeft(treeNode[5]);
        treeNode[2].setRight(treeNode[6]);
        // 初始化节点3的左子树和右子树
        treeNode[3].setLeft(treeNode[7]);
        // 初始化节点4的左子树和右子树
        // 初始化节点5的左子树和右子树
        treeNode[5].setLeft(treeNode[8]);
        // 初始化节点6的左子树和右子树
        treeNode[6].setRight(treeNode[9]);
        // 初始化节点7的左子树和右子树
        treeNode[7].setRight(treeNode[10]);
        // 初始化节点8的左子树和右子树
        // 初始化节点9的左子树和右子树
        // 初始化节点10的左子树和右子树
    }

}

1.前序遍历算法

先来看代码

/**
 * 二叉树的前序遍历算法
 * 1.判断节点为空,返回空;
 * 2.打印节点数据;
 * 3.判断是否存在左子树,如果存在,递归,回到步骤1;
 * 4.判断是否存在右子树,如果存在,递归,回到步骤1;
 */
public class PreOrder {

    public void preOrder(TreeNode treeNode) {
        if (null == treeNode) {
            return;
        }
        System.out.print(treeNode.getValue());
        TreeNode leftNode = treeNode.getLeft();
        preOrder(leftNode);
        TreeNode rightNode = treeNode.getRight();
        preOrder(rightNode);
    }

}

测试代码

public class Test {

    public static void main(String[] args) {
        TreeNode[] treeNode = InitTree.initTree();
        PreOrder preOrder = new PreOrder();
        preOrder.preOrder(treeNode[0]);
    }

}

运行结果:ABDHKECFIGJ
程序是如何运行的?
(1)调用preOrder方法,传入的根节点A不为null,打印A节点的值A;


前序遍历1

(2)获取到A的左子树B,调用preOrder方法,B不为null,打印B节点的值B,结果AB;


前序遍历2

(3)获取到B的左子树D,调用preOrder方法,D不为null,打印D节点的值D,结果ABD;
前序遍历3

(4)获取到D的左子树H,调用preOrder方法,H不为null,打印H节点的值H,结果ABDH;
前序遍历4

(5)获取H的左子树,调用preOrder方法,H的左子树为null,方法返回null;继续执行H的逻辑,获取到H的右子树K,调用preOrder方法,K不为null,打印K节点的值K,结果ABDHK;


前序遍历5

(6)获取K的左子树,调用preOrder方法,K的左子树为null,方法返回null;继续执行K的逻辑,获取K的右子树,调用preOrder方法,K的右子树为null,方法返回null;(不要懵,方法中我们无非只有3个动作,打印、获取左子树递归、获取右子树递归,运行至此,K、H节点均已判断完毕)继续执行D的逻辑,获取D的右子树,调用preOrder方法,D的右子树为null,方法返回null;继续执行B的逻辑,获取到B的右子树E,调用preOrder方法,E不为null,打印E节点的值E,结果ABDHKE;
前序遍历6

(7)获取E的左子树,调用preOrder方法,E的左子树为null,方法返回null;继续执行E的逻辑,获取E的右子树,调用preOrder方法,E的右子树为null,方法返回null;继续执行A的逻辑,获取到A的右子树C,调用preOrder方法,C不为null,打印C节点的值C,结果ABDHKEC;
前序遍历7

(8)获取到C的左子树F,调用preOrder方法,F不为null,打印F节点的值F,结果ABDHKECF;
前序遍历8

(9)获取到F的左子树I,调用preOrder方法,I不为null,打印I节点的值I,结果ABDHKECFI;
前序遍历9

(10)获取I的左子树,调用preOrder方法,I的左子树为null,方法返回null;继续执行I的逻辑,获取I的右子树,调用preOrder方法,I的右子树为null,方法返回null;继续执行F的逻辑,获取F的右子树,调用preOrder方法,F的右子树为null,方法返回null;继续执行C的逻辑,获取到C的右子树G,调用preOrder方法,G不为null,打印G节点的值G,结果ABDHKECFIG;
前序遍历10

(11)获取G的左子树,调用preOrder方法,G的左子树为null,方法返回null;继续执行G的逻辑,获取到G的右子树J,调用preOrder方法,J不为null,打印J节点的值J,结果ABDHKECFIGJ;
前序遍历11

(12)获取J的左子树,调用preOrder方法,J的左子树为null,方法返回null;继续执行J的逻辑,获取J的右子树,调用preOrder方法,J的右子树为null,方法返回null;至此所有的节点都已判断完成,前序遍历算法的最终结果为:ABDHKECFIGJ。


前序遍历12

2.中序遍历算法

先来看代码

/**
 * 二叉树的中序遍历算法
 * 1.判断节点为空,返回空;
 * 2.判断是否存在左子树,如果存在,递归,回到步骤1;
 * 3.打印节点数据;
 * 4.判断是否存在右子树,如果存在,递归,回到步骤1;
 */
public class InOrder {

    public void inOrder(TreeNode treeNode) {
        if (null == treeNode) {
            return;
        }
        TreeNode leftNode = treeNode.getLeft();
        inOrder(leftNode);
        System.out.print(treeNode.getValue());
        TreeNode rightNode = treeNode.getRight();
        inOrder(rightNode);
    }

}

测试代码

public class Test {

    public static void main(String[] args) {
        TreeNode[] treeNode = InitTree.initTree();
        InOrder inOrder = new InOrder();
        inOrder.inOrder(treeNode[0]);
    }

}

运行结果:HKDBEAIFCGJ
程序是如何运行的?
(1)调用inOrder方法,传入的根节点A不为null,获取到A的左子树B;调用inOrder方法,B不为null,获取到B的左子树D;调用inOrder方法,D不为null,获取到D的左子树H;调用inOrder方法,H不为null,获取H的左子树;调用inOrder方法,H的左子树为null,方法返回null;打印H节点的值H,结果H;


中序遍历1

(2)继续执行H的逻辑,获取到H的右子树K,调用inOrder方法,K不为null,获取K的左子树;调用inOrder方法,K的左子树为null,方法返回null;打印K节点的值K,结果HK;


中序遍历2

(3)继续执行K的逻辑,获取K的右子树,调用inOrder方法,K的右子树为null,方法返回null;至此,H、K节点均已判断完成;继续执行D的逻辑,打印D节点的值D,结果HKD;
中序遍历3

(4)继续执行D的逻辑,获取D的右子树,调用inOrder方法,D的右子树为null,方法返回null;继续执行B的逻辑,打印B节点的值B,结果HKDB;
中序遍历4

(5)继续执行B的逻辑,获取到B的右子树E,调用inOrder方法,E不为null,获取E的左子树;调用inOrder方法,E的左子树为null,方法返回null;打印E节点的值E,结果HKDBE;


中序遍历5

(6)继续执行E的逻辑,获取E的右子树,调用inOrder方法,E的右子树为null,方法返回null;继续执行A的逻辑,打印A节点的值A,结果HKDBEA;
中序遍历6

(7)继续执行A的逻辑,获取到A的右子树C,调用inOrder方法,C不为null,获取到C的左子树F;调用inOrder方法,F不为null,获取到F的左子树I;调用inOrder方法,I不为null,获取I的左子树;调用inOrder方法,I的左子树为null,方法返回null;打印I节点的值I,结果HKDBEAI;
中序遍历7

(8)继续执行I的逻辑,获取I的右子树,调用inOrder方法,I的右子树为null,方法返回null;继续执行F的逻辑,打印F节点的值F,结果HKDBEAIF;
中序遍历8

(9)继续执行F的逻辑,获取F的右子树,调用inOrder方法,F的右子树为null,方法返回null;继续执行C的逻辑,打印C节点的值C,结果HKDBEAIFC;
中序遍历9

(10)继续执行C的逻辑,获取到C的右子树G,调用inOrder方法,G不为null,获取G的左子树;调用inOrder方法,G的左子树为null,方法返回null;打印G节点的值G,结果HKDBEAIFCG;
中序遍历10

(11)继续执行G的逻辑,获取到G的右子树J,调用inOrder方法,J不为null,获取J的左子树;调用inOrder方法,J的左子树为null,方法返回null;打印J节点的值J,结果HKDBEAIFCGJ;
中序遍历11

(12)继续执行J的逻辑,获取J的右子树,调用inOrder方法,J的右子树为null,方法返回null;至此所有的节点都已判断完成,中序遍历算法的最终结果为:HKDBEAIFCGJ。


中序遍历12

3.后序遍历算法

先来看代码

/**
 * 二叉树的后续遍历算法
 * 1.判断节点为空,返回空;
 * 2.判断是否存在左子树,如果存在,递归,回到步骤1;
 * 3.判断是否存在右子树,如果存在,递归,回到步骤1;
 * 4.打印节点数据;
 */
public class PostOrder {

    public void postOrder(TreeNode treeNode) {
        if (null == treeNode) {
            return;
        }
        TreeNode leftNode = treeNode.getLeft();
        postOrder(leftNode);
        TreeNode rightNode = treeNode.getRight();
        postOrder(rightNode);
        System.out.print(treeNode.getValue());
    }

}

测试代码

public class Test {

    public static void main(String[] args) {
        TreeNode[] treeNode = InitTree.initTree();
        PostOrder postOrder = new PostOrder();
        postOrder.postOrder(treeNode[0]);
    }

}

运行结果:KHDEBIFJGCA
程序是如何运行的?
(1)调用postOrder方法,传入的根节点A不为null,获取到A的左子树B;调用postOrder方法,B不为null,获取到B的左子树D;调用postOrder方法,D不为null,获取到D的左子树H;调用postOrder方法,H不为null,获取H的左子树;调用postOrder方法,H的左子树为null,方法返回null;继续执行H的逻辑,获取到H的右子树K;调用postOrder方法,K不为null,获取K的左子树;调用postOrder方法,K的左子树为null,方法返回null;继续执行K的逻辑,获取K的右子树,K的右子树为null,方法返回null;打印K节点的值K,结果K;


后序遍历1

(2)继续执行H的逻辑,打印H节点的值H,结果KH;


后序遍历2

(3)继续执行D的逻辑,获取D的右子树,D的右子树为null,方法返回null;打印D节点的值D,结果KHD;
后序遍历3

(4)继续执行B的逻辑,获取到B的右子树E;调用postOrder方法,E不为null,获取E的左子树;调用postOrder方法,E的左子树为null,方法返回null;继续执行E的逻辑,获取E的右子树,E的右子树为null,方法返回null;打印E节点的值E,结果KHDE;
后序遍历4

(5)继续执行B的逻辑,打印B节点的值B,结果KHDEB;


后序遍历5

(6)继续执行A的逻辑,获取到A的右子树C;调用postOrder方法,C不为null,获取到C的左子树F;调用postOrder方法,F不为null,获取到F的左子树I;调用postOrder方法,I不为null,获取I的左子树;调用postOrder方法,I的左子树为null,方法返回null;继续执行I的逻辑,获取I的右子树,I的右子树为null,方法返回null;打印I节点的值I,结果KHDEBI;
后序遍历6

(7)继续执行F的逻辑,获取F的右子树,F的右子树为null,方法返回null;打印F节点的值F,结果KHDEBIF;
后序遍历7

(8)继续执行C的逻辑,获取到C的右子树G;调用postOrder方法,G不为null,获取G的左子树;调用postOrder方法,G的左子树为null,方法返回null;继续执行G的逻辑,获取到G的右子树J;调用postOrder方法,J不为null,获取J的左子树;调用postOrder方法,J的左子树为null,方法返回null;继续执行J的逻辑,获取J的右子树,J的右子树为null,方法返回null;打印J节点的值J,结果KHDEBIFJ;
后序遍历8

(9)继续执行G的逻辑,打印G节点的值G,结果KHDEBIFJG;
后序遍历9

(10)继续执行C的逻辑,打印C节点的值C,结果KHDEBIFJGC;
后序遍历10

(11)继续执行A的逻辑,打印A节点的值A,结果KHDEBIFJGCA;
后序遍历11

(12)至此所有的节点都已判断完成,后序遍历算法的最终结果为:KHDEBIFJGCA。


后序遍历12

4.层序遍历算法

先来看代码

/**
 * 二叉树的层序遍历算法
 * 1.判断节点为空,返回空;
 * 2.否则按照节点从上到下,从左到右的顺序遍历节点信息;
 */
public class FloorOrder {

    public void floorOrder(TreeNode treeNode) {
        if (null == treeNode) {
            return;
        }
        LinkedList<TreeNode> list = new LinkedList<TreeNode>();
        list.add(treeNode);
        TreeNode pollTree;
        while (!list.isEmpty()) {
            pollTree = list.poll();
            System.out.print(pollTree.getValue());
            TreeNode left = pollTree.getLeft();
            if (null != left) {
                list.add(left);
            }
            TreeNode right = pollTree.getRight();
            if (null != right) {
                list.add(right);
            }
        }
    }

}

测试代码

public class Test {

    public static void main(String[] args) {
        TreeNode[] treeNode = InitTree.initTree();
        FloorOrder floorOrder = new FloorOrder();
        floorOrder.floorOrder(treeNode[0]);
    }

}

运行结果:ABCDEFGHIJK
层序遍历算法其实就是从树的根节点开始,按照从上到下,从左到右的顺序遍历所有节点信息。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 211,817评论 6 492
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,329评论 3 385
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 157,354评论 0 348
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,498评论 1 284
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 65,600评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,829评论 1 290
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,979评论 3 408
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,722评论 0 266
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,189评论 1 303
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,519评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,654评论 1 340
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,329评论 4 330
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,940评论 3 313
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,762评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,993评论 1 266
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,382评论 2 360
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,543评论 2 349

推荐阅读更多精彩内容