アルゴリズムの木構造について、ご教示ください。

Question

アルゴリズムの木構造について、ご教示ください。アルゴリズムのデータ構造で、配列やリストと同列に並べられて、木構造が出てきます。
この部分で引っかかっています。
木構造はあくまで、処理の仕方とか、考え方のような気がしています。

木構造も、データ構造ということは、データの持ち方だと思うのですが、各ノードのデータの指定の仕方はどのようになるのでしょうか？
配列であれば、添字を指定してアクセスできる、リストであれば、ポインタを辿ってアクセスできる、となります。

では、木構造ではどうするのでしょうか？

リストのように、各ノードがポインタを持っているのでしょうか？
そうすると、木構造はこのポインタの動きを、ツリー形式で図示しただけのものでは？と感じられます。
そうすると、データの持ち方自体は、リストなのでしょうか、配列なのでしょうか？

自分でもなんと言えば良いのかわからず、とりとめのない内容となってます。
よろしければ、ご回答下さい。

Answer 1

C言語で実装される場合、各ノードがポインタを持っています。
木構造はリストと異なり、ノードが複数の子を持てますから、二分木であれば、親へのポインタと左の子、右の子へのポインタを持っている形になります。

データ構造とはデータの配置の仕方の事ですから、配列のようにメモリ上の連続した領域を確保するパターン、リストのようにメモリ領域の離れたところを一つ（または二つ）のポインタでつなぐパターン、木構造のように、一つの親と複数の子をつなぐパターン、ハッシュのように計算でジャンプ先を求めるパターンなどが考えられます。（それぞれのパターンで、データの検索、追加、削除にかかるコストが違ってきます。ビッグオー記法などによる計算オーダの話を勉強してみると、イメージがつかめると思います）

配列が添え字でアクセスできるのは、文法上便利だからたまたまそうなっているだけで、Cでは添え字アクセスはポインタのシンタックスシュガーですし、どのようにデータを指定するかはあまり重要ではないです。

Answer 2

＞リストなのでしょうか、配列なのでしょうか

お察しの通り、リストです

大抵は、木構造は自己参照構造体（リスト構造）のすごいバージョンとして説明されます

かんたんに言うと、リスト構造をすごくしたのが木構造です

お察しの通り、リストを豪華にしたのが木構造です