概述
樹是一種經常用到的資料結構，用來模擬具有樹狀結構性質的資料集合，樹的每一個節點有一個值和一個包含所有子節點的串列，二叉樹是一種更為典型的樹狀結構，每個節點最多有兩個子樹的樹結構，稱作左子樹和右子樹，
樹的遍歷
前序遍歷
前序遍歷首先訪問根節點，然后遍歷左子樹，最后遍歷右子樹，
F
/ \
/ \
B G
/ \ \
A D I
/ \ /
C E H
F->B->A-D-C-E->G->I->H
中序遍歷
中序遍歷是先遍歷左子樹，然后訪問根節點，最后遍歷右子樹，對于二叉搜索樹，可以通過中序遍歷得到一個遞增的有序序列，
F
/ \
/ \
B G
/ \ \
A D I
/ \ /
C E H
A->B->C->D->E->F->G->H->I
后序遍歷
后序遍歷是先遍歷左子樹，然后遍歷右子樹，最后訪問根節點，
F
/ \
/ \
B G
/ \ \
A D I
/ \ /
C E H
A-C->E->D->B->H->I->G->F
值得注意的是，洗掉樹中的節點時，洗掉程序將按照后序遍歷的順序進行，也就是說，洗掉一個節點時，首先洗掉它的左節點和它的右節點，然后洗掉節點本身，后序在數學表達中廣泛使用，例如AST
+
/ \
/ \
* 5
/ \
4 -
/ \
7 2
使用中序遍歷可以輕松的構建原始運算式(4*(7-2))+5，使用后序遍歷可以便捷的計算該運算式，每遇到一個運算子，可以從堆疊中彈出堆疊頂的兩個元素，計算結果回傳堆疊中，
每日一題：求二叉樹的最小深度
這可以看作是一個后序遍歷
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func minDepth(root *TreeNode) int {
if root == nil {
return 0;
}
if root.Left == nil {
return minDepth(root.Right) + 1;
}
if root.Right == nil {
return minDepth(root.Left) + 1;
}
return min(minDepth(root.Left), minDepth(root.Right)) + 1;
}
func min(x, y int) int {
if x < y {
return x;
}
return y;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/2196.html
標籤：其他