c - 二分木;頻度の高い順に印刷します。 C言語

原文 c binary-tree

私は知っていることを使用することになっています、これはクラスの課題であり、私はK&R本の第7章までです

私がやろうとしているのは、既に作成されているバイナリツリー(辞書式順序で配置)をトラバースし、その頻度の昇順で構造を出力することです。ここに再帰的なツリープリントがあります。 treeprintを再帰的にトラバースするための私のアイデアは、pcountをtreenodeカウントと比較してチェックすることです。それらが同じである場合、ノードを印刷し、その数を-4に設定して、印刷されないようにします(numcountは現在使用されていません)。 nullポインターに到達するか、p-> countが-4に等しくなります。つまり、ツリーが完全にトラバースされたことを意味し、pcountを再度インクリメントしてその頻度を確認する必要があります。何かがおかしいのは分かりますが、わかりません。ゲティスバーグというテキストファイルを使用しています。テキストは最後にそのまま含めています。

 /* treeprint: in-order print of tree p */
  void treeprint(struct tnode *p)
  {

      if(p != NULL) {
          treeprint(p->left);
          if(p->count == -4 || p == NULL){
              pcount++;
              treeprint(pt);
          }
          if(pcount == p->count) {
          printf("%4d %s\n", p->count, p->word);
          p->count = -4;
          numcount++;
      //  treeprint(p->right);
          }
          treeprint(p->right);
      }
  }


ここに宣言と本体があります:

  #include <stdio.h>
  #include <ctype.h>
  #include <string.h>
  #include <stdlib.h>
  #include "getch.h"
  #define MAXWORD 100

  int numcount = 1;
  int pcount = 1;
  struct tnode * pt;

  typedef struct tnode{
      char *word;
      int count;
      struct tnode *left;
      struct tnode *right;
  }treenode;


  int getword(char *, int);
  struct tnode *addtree(struct tnode *, char *);
  void treeprint(struct tnode *);
  int getch(void);
  void ungetch(int);
  main()
  {
      struct tnode *root;
      struct tnode *sortedtree;
      char word[MAXWORD];

      root = NULL;
      while(getword(word, MAXWORD) != EOF)
          if(isalpha(word[0])){
              root = addtree(root, word);
              pt = root;
          }
  //  sortedtree = treesort(sortedtree, root);
      treeprint(root);
  //  printf("so far so good \n\n");
  //  treeprint(sortedtree);
      printf("numcount = %d\n", numcount);
      return 0;
  }


ツリーを構築する私のaddtree関数:

  /* addtree: add a node with w, at or below p*/
  struct tnode *addtree(struct tnode *p, char *w)
  {
      int cond;

      if(p == NULL) {
          p = (struct tnode *) malloc(sizeof(struct tnode));
          p->word = strdup(w);
          p->count = 1;
          p->left = p->right = NULL;
      } else if ((cond = strcmp(w, p->word)) == 0)
          p->count++;
      else if (p->count < 0)
          p->left = addtree(p->left, w);
      else
          p->right = addtree(p->right, w);
      return p;
  }


ゲティスバーグのテキスト:


4つのスコアと7年前に私たちの父親はこれについて
大陸は自由の国で構想され、
すべての人は平等に創造されるという命題。今、私たちは
偉大な内戦、その国か他の国かをテスト
考え出され、とても献身的で、長く耐えることができます。私たちは素晴らしいで会っています
その戦争の戦場。その一部を専用にするようになりました
ここで命を与えた人々の最後の休息場所として
その国が生きるかもしれません。それは完全に適切で適切です
これを行う必要があります。しかし、より広い意味では、私たちができることを捧げることはできません
奉献しないと、私たちはこの地を神聖にすることはできません。生きている勇者たち
ここで戦った死者は、貧しい人々よりはるかに上にそれを奉献しました
追加または低下させる力。世界はほとんど注意せず、長い間覚えていない
ここで私たちが言うことは、彼らがここでしたことを決して忘れることはできません。です
私たちにとって、生きているのではなく、ここで未完成の仕事に専念する
ここで戦った彼らはこれまで気高く崇高に進んできました。です
私たちはここで、以前に残った素晴らしい仕事に専念します
これらの名誉ある死者から、私たちはそれにもっと献身的に取り組むこと
彼らが私たちが
ここで、これらの死者が無駄に死んではならないことを非常に解決します
この国は、神の下で、新たな自由の誕生と
国民のために、国民によって、国民のために、
地球から滅びる。
答え
何が問題なのかというと、それらを周波数順に並べるアプローチについては触れていないということです。

ヒープ構造を記述し、単語ツリーを走査して各word:countをヒープに挿入し、ヒープから値を削除して出力する方がはるかに簡単です。

ヒープは、常にルートに最大値を持つ、部分的に順序付けられたツリーです。挿入および削除時に、ツリーはこのプロパティを維持するために再調整されます。ヒープを配列s.tにマップする非常に効率的な実装があります。ルートはオフセット1にあり、左の子はオフセット2 * rootにあり、右の子は2 * root + 1にあります。ヒープは、書くのが楽しい構造です。
関連記事

c - コピーを作成するのではなく、ポインタを使い始める前に、構造はどのくらいの大きさにすべきですか? [C] [終了]

c - Cの配列で2次元配列にインデックスを付ける方法のベクトル化

java - Android Gstreamer SDKでANativeWindow_lockがエラー-22を返す

c - 厳格なエイリアシングを破った結果を理解する

c - 複数の構造体を宣言し、それらをすでに割り当てられているメモリにオーバーレイする

c++ - ゼロパディング付きのインテルMKLを使用した3D FFT

python - プロセス間通信Python [重複]

c - C99で関数ポインターの構造がNULLかどうかを確認するクイックチェック

c - 構造体を関数に渡し、Cで変更する

c - EVP_PKEYを使用したOpenSSL RSA_size