問三番なのですが、一度葉から根まで辿り、その後根から葉まで辿るのはなぜなのでしょうか。
最初から根から葉に辿れば良いのではないでしょうか。
また、kの値をk←parent［k］の式などが無くても、ひとつづつ辿ることはできるのでしょうか。
どなたか回答お願いします。

>問三番なのですが、一度葉から根まで辿り、その後根から葉まで辿るのはなぜなのでしょうか。
>最初から根から葉に辿れば良いのではないでしょうか。
このプログラムは図2にあるように B => 010 の変換を目的としたものです。
根から辿ろうとすると、最初の分岐で左右どちらに辿ればいいか分かりません。
そのため、初めに葉から根に向かい、ルートを確定させたうえで、根から葉に向かい、ビット列を構築するという手順になっています。

>また、kの値をk←parent［k］の式などが無くても、ひとつづつ辿ることはできるのでしょうか。
プログラムの3行目で Encode(parent[k], parent, left) と再度Encodeを呼び出しています。(説明(3)にも「再帰的に」呼び出すと書かれています。)
再帰呼び出しのトレースは頭が混乱しやすいですが、頑張ってトレースしてみてください。