第6章の演習

ソースのダウンロード

今後の演習では，ホームフォルダの下にmis2というフォルダを作って，そこで作業することを前提とする．作成していない時は，ターミナルから

mkdir ~/mis2

を実行する． http://opendatastructures.orgのc++ edition, c++ sources ( C++ sources(講義独自版) ) からダウンロードしたファイルをホームフォルダの下のmis2に置く．ods.cpp.tgzというファイルができた時は，

cd ~/mis2
tar zxvf ods-cpp.tgz

ods-cpp.tarというファイルができた時は，

cd ~/mis2
tar xvf ods-cpp.tar

を実行するとcppというフォルダができる．Finderからダブルクリックしてもアーカイブユーティリティが立ち上がり展開されるので，そちらでも良い．

演習(BinaryTree)

~/mis2/cpp 以下にbinaryTreeTest.cpp というファイルを作成する．

#include "BinaryTree.h"


class MyBinaryTree : public ods::BinaryTree<ods::BTNode1>{
  typedef ods::BTNode1 Node;
public:
  MyBinaryTree(ods::BTNode1* nil_, ods::BTNode1* r_) :ods::BinaryTree<ods::BTNode1>(nil_){
    r = r_;
  }
  void traverse(){
    traverse(r);
  }
  void traverse(Node* u){
    if (u == nil) return;
    std::cout << u << std::endl;
    traverse(u->left);
    traverse(u->right);
  }
  void traverse2() {
    Node *u = r, *prev = nil, *next;
    while (u != nil) {
      std::cout << u << std::endl;
      if (prev == u->parent) {
        if (u->left != nil) next = u->left;
        else if (u->right != nil) next = u->right;
        else next = u->parent;
      } else if (prev == u->left) {
        if (u->right != nil) next = u->right;
        else next = u->parent;
      } else {
        next = u->parent;
      }
      prev = u;
      u = next;
    }
  }
  void bfTraverse() {
    ods::ArrayDeque<Node*> q;
    if (r != nil) q.add(q.size(),r);
    while (q.size() > 0) {
      Node *u = q.remove(0);
      std::cout << u << std::endl;
      if (u->left != nil) q.add(q.size(),u->left);
      if (u->right != nil) q.add(q.size(),u->right);
    }
  }
};
int main(){
  ods::BTNode1 *r = new ods::BTNode1();
  ods::BTNode1 *n1 = new ods::BTNode1();
  ods::BTNode1 *n2 = new ods::BTNode1();
  ods::BTNode1 *n3 = new ods::BTNode1();
  std::cout << "r = " << r << ",n1=" << n1 << ",n2=" << n2 << ",n3=" << n3 << std::endl;
  r->left = n1; n1->parent = r;
  r->right = n2; n2->parent = r;
  n2->left = n3; n3->parent = n2;
  //              r
  //             / \
  //            n1  n2
  //               /
  //              n3
  MyBinaryTree t(0, r);
  std::cout << "t.size()=" << t.size() << std::endl;
  std::cout << "t.size2()=" << t.size2() << std::endl;
  std::cout << "t.height()=" << t.height() << std::endl;
  t.traverse();
  std::cout << "end of traverse()" << std::endl;
  t.traverse2();
  std::cout << "end of traverse2()" << std::endl;
  t.bfTraverse();
  std::cout << "end of bfTraverse()" << std::endl;
}

これを，

cd ~/mis2/cpp
g++ -Wall  -o binaryTreeTest binaryTreeTest.cpp

でコンパイルし，

./binaryTreeTest

で実行する．

演習(BinarySearchTree)

~/mis2/cpp 以下にbinarySearchTreeTest.cpp というファイルを作成する．

#include "BinarySearchTree.h"
#include <iostream>
#include <vector>
#include <algorithm>

int main(){
  int null = -1;
  ods::BinarySearchTree<ods::BSTNode1<int>,int> primes(null);
  std::vector<int> vs;
  for(int i = 2; i < 1000; i++){
    vs.push_back(i);
  }
  std::random_shuffle(vs.begin(),vs.end());
  for(size_t k = 0; k < vs.size(); k++) primes.add(vs[k]);
  std::cout << "Tree height=" << primes.height() << std::endl;
  for(int i = 2; i < 1000; i++){
    if(primes.find(i) == i){
      std::cout << i << std::endl;
      for(int j = i + i; j < 1000; j += i){
        primes.remove(j);
      }
    }
  }
  std::cout << "Tree height=" << primes.height() << std::endl;
  std::cout << "Tree size=" << primes.size() << std::endl;
}

これを，

cd ~/mis2/cpp
g++ -o binarySearchTreeTest binarySearchTreeTest.cpp

でコンパイルし，

./binarySearchTreeTest

で実行する．
(注) 最初に2から1000までの数字を入れる際に，順番に入れると偏った木ができるので，random_shuffleを実行してからランダムな順番に入れている．

BinarySearchTreeのfindは見つからない場合も直後の要素を返すので，要素が含まれているかどうかは，findの結果が探した要素と等しいかどうかで判定している．　

[投票]以下の問いに答えよ?

空のBinarySearchTreeから始めて，1-10をaddした時に一番高さが小さい木になるのはどの順番でaddした時?

1, 2, ..., 10
5,6,4,7,3,8,2,9,1,10
5,3,2,1,4,8,6,7,9,10
10,9,8,7,6,5,4,3,2,1
5,6,7,8,9,10,4,3,2,1