P15 二叉树前中后层序遍历(递归+迭代)

﹏ヽ暗。殇╰゛Y 2022-08-30 11:21 38阅读 0赞

package main
    
    import (
    	"fmt"
    
    	"github.com/emirpasic/gods/stacks/arraystack"
    )
    
    // 前序遍历: 根左右
    // 中序遍历: 左根右
    // 后序遍历: 左右根
    // 层序遍历: 从上往下、从左往右
    // 递归遍历: 使用递归方法遍历
    // 迭代遍历: 使用迭代方法实现递归遍历
    
    type Node struct { 
    	Value int
    	Left  *Node
    	Right *Node
    }
    
    func NewTree() *Node { 
    	// 第四层
    	left42 := &Node{ Value: 6}
    	right42 := &Node{ Value: 7}
    	// 第三层
    	left31 := &Node{ Value: 4}
    	right31 := &Node{ Value: 5, Left: left42, Right: right42}
    	// 第二层
    	left21 := &Node{ Value: 2, Left: left31, Right: right31}
    	right21 := &Node{ Value: 3}
    	return &Node{ Value: 1, Left: left21, Right: right21}
    }
    
    // 前序先打印根->打印左->打印右
    func recursion01(node *Node) { 
    	if node == nil { 
    		return
    	}
    	fmt.Print(node.Value)
    	recursion01(node.Left)
    	recursion01(node.Right)
    }
    
    // 中序先打印左->打印根->打印右
    func recursion02(node *Node) { 
    	if node == nil { 
    		return
    	}
    	recursion02(node.Left)
    	// 直至左边遍历完(找到最左叶子)才打印根
    	fmt.Print(node.Value)
    	// 根打印完打印右(找最右叶子)
    	recursion02(node.Right)
    }
    
    // 后序先打印左->打印右->打印根
    func recursion03(node *Node) { 
    	if node == nil { 
    		return
    	}
    	defer fmt.Print(node.Value)
    	recursion03(node.Left)
    	recursion03(node.Right)
    }
    
    func rin04(node *Node, ss map[int][]*Node, index int) { 
    	if node == nil { 
    		return
    	}
    	ss[index] = append(ss[index], node)
    	index++
    	rin04(node.Left, ss, index)
    	rin04(node.Right, ss, index)
    }
    
    // 层序
    func recursion04(node *Node) { 
    	var ss = make(map[int][]*Node) // [第几层][]{当前层有谁}
    	curr := node
    	rin04(curr, ss, 0)
    	for i := 0; i < len(ss); i++ { 
    		for _, item := range ss[i] { 
    			fmt.Print(item.Value)
    		}
    	}
    }
    
    // 迭代前序: 根左右
    func iteration01(root *Node) { 
    	stack := arraystack.New()
    	stack.Push(root)
    	for !stack.Empty() { 
    		v, _ := stack.Pop()
    		val, _ := v.(*Node)
    		fmt.Print(val.Value)
    		if val.Right != nil { 
    			stack.Push(val.Right)
    		}
    		if val.Left != nil { 
    			stack.Push(val.Left)
    		}
    
    	}
    }
    
    // 迭代中序: 左根右
    func iteration02(root *Node) { 
    	stack := arraystack.New()
    	for curr := root; !stack.Empty() || curr != nil; { 
    		if curr != nil {  // 一直入栈直到最左叶子
    			stack.Push(curr)
    			curr = curr.Left
    		} else { 
    			v, _ := stack.Pop() // 出栈
    			val, _ := v.(*Node)
    			fmt.Print(val.Value) // 4
    			curr = val.Right     // 将该元素的右节点入栈
    		}
    	}
    }
    
    // 迭代后序: 左右根
    func iteration03(root *Node) { 
    	stack := arraystack.New()
    	for curr := root; !stack.Empty() || curr != nil; { 
    		for curr != nil {  // 一直入栈直到最左叶子
    			stack.Push(curr)
    			curr = curr.Left
    		}
    		// 取叶子
    		v, _ := stack.Pop() // 4,2#
    		val, _ := v.(*Node)
    		if val.Right == nil { 
    			fmt.Print(val.Value)
    		} else {  // 有右叶子，找右叶子的最左子叶
    			curr = val.Right
    			val.Right = nil // 拿右节点去遍历后，取消关系
    			stack.Push(val)
    		}
    	}
    }
    
    // 层序
    func iteration04(node *Node) { 
    	curr := []*Node{ node}
    	for curr != nil { 
    		next := func(list []*Node) (after []*Node) { 
    			for _, item := range list { 
    				fmt.Print(item.Value)
    				if item.Left != nil { 
    					after = append(after, item.Left)
    				}
    				if item.Right != nil { 
    					after = append(after, item.Right)
    				}
    			}
    			return
    		}(curr)
    		curr = next
    	}
    }
    
    func method1() { 
    	t := NewTree()
    	fmt.Print("递归前序遍历: ")
    	recursion01(t)
    	fmt.Print("\n迭代前序遍历: ")
    	iteration01(t)
    }
    func method2() { 
    	t := NewTree()
    	fmt.Print("\n递归中序遍历: ")
    	recursion02(t)
    	fmt.Print("\n迭代中序遍历: ")
    	iteration02(t)
    }
    func method3() { 
    	t := NewTree()
    	fmt.Print("\n递归后序遍历: ")
    	recursion03(t)
    	fmt.Print("\n迭代后序遍历: ")
    	iteration03(t)
    }
    func method4() { 
    	t := NewTree()
    	fmt.Print("\n递归层序遍历: ")
    	recursion04(t)
    	fmt.Print("\n迭代层序遍历: ")
    	iteration04(t)
    }
    func main() { 
    	method1()
    	method2()
    	method3()
    	method4()
    }