105商業類技藝競賽試題Problem3

*這兩題解題時間是前面問題一、二的加總，感謝台灣商管教材研發學會的教學影片

問題一、是否為堆積樹(Heap tree)或二元搜尋樹(Binary search tree)

判斷Heap Tree的條件為左右子節點都比其父節點大/小即為最大/最小堆積樹
判斷Binary Tree的條件為左子節點都比其父節點小而右子節點都比其父節點大即為二元搜尋樹

所以重點在於，判斷節點的大小

 Private Function FindMax(nodes() As Integer, root As Integer, upperBound As Integer) As Integer

        If root > upperBound Then Return Integer.MinValue

        Dim t As Integer = Math.Max(FindMax(nodes, 2 * root + 1, upperBound), FindMax(nodes, 2 * root + 2, upperBound))

        Dim Max As Integer = Math.Max(nodes(root), t)

        Return Max

    End Function

以遞迴方式，每個節點都會看做Root點，以判斷最大堆積樹為例

Private Function isMaxHeap(nodes() As Integer) As Boolean

        Dim U As Integer = nodes.GetUpperBound(0)

        Dim i As Integer = 0

        For i = 0 To U

            If nodes(i) < FindMax(nodes, 2 * i + 1, U) Or

            nodes(i) < FindMax(nodes, 2 * i + 2, U) Then

                Return False

            End If

        Next

        Return True

    End Function

就可以FindMax判斷左右子節點是否符合條件

---

問題二:後序表示法（post-order）

此題重點在如何利用前序(preorder)和中序(inorder)來建立Tree，

再用後序(postorder)表示

程式碼重點：
Node Class中包含左子樹、右子樹與值
Pivot:切割點的值，前序的開頭都為父節點/根節點
Index:切割點→知道切割點左邊即是左子樹的數量LeftChildNum
即可以遞迴方式，製造左子樹與右子樹
之後再補詳細講解吧，So Hard~

 Private Function BuildTree(preOrder() As String, inOrder() As String, PreStart As Integer, PreBound As Integer, InStart As Integer, InBound As Integer, ByRef binTree As BinarySearchTree)



        Dim MyNode As New Node

        If PreStart > PreBound Then Return Nothing

        If IsNothing(binTree.Root) Then binTree.Root = MyNode

        Dim Pivot As String = preOrder(PreStart)

        MyNode.value = Pivot

        Dim Index As Integer = Array.IndexOf(inOrder, Pivot, InStart, InBound - InStart + 1)

        Dim LeftChildNum As Integer = Index - InStart

        MyNode.left = BuildTree(preOrder, inOrder, PreStart + 1, PreStart + LeftChildNum, InStart, Index - 1, binTree)

        MyNode.right = BuildTree(preOrder, inOrder, PreStart + LeftChildNum + 1, PreBound, Index + 1, InBound, binTree)

        Return MyNode


    End Function

Class BinarySearchTree
    Public Root As New Node
    Public PostOrderList As New ArrayList
    Public Sub New()
        Root = Nothing
    End Sub

    Public Sub GenPostOrderList()
        PostOrderList.Clear()
        PostOrder(Root)
    End Sub

    Public Sub PostOrder(tempRoot As Node)
        If Not (tempRoot Is Nothing) Then
            PostOrder(tempRoot.left)
            PostOrder(tempRoot.right)
            PostOrderList.Add(tempRoot.value)

        End If
    End Sub
    Public Function ShowPostOrderList(TList As ArrayList) As String
        Dim U As Integer = TList.Count - 1
        Dim i As Integer
        Dim Ans As String = ""
        For i = 0 To U
            Ans = Ans & TList.Item(i) & ","
        Next
        Return Ans.Substring(0, Ans.Length - 1)

    End Function
End Class