- ベストアンサー
StandardMLの二分木に関する問題で困っています。
StandardMLで二分木を左右反転する関数reflect:'a tree->'a treeを作成したい。 実行例；reflect(tree) 二分木を表すデータ型 datatype 'a tree=Empty | Node of 'a *'a tree * 'a tree;
- yu-ki8877
- お礼率31% (5/16)
- その他（プログラミング・開発）
- 回答数2
- ありがとう数1
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
reflect の引数は 'a tree なんだけど, それは Empty か Node かのいずれかです. で, Empty のときには単純に Empty を返せばいいので reflect(Empty) = Empty と書けます. 一方, Node のときは reflect(Node(root, left, right)) とマッチングさせればよく, これにより Node の対応する要素が root, left, right に束縛されます. これらの変数を使って「どのような二分木を作るのか」を書いてやる. 単にこのノードで左右を入れ替えるだけなら reflect(Node(root, left, right)) = Node(root, right, left) だけど, 左右の部分木でも入れ替える必要があります. そしてそれは left および right のそれぞれに対して reflect を再帰的に適用すればできるはず, ですね.
その他の回答 (1)
- Tacosan
- ベストアンサー率23% (3656/15482)
困ってるのはわかるけど, 自分で解こうという気はちょっとでもありましたか? もし解こうという気があったのなら, 何かは考えたはずです. それを書いてください. もし自分で解こうという気がないなら, ここで質問する資格はありません. 諦めてください.
補足
申し訳ありませんでした。実際にプログラムを書くことはできませんでしたが、アルゴリズムは考えることができてます。 二分木の右部分木と左部分木をそれぞれの節点で入れ替える作業を行えばよいということは分かりますが、実際にどのように右部分木を指定して入れ替えれば良いかが分かりません。 教えてください。よろしくお願いします。
関連するQ&A
- haskellでの木構造処理でエラー
「すごいhaskellたのしく学ぼう！」という本でhaskellを勉強している者です。 現在haskellでの木構造の処理について部分を読んでいるんですが、この本のサンプル通りにやってもうまくいきません。 以下がそのサンプルです。 data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show) data Direction = L | R deriving (Show) type Directions = [Direction] freeTree :: Tree Char freeTree = Node 'P' (Node 'O' (Node 'L' (Node 'N' Empty Empty) (Node 'T' Empty Empty) ) (Node 'Y' (Node 'S' Empty Empty) (Node 'A' Empty Empty) ) ) (Node 'L' (Node 'W' (Node 'C' Empty Empty) (Node 'R' Empty Empty) ) (Node 'A' (Node 'A' Empty Empty) (Node 'C' Empty Empty) ) ) changeToP :: Directions -> Tree Char -> Tree Char changeToP (L:ds) (Node x l r) = Node x (changeToP ds l) r changeToP (R:ds) (Node x l r) = Node x l (changeToP ds r) changeTop [] (Node _ l r) = Node 'P' l r 簡単に説明すると、 changeToP Directions (Tree Char) で Directions に従い木を再帰的に処理し、ノードの文字をPに変更した木を返します。 例えば changeToP [R,L] freeTree とすると Node 'P' (Node 'O' (Node 'L' (Node 'N' Empty Empty) (Node 'T' Empty Empty) ) (Node 'Y' (Node 'S' Empty Empty) (Node 'A' Empty Empty) ) ) (Node 'L' (Node 'P' -- ここが'W'から'P'に変わります (Node 'C' Empty Empty) (Node 'R' Empty Empty) ) (Node 'A' (Node 'A' Empty Empty) (Node 'C' Empty Empty) ) ) となります（'W'が'P'に変わります）。 しかしこれがうまく行きません これをそのまま評価すると Node 'P' (Node 'O' (Node 'L' (Node 'N' Empty Empty) (Node 'T' Empty Empty)) (Node 'Y' (Node 'S' Empty Empty) (Node 'A' Empty Empty))) (Node 'L' *** Exception: /Documents/foo.hs:(25,1)-(26,57): Non-exhaustive patterns in function changeToP といったエラーを吐きます。 「パターンが徹底されていない」といった意味のエラーのようなんですが、パターンマッチは完璧だと思います。 ていうか、そもそも本のサンプル通りに書いてます。 本ではこれでうまくいくようなんですが自分の環境ではこのざまです。 何がいけないでしょうか。 ちなみにOSはmac os x 10.7.5で、haskell処理系はghc 7.4.2です。 よろしくお願いします。
- ベストアンサー
- その他（プログラミング・開発）
- C言語 2分木探索について質問です
Ｃ言語初心者です。 2分木構造体 struct node{ int data; Tree left_subtree; Tree right_subtree; } を上記のように定義した場合、 2分木の根節点のポインタ struct node *Tree を引数として与えられたとき、 2分木内の節点に保持された整数データの総和を戻り値として返す関数 int sum_data(Tree t);を再帰呼び出しで作成してみたのですが、正しいでしょうか？ ■2分木内の節点に保持された整数データの総和を戻り値として返す関数 int sum_data(Tree t) { // 左分木、右分木のどちらも存在しなければ根節点の値を返す if ((t->left_subtree == NULL) && (t->right_subtree == NULL)) { return t->data; } else// どちらか存在していれば再帰呼び出しする { return (t->data + sum_data(t->left_subtree) + sum_data(t->right_subtree)) } } ご指摘ありましたら、お願いしますm(_ _)m
- ベストアンサー
- C・C++・C#
- 二分木のデータ入力について
C言語についての質問です。 キューと再起関数を使って2分木にデータを入れようとしたところ、以下のようなエラーが発生いたしました。 ddd.c: 関数 ‘dequeue’ 内: ddd.c:80:9: 警告: 戻りでポインタからキャスト無しに整数を作成しています [-Wint-conversion] return x; ^ ddd.c: 関数 ‘growTree’ 内: ddd.c:100:14: エラー: assignment to expression with array type x->sentence = dequeue(); なんとか解消しようとするのですが、どうしてもエラーが増えるばかりで、うまくいきませんでした。 どの部分をどのように直せばいいのか大変お手数ですが、教えていただけると助かります。 よろしくお願いいたします。 以下が実行したプログラムになっております。 #include <stdio.h> #include <stdlib.h> #include <string.h> #define QUEUE_SIZE 100 /*キューの大きさ*/ /*配列でキューを表現する*/ int front, rear; char queue[3][50] = {"0b", "Ab", "Bb"}; char dequeue();/*キューからデータを取り出す*/ int next(int val);/*キューを配列で表現するとき、現在の次の配列のindexを返す*/ struct node{ char sentence[50];//値 struct node *left; //次のセルへのポインタ(左の子) struct node *right; //次のセルへのポインタ(右の子) }; int Gcount=0; void error(char *s);/*エラーを出力する*/ struct node* make_node();/*nodeをつくって返す*/ //void set_value_of_node(struct node* node,int a);/*nodeに値をセットする*/ struct node* growTree(int i, int k);/*深さiまで木を成長させ、そのルートを返す*/ void displayTree(struct node *node);/*node以下の部分木を表示する*/ int main(void){ struct node *root; int total=2 ; front = 0; rear = front + total + 1; root=growTree(total, 0); printf("\n\n\n前 順 表 示\n"); displayTree(root); return 0; } struct node* make_node(){/*nodeをつくって返す*/ struct node *p; if((p=(struct node*)malloc(sizeof(struct node ))) == NULL) error("メモリが足りません\n"); p->left =NULL; p->right =NULL; return(p); } //id set_value_of_node(struct node* node, int a)/*nodeに値をセットする*/ // //f(node == NULL)error("nodeが空です\n"); //ode->value=a; //rintf("%d ", node->value); // // void error(char *s){/*エラーを出力する*/ fprintf(stderr, s); exit(1); } /*キューからデータを取り出す*/ char dequeue(){ char *x; if(front == rear){ error("\nqueue is empty!!\n"); } x = queue[front]; front = next(front); return x; } /*キューを配列で表現するとき、現在の次の配列のindexを返す*/ int next(int val){ int next; next=(val+1)%QUEUE_SIZE; return(next); } struct node* growTree(int i, int k){/*深さiまで木を成長させ、そのルートを返す*/ /*課題1はここを書く*/ if(i == k) return NULL; k++; struct node *x; x = make_node(); x->sentence = dequeue(); x->left = growTree(i, k); x->right = growTree(i, k); return x; } void displayTree(struct node *node){/*node以下の部分木を表示する*/ /*課題2はここを書く*/ if(node == NULL) return; printf("%s\n", node->sentence); displayTree(node->left); displayTree(node->right); }
- 締切済み
- 情報工学
- 二分木のなぞり
ノードにデータが与えられているものとして帰りがけで二分木をなぞり、ノードに立ち寄った順にデータを書き出すときにそのデータが大きい順に並んでいるか判定するプログラムを作りたいです。 typedef struct node Node; struct node{ int data; Node* left; Node* right; }; int flag; void postorder(Node * p) { int kakunou; if( p == NULL ){ return 0 ; } postorder( p->left ); postorder( p->right ); kakunou=p->data; if(kakunou<p->data){ flag=1; } printf( "%2d ", p->data ); } そこで上のようにkakunouにひとつ前に出力したp->dataを格納し、kakunouとp->dataを比べた時にkakunouの方が小さければflag（グローバル変数）を1にしmain関数でflagが1なら、"大きい順ではない"と出力しようと思うのですが、kakunouとp->dataの値が同じになってしまいます。 どのタイミングでkakunou=p->data;を入れればよいのか、また根本的に考え方がおかしいなら方針を教えていただきたいです。よろしくお願いします。
- ベストアンサー
- C・C++・C#
- 二分探索木のheight(高さ?)を見つけるアルゴリズム
Binary Search Tree(=二分探索木)のheight(高さ?)を見つけるメソッドを作りたいのですが、 そのアルゴリズムが頭にうまく浮かびません。 まず思いついたのは一つ一つのNode(=ノード)をそれぞれのLeaf(=リーフ、葉?)まで辿っていって それらのheightを全部記憶させておいて後で比較するという…最も原始的な方法です。 しかし、Treeの大きさも未知なので用意する変数の数も未知になって どう考えても不適当でしょう(当たり前か(^^ゞ)。 Recursion(=再帰)を使えばいいのでしょうか? そうだとしてもどうすればいいのか…。 アルゴリズムがパッと浮かぶ方、どうか教えて下さい。
- ベストアンサー
- Java
- pascal二分木の課題
レポート課題で、pascalの二分木についての問題が出たのですが、うまくソースコードを作ることができません！ 誰かお手伝いよろしくお願いします！ 課題：progに木をバランスよく組みなおす関数repackを追加せよ program prog(input,output); const maxRange = 100; type dataType = integer; tree = ^treeCall; treeCall = record data:dataType; left,right:tree end; var root:tree; command:char; value:dataType; function search(d:dataType; t:tree):tree; begin if t=nil then search:=nil(*ブレーク*) else if t^.data=d then search:=t(*見つけた*) else if t^.data>d then search:=search(d,t^.left)(*左を検索*) else search:=search(d,t^.right)(*右を検索*) end; procedure insert(d:dataType; var t:tree); begin (**) if t=nil then begin new(t); t^.data:=d; t^.left:=nil; t^.right:=nil end else if t^.data=d then (*すでに登録されているので何もしない*) else if t^.data>d then insert(d,t^.left) else insert(d,t^.right); end; procedure delete(d:dataType; var t:tree); var temp:tree; procedure deleteMin(var r:tree); var temp:tree; begin temp:=r; while temp^.left<>nil do temp:=temp^.left; t^.data:=temp^.data; delete(temp^.data,r) end; begin if t=nil then writeln('Not Exist.') else if t^.data=d then if (t^.left<>nil) and (t^.right<>nil) then deleteMin(t^.right) else begin temp:=t; if t^.left<>nil then t:=t^.left else t:=t^.right; dispose(temp); end else if t^.data>d then delete(d,t^.left) else delete(d,t^.right) end; procedure writeSet(t:tree); begin if t=nil then (*何もしない*) else begin writeSet(t^.left);(*左へ左へ・・・*) write(t^.data:1,' '); writeSet(t^.right)(*右へ・・・*) end end; (****** Body ******) begin root:=nil; repeat write('> '); read(command); if command in ['i','d','s','w'] then begin (*もしもコマンドがw以外なら値を読み込む*) if command='w' then readln else readln(value); case command of (*数値をバイナリーツリーに挿入 ここでソーティングしたい*) 'i': insert(value,root); 'd': delete(value,root);
- 締切済み
- その他（プログラミング・開発）
- 多分探索木の高さを測定する関数について
今、多分探索木の高さを測定する関数を作成していますが、行き詰ってしまいました。 二分探索木の深さを求める関数を改良すればよろしいと思ったんですが。 どうもうまくいきません。助言お願いします。 以下、二分探索木の高さを求める関数を貼っときます。 int compute_height(NODE *root){ int lh=0, rh=0, Max; if(root==NULL){ return 0; } lh=compute_height(root->left)+1; rh=compute_height(root->right)+1; if(lh > rh){ return Max=lh; }else{ return Max=rh; } } 多分木探索の構造体定義は以下のようです typedef struct node{ int key[16]; //キー配列 int nkeys ; // キーの個数(実際の) struct node *refs[17] ; // 子への参照欄 } NODE
- 締切済み
- C・C++・C#
- 二分探索木のプログラム
２分探索木のプログラムを作っているのですが、実行するとセグメテーション違反がでます。何が間違っているんでしょうか？ #include<stdlib.h> struct node{ struct node *left,*right; int datum; }; struct bintree{ struct node *root; }; /*空木を作成*/ void InitTree(struct bintree *p) { p->root=NULL; } /*木全体を削除*/ void ClearTree(struct bintree *p) { struct bintree *q,*r; if(p->root!=NULL){ q->root=p->root->left; ClearTree(q); r->root=p->root->right; ClearTree(r); free(p->root); } } /*第二引数で指定された値が木の節点のラベルに存在すれば、その節点へのポインタを返す。なければ、NULLを返す。*/ struct node * SearchNode(struct bintree *p,int x) { struct bintree *q,*r; struct node *a=p->root; int cond=x-(a->datum); if(a==NULL) return NULL; else if(cond==0) return a; else if(cond<0){ q->root=p->root->left; SearchNode(q,x); } else{ r->root=p->root->right; SearchNode(r,x); } } /*第二引数で指定された値が木の節点のラベルに存在すれば、NULLを返す。なければ、追加して、新たに作成された節点へのポインタを返す。*/ struct node * InsertNode(struct bintree *p,int x) { struct bintree *q,*r; struct node *a=p->root; int cond=x-(a->datum); if(a==NULL){ a=(struct node *)malloc(sizeof(struct node)); a->datum=x; a->left=a->right=NULL; return a; } else if(cond==0) return NULL; else if(cond<0){ q->root=p->root->left; a->left=InsertNode(q,x); } else{ r->root=p->root->right; a->right=InsertNode(r,x); } } int main() { struct bintree *p; struct node *a; InitTree(p); a=InsertNode(p,5); InsertNode(p,3); InsertNode(p,0); InsertNode(p,10); SearchNode(p,5); ClearTree(p); return 0; }
- 締切済み
- C・C++・C#
- ２分探索木、挿入
行き詰まりました。 ２分探索木の要素挿入です。 何がいけないのでしょうか？？ 思うように動作しません。 ルートはどうやら設定されるようですが、 その他のデータがうまく挿入されません。 たぶんポインタの使い方がなってないようなのですが、 どこをどうしていいか分からないのでどなたか教えてください。 (インデントくずれました・・・見にくくてすみません) データ構造は以下の通りです。 node{ key //item template ですがint とみなしてください。 node *left //左の子へのポインタ node *right //右の子へのポインタ } root{ node *root //ルートへのポインタ } //ここからソース（多少省略してます。） insert(const K & newKey) { node<K> *temp; if(empty()){//ルートの設定。 temp = new node<K>(newKey, NULL,NULL); root = temp; }else{//木が既存する場合 insertItem(root, newKey); } } insertItem(node<K> *fact, const K & newKey) { node<K> *temp,test; if(fact == NULL){//要素挿入 temp = new node<K>(newKey,NULL,NULL); fact = temp; test = *fact; }else{//挿入場所探索 test=*fact; if(test.key == newKey){ cout<<"same key"; }else if(test.key > newKey){ insertItem(test.left, newKey); }else{ insertItem(test.right, newKey); } } }
- ベストアンサー
- C・C++・C#
- ２分木を中順でなぞりたいのですが（pascal)
課題で「２分探索木にデータを挿入する手続きを定義し、作った木を中順になぞって出力せよ」というのが出されました。 6 / \ 4 7 / \ 2 9 \ / \ 3 8 10 \ 11 \ 12 このような木を考えプログラムを組み実行できたのですが、結果が「2,3,4,6,7,8,9,10,11,12」となってしまいます。中順だと「3,2,4,6,8,9,12,11,10,7」のはずなので合いません。 どこがおかしいのかご指摘お願いします。 ソースは以下の通りです。 program tree_search (input,output); type elementtype = integer; pointertype = ^celltype; celltype = record element : elementtype; leftson : pointertype; rightson: pointertype end; var root : pointertype; procedure inorder( node:pointertype); begin if (node <> nil) then begin inorder( node^.leftson); write( node^.element); inorder( node^.rightson) end end; ｛中順になぞる｝ procedure insert( x:integer; var p:pointertype); begin if ( p = nil) then begin new( p ); p^.element := x; p^.leftson := nil; p^.rightson := nil end else if ( x < p^.element ) then insert( x,p^.leftson) else if ( x > p^.element ) then insert( x,p^.rightson) end; ｛木に挿入する｝ procedure create( var p:pointertype ); begin p:= nil end; ｛空の木を作る｝ begin create(root); insert( 6,root ); insert( 4,root ); insert( 2,root ); insert( 3,root ); insert( 7,root ); insert( 9,root ); insert( 8,root ); insert( 10,root ); insert( 11,root ); insert( 12,root ); inorder( root ) end.
- ベストアンサー
- その他（プログラミング・開発）
お礼
いろいろと教えて頂きありがとうございました。 本当に助かりました。
補足
度々ありがとうございます。教えて頂いた文章を読みながらプログラムを作ってみました。 - fun reflect(Empty)=Empty = | reflect(Node(root,left,right))= = Node(root,reflect(right),reflect(left)); 上記のプログラムでコンパイルおよび実行できましたが、正しく動作するものになっているでしょうか？教えてください。よろしくお願いします。