Java数据结构与算法(3) 寻找中序遍历时的下一个结点

前言

今天一天没有什么状态,学习效率太低了。今天重新温习了一下树的遍历,如何寻找中序遍历的下一个结点。接下来的计划是学习Spring Boot 和 算法与数据结构。


思路

算法与数据结构是我最薄弱的一环。每次写关于算法的代码时,都无法下手,经常陷入到逻辑的死胡同里。真心感觉自己的逻辑能力好差,思路混乱。程序员最重要的是思考和逻辑能力,只有把思路理清楚了,代码才能一气呵成。

  • 中序遍历:首先按照中序遍历的方式去访问根结点的左子树,然后访问根结点,最后按照中序遍历的方式去访问根结点的右子树。

首先看图

image.png

  • P表示父结点,N代表子结点。L表示N的左子树,R表示N的右子树。
  • 我们肯定是采用递归的方式。当结点是L的时候,无关。当R != null的时候,我们返回R结点下面的第一个结点,即下一个结点。如果R == null的时候,我们下一个结点肯定是要往上面走,在P != null下的情况,如果NP的左子树,那么下一个结点就是P如果N不是P的左子树的话,我们需要一直往父亲结点走,直到是某一个结点的左子树,下一个结点即为所求。

代码实现

  • 定义一个MyTreeNode.java。包含以下属性:结点的值,左子树,右子树,父亲结点。
public class MyTreeNode {

    private final char value;
    private MyTreeNode left;
    private MyTreeNode right;
    private MyTreeNode parent;

    public MyTreeNode(char value) {
        super();
        this.value = value;
        this.left = null;
        this.right = null;
        this.parent = null;
    }

    public MyTreeNode getLeft() {
        return left;
    }

    public void setLeft(MyTreeNode left) {
        this.left = left;

        if (left != null) {
            this.left.setParent(this);
        }
    }

    public MyTreeNode getRight() {
        return right;
    }

    public void setRight(MyTreeNode right) {
        this.right = right;

        if (right != null) {
            this.right.setParent(this);
        }
    }

    public MyTreeNode getParent() {
        return parent;
    }

    private void setParent(MyTreeNode parent) {
        this.parent = parent;
    }

    public char getValue() {
        return value;
    }
}
  • 我们自己手动去创建一根这样的树。

image.png 显而易见,前序遍历是ABDEGCF,中序遍历是DBGEACF,后序遍历是DGEBFCA

  • 如何通过前序遍历和中序遍历推出树的结构呢?其实很简单,前序遍历中第一个元素肯定是根结点。我们在从中序遍历中找到该根结点,那么根结点左边的元素就是左子树,右边的元素就是右子树呢。然后递归的给每一个结点设置左子树和右子树。一根完整的二叉树就形成了。简单轻松,贴上代码。
public class MyTreeNodeCreator {

    public static MyTreeNode sampleTree() {
        MyTreeNode root = new MyTreeNode('A');
        root.setLeft(new MyTreeNode('B'));
        root.setRight(new MyTreeNode('C'));
        root.getLeft().setLeft(new MyTreeNode('D'));
        root.getLeft().setRight(new MyTreeNode('E'));
        root.getLeft().getRight().setLeft(new MyTreeNode('G'));
        root.getRight().setRight(new MyTreeNode('F'));

        return root;
    }

    public static MyTreeNode customTree(String font, String mid) {
        if (StringUtils.isEmpty(font)) {
            return null;
        }

        char rootValue = font.charAt(0);
        int index = mid.indexOf(rootValue);
        MyTreeNode root = new MyTreeNode(rootValue);

        root.setLeft(customTree(font.substring(1, index + 1), mid.substring(0, index)));
        root.setRight(customTree(font.substring(index + 1), mid.substring(index + 1)));

        return root;
    }

    public static void behindOrder(MyTreeNode node) {
        if (node == null) {
            return;
        }

        behindOrder(node.getLeft());
        behindOrder(node.getRight());

        System.out.print(node.getValue() + " ");
    }

    public static String displayBehindOrder(String font, String mid) {
        if (StringUtils.isEmpty(font)) {
            return "";
        }

        char rootValue = font.charAt(0);
        int index = mid.indexOf(rootValue);

        return displayBehindOrder(font.substring(1, index + 1), mid.substring(0, index))
                + displayBehindOrder(font.substring(index + 1), mid.substring(index + 1)) + rootValue;
    }
}
  • 接着我们根据二叉树,寻找中序遍历时的下一个结点。先一般后特殊,要进行边界控制,每次必须向前推进循环不变式中涉及的变量值。
