2016-06-17 33 views
0

私はバイナリ検索ツリーを持っており、その要素の後継を取得したいと思います。私のコードは問題ないとわかりますが、何が間違っているのかわかりません115は実行時エラーです。 6get succesorバイナリ検索ツリーC++データ構造

#include<bits/stdc++.h> 
    using namespace std; 

    struct Node 
    { 
     int data; 
     Node *root; 
     Node *left; 
     Node *right; 

    }; 

    typedef Node *ptr; 

    ptr search(ptr tree,int key) 
    { 
     if(tree==NULL)return tree; 
     if(tree->data==key) 
      return tree; 
     else if(tree->data>key) 
      search(tree->right,key); 
     else search(tree->left,key); 
    } 

    ptr most_left(ptr tree) 
    { 
     ptr result=tree; 
     if(tree==NULL)return NULL; 
     while(result->left!=NULL) 
      result=result->left; 
     return result; 
    } 

    ptr most_right(ptr tree) 
    { 
     ptr result=tree; 
     if(tree==NULL)return NULL; 
     while(result->right!=NULL) 
      result=result->right; 
     return result; 
    } 

    ptr min_element(ptr tree) 
    { 
     ptr result=tree; 
     if(tree==NULL)return NULL; 
     while(result->left!=NULL) 
      result=result->left; 
     return result; 
    } 

    ptr max_element(ptr tree) 
    { 
     ptr result=tree; 
     if(tree==NULL)return NULL; 
     while(result->right!=NULL) 
      result=result->right; 
     return result; 
    } 
    ptr temp=NULL; 
    ptr insert_element(ptr &tree,int key) 
    { 

     if(tree==NULL) 
     { 
     tree=new Node(); 
     tree->data=key; 
     tree->root=temp; 
     return tree; 
     } 
     else if(tree->data>=key) 
     { 
     temp=tree; 
     insert_element(tree->left,key); 
     } 
     else 
     { 
      temp=tree; 
      insert_element(tree->right,key); 
     } 

    } 

    void in_order(ptr tree) 
    { 
     if(tree == NULL) return; 
     in_order(tree->left); 
     cout<<tree->data<<" "; 
     in_order(tree->right); 
    } 

    void pre_order(ptr tree) 
    { 
     if(tree == NULL) return; 

     cout<<tree->data<<" "; 
     pre_order(tree->left); 
     pre_order(tree->right); 
    } 

    void post_order(ptr tree) 
    { 
     if(tree == NULL) return; 
     post_order(tree->left); 
     post_order(tree->right); 
     cout<<tree->data<<" "; 
    } 

    ptr succesor(ptr node) 
    { 
     if(node->right != NULL) return min_element(node->right); 
     ptr y = node->root; 
     while(y != NULL && node == y->right) { 
      node = y; 
      y = y->root; 

     } 
     return y; 
    } 

    int main() 
    { 
     ptr tree = NULL; 
     insert_element(tree,7); 
     insert_element(tree,5); 
     insert_element(tree,55); 
     insert_element(tree,6); 
     insert_element(tree,15); 
     insert_element(tree,60); 
     insert_element(tree,10); 
     insert_element(tree,115); 
     ptr inserted = insert_element(tree,5); 
     insert_element(tree,6); 
     insert_element(tree,12); 
     cout<<"succesor "<<succesor(inserted)->data; 
     cout<<"\nData Inserted \n"<<"In order : "; 
     in_order(tree); 
     cout<<endl; 
     cout<<"Pre order : "; 
     pre_order(tree); 
     cout<<endl; 
     cout<<"Post order : "; 
     post_order(tree); 
     cout<<endl; 
     cout<<"Minimum : "<<min_element(tree)->data<<endl; 
     cout<<"Maximum : "<<max_element(tree)->data<<endl; 
     return 0; 
    } 
+0

あなたは出力から期待するものの多くを説明できますか?なぜ5が間違っているのですか(2つの5があるので、そのうちの1つの後継者は他の5になります)。 "115ランタイムエラー"とはどういう意味ですか? –

+0

5が6で、115の後継者を取得しようとするとランタイムエラー –

+0

新しいNode()の後にNode()構造体のすべてのポインタメンバーを初期化する(データがない場合はnullptrへ) – lorro

答えて

2
  1. でなければなりません
    いいえ、プログラムが絶対的に正しいです "5は6でなければなりません"。
    insert_element関数では、tree->data >= key> =になります)をチェックするので、挿入するキーと同じデータを持つ要素がすでに存在する場合、新しいキーが左のサブツリーに挿入されます。あなたは>>=を交換した場合、以前の挿入5.イスト最後に挿入された5の後継者は、第2の5の右部分木に挿入されますので、期待通りその後継者が6である理由はここにあります。

  2. ランタイムエラー115
    もちろん、これが最大値であるため115の後継者はありません。したがって、succesor関数は、逆参照されると未定義の動作につながるNULLポインタを返します。

ところで、プログラムには未定義の動作があります。関数searchinsert_elementは、値を返さずに関数の最後から流出することがあります。標準は次のように述べています:

値のないリターンに相当します。これは、値を返す関数では未定義の動作になります。 (6.6.3)

ほとんどの実装では、戻り値が格納されている場所は再帰呼び出しのreturn文からその値を保持するため、幸運です。もちろん、これは修正する必要があります。

+0

お願いします ? –