二叉树的前序中序后序遍历 kotlin实现

例子：

26840968-b023aab75f5dd31f.jpg

kotlin代码表示此二叉树

 fun init() {
        var root = Node("A")
        var nodeB = Node("B")
        var nodeC = Node("C")
        var nodeD = Node("D")
        var nodeE = Node("E")
        var nodeF = Node("F")
        var nodeG = Node("G")
        var nodeH = Node("H")
        var nodeI = Node("I")

        root.leftNode = nodeB
        root.rightNode = nodeC

        nodeB.leftNode = nodeD
        nodeC.leftNode = nodeE
        nodeC.rightNode = nodeF

        nodeD.leftNode = nodeG
        nodeD.rightNode = nodeH

        nodeE.rightNode = nodeI
    }

目标（二叉树遍历的定义）：从根结点出发，按照某种次序，依次访问二叉树中所有结点每个结点被访问一次
前序遍历：根左右（若二叉树为空，则空操作返回，否则返回根结点，前后遍历前子树，在遍历右子树）
//前序遍历

//递归实现
 private fun preListRecurrence(root: Node?) {
        if (null != root) {
            println(root.value)
            preListRecurrence(root?.leftNode)
            preListRecurrence(root?.rightNode)
        }
    }

用最白痴的方法复原以下这个递归，总共调用了19次，遍历整个二叉树

image.png

//栈实现
 private fun preListStack(root: Node) {
        if (null != root) {
            var stack = Stack<Node>()
            stack.add(root)
            while (!stack.isEmpty()) {
                var root = stack.pop()
                if (null != root.rightNode) {
                    stack.push(root.rightNode)
                }
                if (null != root.leftNode) {
                    stack.push(root.leftNode)
                }
            }
        }
    }

//栈的数据变化

image.png

中序遍历 //目标 左中右
//递归实现

   private fun middleListRecurrence(root: Node?) {
        if (null != root) {
            middleListRecurrence(root.leftNode)
            print(root.value)
            middleListRecurrence(root.rightNode)
        }
    }
//栈实现
    private fun middleListStack(root: Node?) {
        var stack = Stack<Node>()
        var nodeCu = root
        while (null != nodeCu || !stack.isEmpty()) {
            while (null != nodeCu) {
                stack.push(nodeCu)
                nodeCu = nodeCu.leftNode
            }
            nodeCu = stack.pop()
            print(nodeCu.value)
            nodeCu = nodeCu.rightNode
        }
    }

后序遍历 //目标 左根中
//递归实现

 private fun lastListRecurrence(root: Node?) {
        if (null != root) {
            lastListRecurrence(root.leftNode)

            lastListRecurrence(root.rightNode)

            print(root.value)
        }
    }

//栈实现

private fun lastStackRecurrence(root: Node?) {
        var stack = Stack<Node>()
        //中间栈
        val output = Stack<Node>()
        var nodeCurr = root
        while (null != nodeCurr || !stack.isEmpty()) {
            if (null != nodeCurr) {
                output.push(nodeCurr)
                stack.push(nodeCurr)
                nodeCurr = nodeCurr.rightNode
            } else {
                nodeCurr = stack.pop()
                nodeCurr = nodeCurr.leftNode
            }
        }
        while (!output.isEmpty()) {
            print(output.pop().value)
        }
    }

完整代码

package com.hgc.studykotlin

import java.util.*

class TestTree {
    companion object {
        @JvmStatic
        fun main(args: Array<String>) {
            NodeOperation().init()
        }
    }
}

class NodeOperation {
    fun init() {
        var root = Node("A")
        var nodeB = Node("B")
        var nodeC = Node("C")
        var nodeD = Node("D")
        var nodeE = Node("E")
        var nodeF = Node("F")
        var nodeG = Node("G")
        var nodeH = Node("H")
        var nodeI = Node("I")

        root.leftNode = nodeB
        root.rightNode = nodeC

        nodeB.leftNode = nodeD
        nodeC.leftNode = nodeE
        nodeC.rightNode = nodeF

        nodeD.leftNode = nodeG
        nodeD.rightNode = nodeH

        nodeE.rightNode = nodeI

        println()
        preListStack(root)

        println()
        preListRecurrence(root)

        println()
        middleListStack(root)

        println()
        middleListRecurrence(root)

        println()
        lastListRecurrence(root)

        println()
        lastStackRecurrence(root)
    }

    private fun preListStack(root: Node) {
        if (null != root) {
            var stack = Stack<Node>()
            stack.add(root)
            while (!stack.isEmpty()) {
                var root = stack.pop()
                print(root.value)
                if (null != root.rightNode) {
                    stack.push(root.rightNode)
                }
                if (null != root.leftNode) {
                    stack.push(root.leftNode)
                }
            }
        }
    }

    private fun preListRecurrence(root: Node?) {
        if (null != root) {
            print(root.value)
            preListRecurrence(root.leftNode)
            preListRecurrence(root.rightNode)
        }
    }

    private fun middleListStack(root: Node?) {
        var stack = Stack<Node>()
        var nodeCu = root
        while (null != nodeCu || !stack.isEmpty()) {
            while (null != nodeCu) {
                stack.push(nodeCu)
                nodeCu = nodeCu.leftNode
            }
            nodeCu = stack.pop()
            print(nodeCu.value)
            nodeCu = nodeCu.rightNode
        }
    }

    private fun middleListRecurrence(root: Node?) {
        if (null != root) {
            middleListRecurrence(root.leftNode)
            print(root.value)
            middleListRecurrence(root.rightNode)
        }
    }

    private fun lastStackRecurrence(root: Node?) {
        var stack = Stack<Node>()
        //中间栈
        val output = Stack<Node>()
        var nodeCurr = root
        while (null != nodeCurr || !stack.isEmpty()) {
            if (null != nodeCurr) {
                output.push(nodeCurr)
                stack.push(nodeCurr)
                nodeCurr = nodeCurr.rightNode
            } else {
                nodeCurr = stack.pop()
                nodeCurr = nodeCurr.leftNode
            }
        }
        while (!output.isEmpty()) {
            print(output.pop().value)
        }
    }

    private fun lastListRecurrence(root: Node?) {
        if (null != root) {
            lastListRecurrence(root.leftNode)

            lastListRecurrence(root.rightNode)

            print(root.value)
        }
    }
}

class Node(var value: String) {
    var leftNode: Node? = null
    var rightNode: Node? = null
}

问题1，已知前序 中序求后序
问题2，已知中序 后序求前序
问题3，中序和后序已知，可以推出前序吗，如果不能原因？