例子：
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
}
目標(biāo)（二叉樹遍歷的定義）：從根結(jié)點(diǎn)出發(fā)，按照某種次序，依次訪問二叉樹中所有結(jié)點(diǎn)每個(gè)結(jié)點(diǎn)被訪問一次
前序遍歷：根左右（若二叉樹為空，則空操作返回，否則返回根結(jié)點(diǎn)挎挖，前后遍歷前子樹，在遍歷右子樹）
//前序遍歷
//遞歸實(shí)現(xiàn)
private fun preListRecurrence(root: Node?) {
if (null != root) {
println(root.value)
preListRecurrence(root?.leftNode)
preListRecurrence(root?.rightNode)
}
}
用最白癡的方法復(fù)原以下這個(gè)遞歸航夺，總共調(diào)用了19次，遍歷整個(gè)二叉樹
image.png
//棧實(shí)現(xiàn)
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)
}
}
}
}
//棧的數(shù)據(jù)變化
image.png
中序遍歷 //目標(biāo) 左中右
//遞歸實(shí)現(xiàn)
private fun middleListRecurrence(root: Node?) {
if (null != root) {
middleListRecurrence(root.leftNode)
print(root.value)
middleListRecurrence(root.rightNode)
}
}
//棧實(shí)現(xiàn)
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
}
}
后序遍歷 //目標(biāo) 左根中
//遞歸實(shí)現(xiàn)
private fun lastListRecurrence(root: Node?) {
if (null != root) {
lastListRecurrence(root.leftNode)
lastListRecurrence(root.rightNode)
print(root.value)
}
}
//棧實(shí)現(xiàn)
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，中序和后序已知冷蚂，可以推出前序嗎缭保，如果不能原因？