public class InOrder {

    public MyTreeNode next(MyTreeNode node) {
        if (node == null) {
            return null;
        }

        if (node.getRight() != null) {
            return first(node.getRight());
        } else {
            while (node.getParent() != null && node.getParent().getLeft() != node) {
                node = node.getParent();
            }

            return node.getParent();
        }
    }

    /**
     * Gets first node
     *
     * @param node
     * @return
     */
    public MyTreeNode first(MyTreeNode node) {
        if (node == null) {
            return null;
        }

        MyTreeNode curNode = node;

        while (curNode.getLeft() != null) {
            curNode = curNode.getLeft();
        }

        return curNode;
    }
}
  • 核心代码完成,我们开始写测试demo。我们需要编写测试用例,要遵守BCDE原则,以保证被测试模块的交付质量。
    • BBorder,边界值测试,包括循环边界,特殊取值,特殊时间点,数据顺序等。
    • CCorrect,正确的输入,并得到预期的结果。
    • DDesign,与设计文档相结合,来编写单元测试。
    • EError,强制错误信息的输入(如:非法数据,异常流程,非业务允许输入等),并得到预期的结果。

运行Demo,输出和我们预期一样的结果。

image.png

public class Demo {
    private static InOrder inOrder = new InOrder();

    public static void main(String[] args) {
        printMidOrder();
    }

    public static void printBehindOrder() {
        MyTreeNode root = MyTreeNodeCreator.customTree("ABDEGCF", "DBGEACF");
        MyTreeNodeCreator.behindOrder(root);
        MyTreeNodeCreator.behindOrder(MyTreeNodeCreator.customTree("ABCD", "ABCD"));
    }

    public static void printMidOrder() {
        MyTreeNode sampleTree = MyTreeNodeCreator.sampleTree();
        display(sampleTree);
        display(MyTreeNodeCreator.customTree("", ""));
        display(MyTreeNodeCreator.customTree("A", "A"));
        display(MyTreeNodeCreator.customTree("AB", "BA"));
        display(MyTreeNodeCreator.customTree("ABCD", "DCBA"));
        display(MyTreeNodeCreator.customTree("ABCD", "ABCD"));
    }

    public static void display(MyTreeNode sampleTree) {
        for (MyTreeNode root = inOrder.first(sampleTree); root != null; root = inOrder.next(root)) {

            System.out.print(root.getValue());
        }
        System.out.println(" ");
    }
}

尾言

我感觉数据结构和算法,思路是最重要的。只要有思路了,代码就水到渠成。没有思路,任何华丽的代码都是徒劳的。

虽然有些数据结构和算法已经掌握了,但是想要简单形象的表达出来,对于我来说还是十分困难的。继续加油。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏desperate633

LintCode 二叉树的锯齿形层次遍历题目分析代码

给出一棵二叉树,返回其节点值的锯齿形层次遍历(先从左往右,下一层再从右往左,层与层之间交替进行)

9730
来自专栏大数据和云计算技术

算法基础7:平衡查找树概述

算法是基础,小蓝同学准备些总结一系列算法分享给大家,这是第7篇《平衡查找树概述》,非常赞!希望对大家有帮助,大家会喜欢! 前面系列文章: 归并排序 #算法...

34590
来自专栏撸码那些事

【图解数据结构】 二叉树遍历

34140
来自专栏算法修养

FZU 1064 教授的测试(卡特兰数,递归)

Problem 1064 教授的测试 Accept: 149 Submit: 364 Time Limit: 1000 mSec Memor...

36780
来自专栏计算机视觉与深度学习基础

Leetcode 124 Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum. For this problem, a path is de...

22190
来自专栏JavaEdge

二分查找复杂度分析

41750
来自专栏恰童鞋骚年

数据结构基础温故-4.树与二叉树(上)

前面所讨论的线性表元素之间都是一对一的关系,今天我们所看到的结构各元素之间却是一对多的关系。树在计算机中有着广泛的应用,甚至在计算机的日常使用中,也可以看到树形...

11830
来自专栏java一日一条

Calendar 详解

究竟什么是一个 Calendar 呢?中文的翻译就是日历,那我们立刻可以想到我们生活中有阳(公)历、阴(农)历之分。它们的区别在哪呢?

9110
来自专栏专注 Java 基础分享

Java 中的时间日期 API

47170
来自专栏java一日一条

Calendar 详解

究竟什么是一个 Calendar 呢?中文的翻译就是日历,那我们立刻可以想到我们生活中有阳(公)历、阴(农)历之分。它们的区别在哪呢?

5810

扫码关注云+社区

领取腾讯云代金券