算法: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》
本文链接: https://www.pstips.net/traverse-tree.html
请尊重原作者和编辑的辛勤劳动,欢迎转载,并注明出处!

关于 Mooser Lee

我是一个Powershell的爱好者,创建了PowerShell中文博客,热衷于Powershell技术的搜集和分享。本站部分内容来源于互联网,不足之处敬请谅解,并欢迎您批评指正。

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注