c - Cでの二分木挿入ソート

Question

時間計算量が問題となるC言語の挿入ソートを使用してバイナリツリーをソートする方法を誰でも説明できます。私はコーディングを学んでいます。君たちありがとう！

Answer 1

ここで使用する特定の用語があることに注意してください。二分木は、すべてのノードが最大 2 つの子を持つデータ構造です。バイナリ ツリーのノードの順序付けに関する規則はありません。

二分探索木は、与えられたノード N に対して、N の左側の部分木のすべてのノードが N よりも「小さい」と見なされ、N の右側の部分木のすべてのノードが N よりも「大きい」と見なされるような 2 分木です。ノードがツリー内の N と「等しい」と見なされるようにします。ただし、ノードを一貫して左サブツリーまたは右サブツリーに配置するように定義している場合に限ります。

他の人が示唆しているように、コードを修正して通常の二分木ではなく二分探索木を構築するか、二分木を線形データ構造に変換してソートするのが最善です。

Answer 2

従来の意味でバイナリ ツリーをコーディングした場合、ツリーに項目を追加すると、ソートされた順序が保持されます。ツリーをトラバースすることで、アイテムの完全なリストを順番に取得できます。読むことをお勧めします：

• http://en.wikipedia.org/wiki/Tree_traversal

• http://en.wikipedia.org/wiki/Binary_tree

こちらもご覧ください: http://nova.umuc.edu/~jarc/idsv/lesson1.html

Answer 3

#include <stdio.h>
#include <malloc.h>
#define FIN "algsort.in"
#define FOUT "algsort.out"

struct Node {
   int val;
   struct Node *left;
   struct Node *right;
};

typedef struct Node node;

void insert(node **bt, node *Node) {

if( !(*bt) ) {

     *bt = Node;

} else {

        if( Node->val < (*bt)->val )

            insert(&((*bt)->left), Node);

        else

            insert(&((*bt)->right), Node);
 }
 }

 void printout(struct Node *node) {

   if(node->left) printout(node->left); 

   printf("%d ", node->val);  

   if(node->right) printout(node->right);
 }

 void postorder(struct Node *node) {

      if(node->left) printout(node->left);   

      if(node->right) printout(node->right); 

      printf("%d ", node->val);  
 }

 int main () {

     int i, n, elem;    

     node *curr; 

     freopen(FIN, "r", stdin);

     freopen(FOUT, "w", stdout);

     node *bt = NULL;

     scanf("%d", &n);

     for(i = 0; i < n; ++i) {

        scanf("%d", &elem); 

        curr = malloc( sizeof(struct Node) );

        curr->val = elem;

        curr->left = NULL;

        curr->right = NULL;

        insert(&bt, curr );

     }

    printout( bt ); 

    return(0);
  }

algsort.in に次の整数の配列が含まれているとします。

algsort.int -> 9,8,7,6,5,4,3,2,0,1,-1;

algsort.out -> -1,0,1,2,3,4,5,6,7,8,9