算法：PowerShell如何后续遍历树结构

以前老师有讲过，《数据结构》这门课很重要，工作的过程中遇到的概率非常大。一点都不假，既然遇到了，就温习一下。

二叉树最经典了，后序遍历的规则是：先访问左节点，再访问右节点，最后访问根节点。那就以这个规则，推广至多叉树。

我们假设树的结构已经用PowerShell定义好了：

$Tree = @{
    Name='差旅费'
    Child=@(
        @{
        Name='机票费'
        Child=@(
            @{
               Name='国内机票'
            },
            @{
               Name='国际机票'
            }
            )
        },
        @{
        Name='火车费'
        },
        @{
        Name='酒店费'
             Child=@(
            @{
               Name='一星级酒店'
            },
            @{
               Name='五星级酒店'
            })
        },
        @{
        Name='招待费'
               Child=@(
            @{
               Name='日本按摩'
            },
            @{
               Name='韩国大保健'
            }
            )
        },
        @{
         Name='上网费'
         Child=@(
            @{
               Name='看电影'
            },
            @{
               Name='访问《PowerShell中文博客：PSTips.NET》'
            })
         }
        )
}

接下来演示整个思考的过程，凭着直觉先写出了第一个遍历函数：

function Traverse-Tree1{
param($root)
    $stack = New-Object System.Collections.Stack
    $stack.Push($root)
    while($stack.Count -gt 0){
        $item = $stack.Pop()
        $item.Name
        if($item.Child.Count -gt 0){
            $item.Child | foreach{
            $stack.Push($_)
            }
        }
    }
}

输出为：

差旅费
上网费
访问《PowerShell中文博客：PSTips.NET》
看电影
招待费
韩国大保健
日本按摩
酒店费
五星级酒店
一星级酒店
火车费
机票费
国际机票
国内机票

虽然每个节点都访问到了，但是原需求中还要求输出层级关系，并且只输出叶子节点，改动如下：

function Traverse-Tree2{
param($root)
    $stack = New-Object System.Collections.Stack
    $stack.Push($root)
    while($stack.Count -gt 0){
        $item = $stack.Pop()
        if($item.Child.Count -gt 0){
            $item.Child | foreach{
            $_.Name = '{0}->{1}' -f $item.Name , $_.Name
            $stack.Push($_)
            }
        }
        else{
            $item.Name
        }  
    }
}

输出为：

差旅费->上网费->访问《PowerShell中文博客：PSTips.NET》
差旅费->上网费->看电影
差旅费->招待费->韩国大保健
差旅费->招待费->日本按摩
差旅费->酒店费->五星级酒店
差旅费->酒店费->一星级酒店
差旅费->火车费
差旅费->机票费->国际机票
差旅费->机票费->国内机票

当我沾沾自喜准备收工时，发现节点的顺序不是期望的后序遍历。

此时，我意识到问题虽小，那是也马虎不得，应当静下心来下把算法在草稿纸上写出来，然后再考虑代码实现。

1. 根节点 入栈
2. 检查栈顶元素，
   2.1 如果没有子节点，输出该节点，并出栈
   2.2 如果有子节点，且所有的子节点都被访 问过，输出该节点，并出栈
   2.3 否则标志该子节点被访问过，并将子节点压入堆栈
   2.4 重复步骤2，直到栈为空

下面才是正解：

function Traverse-Tree3{
param($root)
    $stack = New-Object System.Collections.Stack
    # 1.根节点入栈
    $stack.Push(@{Node=$root;Index=0})
    while($stack.Count -gt 0){
        # 2. 检查栈顶元素
        $item = $stack.Peek()
        # 2.1 如果没有子节点，输出该节点，并出栈
        # 2.2 如果有子节点，且所有的子节点都被访问过，输出该节点，并出栈
        if(($item.Node.Child.Count -eq 0) -or ($item.Index -eq $item.Node.Child.Count)){
            if($item.Node.Child.Count -eq 0)
            {
               $item.Node.Name
            }
            $null = $stack.Pop()
        }
        # 2.3 否则标志该子节点被访问过，并将子节点压入堆栈，重复2，
        else{
          $child = @{Node = $item.Node.Child[$item.Index];Index=0}
          $child.Node.Name = '{0}->{1}' -f $item.Node.Name , $child.Node.Name
          $stack.Push($child)
          $item.Index = $item.Index+1
        }
        # 2.4 重复步骤2，直到栈为空
    }
}

输出为：

差旅费->机票费->国内机票
差旅费->机票费->国际机票
差旅费->火车费
差旅费->酒店费->一星级酒店
差旅费->酒店费->五星级酒店
差旅费->招待费->日本按摩
差旅费->招待费->韩国大保健
差旅费->上网费->看电影
差旅费->上网费->访问《PowerShell中文博客：PSTips.NET》