Tree/tree.cpp at master · chelseah/Tree · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include "tree.h"
Tree::Tree(){
  item_ = new Item();
  root = 0;
  left = NULL;
  right = NULL;
}

Tree::Tree(Item *item)
: item_(item){
  root = 1;
  left = new Tree();
  right = new Tree();
}

Tree::~Tree(){
  delete item_;
  delete left;
  delete right;
}

int Tree::CountNodes(){
  int count;
  if(root==0){
    count=0;
  }
  else{
    count=1;
    count+=left->CountNodes();
    count+=right->CountNodes();
  }
  return count;
}

void Tree::PreorderPrint(vector <string> &outstr){
  if(root!=0){
      item_->PrintState(outstr);
      left->PreorderPrint(outstr);
      right->PreorderPrint(outstr);
  }
}
void Tree::PostorderPrint(vector <string> &outstr){
  if(root!=0){
      left->PostorderPrint(outstr);
      right->PostorderPrint(outstr);
      item_->PrintState(outstr);
  }
}

void Tree::InorderPrint(vector <string> &outstr){
  if(root!=0){
      //cout << outstr.size() << endl;
      left->InorderPrint(outstr);
      item_->PrintState(outstr);
//      cout << outstr.size()<< "in tree" << endl;
      right->InorderPrint(outstr);
  }
}
bool Tree::Intree(Tree &node){
  int cmp;
  if(root==0){
    return false;
  } else {
    cmp = item_->Ge(node.item_);
    if (cmp==0){
    return true;
    } else {
      if (cmp<0){
        return left->Intree(node);
      }
      else{
        return right->Intree(node);
      }
    }
  }
}
void Tree::Insert(Tree &node){
  int cmp;
  if(root==0){
    item_ ->copy(node.item_);
    root = 1;
    left = new Tree();
    right = new Tree();
  } else {
    cmp  = item_->Ge(node.item_);
    if(cmp<0){
      left->Insert(node);
    } else{
        if(cmp==0){
          if(item_->Better(node.item_)>0){
            item_ ->copy(node.item_);
          }
        } else{
          right->Insert(node);
        }
      }
  }
}