Python(20)MSDOSのtreeコマンドのように枝も出力する:いまいち編

前の関連記事：Python(19)二分木を出力する部分をwhile文で書く

結構ちょろくできると思っていたのが大間違いでした。四苦八苦してもう答えをみてやれ、と思ってFreeDOSのtreeコマンドのソースをみたのですが、理解できず、、、

各階層にある枝を二進数に置き換える

N
    G
        D
            B
                A
                C
            F
                E
                 
        K
            I
                H
                J
            M
                L
                 
    U
        R
            P
                O
                Q
            T
                S
                 
        X
            W
                V
                 
            Z
                Y

これの各ノードを結んでいる枝を出力したいのですけど、なかなかできません。

隣接している行のノードを結ぶ枝はわかるのですが、行が離れているノード同士を結ぶ線をどうして引いたらよいものか、、、

1行目からノードと一緒に枝を出力していこうと思っても同じ階層にまたノードがでてくるのかは予測できないので、最下行から出力していくことにしました。

最下行から枝を生やしていくとノードにぶつかったところで枝を終わらせればよいわけです。

各行での枝の位置をどう把握するのか悩みましたが結局二進数で枝のある階層を把握することにしました。

上記の二分木の場合は階層0から階層4まであります。

階層4に枝がくることはないので、枝の位置を把握する二進数は4桁でよいとわかります。

ノードが存在する行の上の階層にある枝は"└─"か"├─"になります。

あとは上行に向かってノードにぶつかるまで"│"を生やしていけばよいわけです。

"└─"か"├─"どちらの枝になるのかは下行から枝が生えてくるかどうかによって決定されます。

枝があるとき1、枝がないときを0にして上図の二分木の枝の情報を書き出してみます。

N          0000
├─G        1000
│ ├─D      1100
│ │ ├─B    1110
│ │ │ ├─A  1111
│ │ │ └─C  1111
│ │ └─F    1110
│ │   └─E  1101
│ │        1100
│ └─K      1100
│   ├─I    1010
│   │ ├─H  1011
│   │ └─J  1011
│   └─M    1010
│     └─L  1001
│          1000
└─U        1000
  ├─R      0100
  │ ├─P    0110
  │ │ ├─O  0111
  │ │ └─Q  0111
  │ └─T    0110
  │   └─S  0101
  │        0100
  └─X      0100
    ├─W    0010
    │ └─V  0011
    │      0010
    └─Z    0010
      └─Y  0001
           0000

うーん、ブラウザでずれないように見せるための調整に手間がかかってしまいました。

いまはSleipnir4で縦を合わしたので他のブラウザではずれるかもしれません。

以下にテキストファイルで縦にそろえたものも貼り付けておきます。

N                  0000
├─G              1000
│  ├─D          1100
│  │  ├─B      1110
│  │  │  ├─A  1111
│  │  │  └─C  1111
│  │  └─F      1110
│  │      └─E  1101
│  │             1100
│  └─K          1100
│      ├─I      1010
│      │  ├─H  1011
│      │  └─J  1011
│      └─M      1010
│          └─L  1001
│                 1000
└─U              1000
    ├─R          0100
    │  ├─P      0110
    │  │  ├─O  0111
    │  │  └─Q  0111
    │  └─T      0110
    │      └─S  0101
    │             0100
    └─X          0100
        ├─W      0010
        │  └─V  0011
        │         0010
        └─Z      0010
            └─Y  0001
                   0000

これはコピペしてメモ帳に貼り付ければ縦に揃って見えるはずです。

二進数を枝に出力するアルゴリズムを考える

最下行からみていって、ノードがある階層の一つ上の階層の桁を1にして、1の上の階層が1になったらその下の階層の桁を0に戻せばよさそうです。

いまさら気がつきましたがNが階層0でYが階層4ということは先に書いた4桁の二進数は左が1桁目になります。

これらを考慮して木を枝付きで出力するtree_repr()関数を書きました。

python20.py

N
├─G
│  ├─D
│  │  ├─B
│  │  │  ├─A
│  │  │  └─C
│  │  └─F
│  │      └─E
│  │        
│  └─K
│      ├─I
│      │  ├─H
│      │  └─J
│      └─M
│          └─L
│            
└─U
    ├─R
    │  ├─P
    │  │  ├─O
    │  │  └─Q
    │  └─T
    │      └─S
    │        
    └─X
        ├─W
        │  └─V
        │    
        └─Z
            └─Y

これでできたのはできたのですが、まず根からpostorder(帰りがけ順)にノードを取得したあとにそのスタックを後ろからみて枝をつけて、それをまた出力する、という3回もループを回してとても効率が悪いです。

参考にしたサイト

Index of /pub/micro/pc-stuff/freedos/files/dos/tree/
ここにあるzipファイルのなかにあるTREE.CがFreeDOSのtreeコマンドのソースです。

複数のフラグ(真偽値)を1つの整数値として扱う上でのメモ - 試験運用中なLinux備忘録
二進数の扱いが具体的に解説してありわかりやすいです。

次の関連記事:Python(21)二分木をMSDOSのtreeコマンドのように枝も出力する