Text_Indexing/BinarySearchTree.h at master · YosefYudborovsky/Text_Indexing · 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
99
100
101
102
103
104
105
106
107
108
109
110
 //  Created by Frank M. Carrano and Tim Henry.
//  Copyright (c) 2013 __Pearson Education__. All rights reserved.

// Listing 16-4.
// Modified by Ioannis Stamos


/** Link-based implementation of the ADT binary search tree.
 @file BinarySearchTree.h */

#ifndef TEACH_CSCI235_BST_BINARY_SEARCH_TREE_H
#define TEACH_CSCI235_BST_BINARY_SEARCH_TREE_H

#include "BinaryTreeInterface.h"
#include "NotFoundException.h"
#include "BinaryNode.h"

template<class ItemType, class OtherType>
  class BinarySearchTree : public BinaryTreeInterface<ItemType, OtherType>
{
 public:
 BinarySearchTree(): root_(NULL) { };


  BinarySearchTree(const BinarySearchTree<ItemType, OtherType>& tree);
  BinarySearchTree& operator=(const BinarySearchTree<ItemType, OtherType>& right_hand_side);
  virtual ~BinarySearchTree();


  bool IsEmpty() const;
  int GetHeight() const;
  int GetNumberOfNodes() const;
  bool Add(const ItemType& item, int other); // const OtherType&
  bool Remove(const ItemType& data); // Removes a node
  void Clear();

  OtherType GetOther(const ItemType& an_item) const throw(NotFoundException);
  OtherType &GetOtherReference(const ItemType& an_item) throw(NotFoundException);
  bool Contains(const ItemType& an_entry) const;
    OtherType lineNumbersForList(const ItemType& an_entry);


  //------------------------------------------------------------
  // Public Traversals Section.
  //------------------------------------------------------------
    void PreorderTraverse(void visit(ItemType&)) const;
    void InorderTraverse(void visit(ItemType&)) const;
    void InorderTraverseForPrint(void visit(ItemType&)) const;
    void InorderTraverseForSearch(void visit(ItemType&)) const;

    void PostorderTraverse(void visit(ItemType&)) const;
    void maxSizeList() const;

//------------------------------------------------------------

 private:
    BinaryNode<ItemType, OtherType>* root_;
    BinaryNode<ItemType, OtherType>* maxSize = new BinaryNode<ItemType, OtherType>; // a pinter node to point to the node with the highest word count
    //maxSize->SetOther(0);

  int GetHeightHelper(BinaryNode<ItemType, OtherType>* node_ptr) const;
  int GetNumberOfNodesHelper(BinaryNode<ItemType, OtherType>* node_ptr) const;

  // Recursively deletes all nodes from the tree.
  void DestroyTree(BinaryNode<ItemType, OtherType>* node_ptr);

  // Recursively finds where the given node should be placed and
  // inserts it in a leaf at that point.
    BinaryNode<ItemType, OtherType>* InsertInorder(BinaryNode<ItemType, OtherType>* subTreePtr, BinaryNode<ItemType, OtherType>* newNode); // int new_other);
    BinaryNode<ItemType, OtherType>* binarySearchForWord(ItemType an_entry, BinaryNode<ItemType, OtherType>* subTreePtr);


  // Removes the given target value from the tree while maintaining a
  // binary search tree.
  BinaryNode<ItemType, OtherType>* RemoveValue(BinaryNode<ItemType, OtherType>* subTreePtr,
					       const ItemType target,
					       bool& success);

  // Removes a given node from a tree while maintaining a
  // binary search tree.
  BinaryNode<ItemType, OtherType>* RemoveNode(BinaryNode<ItemType, OtherType>* nodePtr);

  // Removes the leftmost node in the left subtree of the node
  // pointed to by nodePtr.
  // Sets inorderSuccessor to the value in this node.
  // Returns a pointer to the revised subtree.
  BinaryNode<ItemType, OtherType>* RemoveLeftmostNode(BinaryNode<ItemType, OtherType>* subTreePtr,
						      ItemType& inorderSuccessor);

  // Returns a pointer to the node containing the given value,
  // or NULL if not found.
  BinaryNode<ItemType, OtherType>* FindNode(BinaryNode<ItemType, OtherType>* treePtr,
					    const ItemType& target) const;

  // Copies the tree rooted at treePtr and returns a pointer to
  // the copy.
  BinaryNode<ItemType, OtherType>* CopyTree(const BinaryNode<ItemType, OtherType>* node_ptr) const;

  // Recursive traversal helper methods:
    void Preorder(void visit(ItemType&), BinaryNode<ItemType, OtherType>* node_ptr) const;
    void Inorder(void visit(ItemType&), BinaryNode<ItemType, OtherType>* node_ptr) const;
    void Postorder(void visit(ItemType&), BinaryNode<ItemType, OtherType>* node_ptr) const;
    void InorderPrint(void visit(ItemType&), BinaryNode<ItemType, OtherType>* node_ptr) const;
    ItemType InorderSearch(void visit(ItemType&), BinaryNode<ItemType, OtherType>* node_ptr) const;

}; // end BinarySearchTree

#include "BinarySearchTree.cpp"

#endif  // TEACH_CSCI235_BST_BINARY_SEARCH_TREE_H