ch8_BST_CODE

• Binary Search Tree Specification

#include <fstream.h>
template<class ItemType>
struct TreeNode;

enum OrderType {PRE_ORDER, IN_ORDER, POST_ORDER};

template<class ItemType>
class TreeType {
public:
  TreeType(); //생성자
  ~TreeType();//소멸자
  TreeType(const TreeType<ItemType>&); //생성자2
  void operator=(const TreeType<ItemType>&);//연산자 오버로딩
  void MakeEmpty();//초기화
  bool IsEmpty() const;
  bool IsFull() const;
  int LengthIs() const;
  void RetrieveItem(ItemType&, bool& found);
  void InsertItem(ItemType);
  void DeleteItem(ItemType);
  void ResetTree(OrderType);
  void GetNextItem(ItemType&, OrderType, bool&);
  void PrintTree(ofstream&) const;
private:
  TreeNode<ItemType>* root; //root노드 가르키는 포인터
};

• Function CountNodes
  • 노드의 총 개수 = left subtree + right subtree + 1(자기 자신-루트)이다.
  • Base case : The tree is empty ->0 으로 리턴
  • General case : CountNodes(Left(tree)) + CountNodes(Right(tree)) +1

//제대로 구현하기
int CountNodes(TreeNode* tree);

int TreeType::LengthIs() const
{
  return CountNodes(root); //length는 곧 노드들의 총 개수
}

int CountNodes(TreeNode* tree)
// 즉 tree는 count를 시작할 시작 지점의 노드(를 가르키는 포인터인 것)
{
	if tree is NULL//base case1(tree가 가르키는 게 NULL이면)
	  return 0 
	else if (tree->left is NULL) AND (tree->right is NULL) //basecase2
	  return 1
	else if Left(tree) is NULL //한쪽만 NULL인 경우
	  return CountNodes(Right(tree)) + 1 //자기 것을 더하고 자식노드를 만들고 진행
	else if Right(tree) is NULL
	  return CountNodes(Left(tree)) + 1
	else 
	  return CountNodes(Left(tree)) + CountNodes(Right(tree)) + 1
}

//최종->CountNode를 최대한 간단히 나타내서 아래와 같이 나타낼 수 있다
int CountNodes(TreeNode* tree)
// Post: returns the number of nodes in the tree.
{
  if (tree == NULL)
    return 0;
  else 
    return CountNodes(tree->left) + CountNodes(tree->right) + 1;
		//NULL인 경우를 BASECASE로 처리하고 있으니 신경쓰지 않고 걍 자식 2개 무조건
		//만든다고 생각한 후 자기 자신을 더한다.
}

• Function RetrieveItem

  • base case :

    • 1) When the key is found
    • 2) The tree is empty(key was not found)

  • general case:
    - Search in the left of right subtrees

    void TreeType::RetrieveItem(ItemType& item, bool& found)
    // Calls recursive function Retrieve to search the tree for item.
    {
      Retrieve(root, item, found); //item과 found에 결과가 저장되어 있음
    }
    
    void Retrieve(TreeNode* tree, 
         ItemType& item, bool& found)
    // Recursively searches tree for item.
    {
      if (tree == NULL) //basecase: 더 찾을 트리가 없음
        found = false;                     
      else if (item < tree->info) //general case: leaf node(base case)까지 닫기 위해
    //자식 노드 만들고 진행(재귀 1번 == 자식 노드 만드는 것)  
        Retrieve(tree->left, item, found); 
      else if (item > tree->info)
        Retrieve(tree->right, item, found);
      else //basecase2: 찾고자 하는 아이템을 찾음
      {
        item = tree->info;                 
        found = true;
       }
    }

• Recursive InsertItem

void Insert(TreeNode*& tree, ItemType item)
{//tree는 포인터
  if (tree == NULL) //base case: null을 만나면 삽입할 장소 찾은 것
  {
    tree = new TreeNode; //연결
    tree->right = NULL;
    tree->left = NULL;
    tree->info = item;
  }
  else if (item < tree->info)
    Insert(tree->left, item);   // general case: 왼쪽 자식노드 만들고(재귀라는 의미) 진행
  else
    Insert(tree->right, item);  // general case: 오른쪽 자식노드 만들고(재귀로) 진행
}

• Recursive DeleteItem
  • 총 3가지 경우들을 고려해야 함
    • 자식이 없는 경우
    • 자식이 1개인 경우
    • 자식이 2개인 경우

void Delete(TreeNode*& tree, ItemType item)
// Deletes item from tree.
// Post:  item is not in tree.
{
  if (item < tree->info)  //general case: 삭제할 아이템 찾기
    Delete(tree->left, item);   
  else if (item > tree->info)
    Delete(tree->right, item);  
  else
    DeleteNode(tree);       //general case: 해당 포인터(tree)가 가리키는 아이템 삭제하기
}

void DeleteNode(TreeNode*& tree)
// Deletes the node pointed to by tree.
// Post: The user's data in the node pointed to by tree is no 
//       longer in the tree.  If tree is a leaf node or has only 
//       non-NULL child pointer the node pointed to by tree is 
//       deleted; otherwise, the user's data is replaced by its 
//       logical predecessor and the predecessor's node is deleted.
{
  ItemType data;
  TreeNode* tempPtr;

  tempPtr = tree; //tempPtr은 삭제될 노드를 가르킨다
  if (tree->left == NULL) //자식이 하나인 경우, 자식이 없는 경우도 여기서 커버 됨
  {
    tree = tree->right;
    delete tempPtr;
  }
  else if (tree->right == NULL) 
  {
    tree = tree->left;
    delete tempPtr;
  }
  else
  {
    GetPredecessor(tree->left, data);//해당 노드의 좌측 subtree 중 제일 우측의 leafnode를 찾아냄
    tree->info = data;
    Delete(tree->left, data);  // 기존의  좌측 subtree 중 제일 우측의 leafnode은 이제 삭제
  }
}

void GetPredecessor(TreeNode* tree, ItemType& data)
// Sets data to the info member of the right-most node in tree.
{
  while (tree->right != NULL)
    tree = tree->right;
  data = tree->info;
}

• 전체 코드

#include "TreeType.h"
struct TreeNode
{
  ItemType info;
  TreeNode* left;
  TreeNode* right;
};

bool TreeType::IsFull() const
// Returns true if there is no room for another item 
//  on the free store; false otherwise.
{
  TreeNode* location;
  try
  {
    location = new TreeNode;
    delete location;
    return false;
  }
  catch(std::bad_alloc exception)
  {
    return true;
  }
}

bool TreeType::IsEmpty() const
// Returns true if the tree is empty; false otherwise.
{
  return root == NULL;
}

int CountNodes(TreeNode* tree);

int TreeType::LengthIs() const
// Calls recursive function CountNodes to count the 
// nodes in the tree.
{
  return CountNodes(root);
}

int CountNodes(TreeNode* tree)
// Post: returns the number of nodes in the tree.
{
  if (tree == NULL)
    return 0;
  else 
    return CountNodes(tree->left) + CountNodes(tree->right) + 1;
}

void Retrieve(TreeNode* tree, 
     ItemType& item, bool& found);

void TreeType::RetrieveItem(ItemType& item, bool& found)
// Calls recursive function Retrieve to search the tree for item.
{
  Retrieve(root, item, found);
}

void Retrieve(TreeNode* tree, 
     ItemType& item, bool& found)
// Recursively searches tree for item.
// Post: If there is an element someItem whose key matches item's,
//       found is true and item is set to a copy of someItem; 
//       otherwise found is false and item is unchanged.
{
  if (tree == NULL)
    found = false;                     // item is not found.
  else if (item < tree->info)      
    Retrieve(tree->left, item, found); // Search left subtree.
  else if (item > tree->info)
    Retrieve(tree->right, item, found);// Search right subtree.
  else
  {
    item = tree->info;                 // item is found.
    found = true;
   }
} 

void Insert(TreeNode*& tree, ItemType item);

void TreeType::InsertItem(ItemType item)
// Calls recursive function Insert to insert item into tree.
{
  Insert(root, item);
}

void Insert(TreeNode*& tree, ItemType item)
// Inserts item into tree.
// Post:  item is in tree; search property is maintained.
{
  if (tree == NULL)
  {// Insertion place found.
    tree = new TreeNode;
    tree->right = NULL;
    tree->left = NULL;
    tree->info = item;
  }
  else if (item < tree->info)
    Insert(tree->left, item);    // Insert in left subtree.
  else
    Insert(tree->right, item);   // Insert in right subtree.
} 
void DeleteNode(TreeNode*& tree);

void Delete(TreeNode*& tree, ItemType item);

void TreeType::DeleteItem(ItemType item)
// Calls recursive function Delete to delete item from tree.
{
  Delete(root, item);
}

void Delete(TreeNode*& tree, ItemType item)
// Deletes item from tree.
// Post:  item is not in tree.
{
  if (item < tree->info)
    Delete(tree->left, item);   // Look in left subtree.
  else if (item > tree->info)
    Delete(tree->right, item);  // Look in right subtree.
  else
    DeleteNode(tree);           // Node found; call DeleteNode.
}   

void GetPredecessor(TreeNode* tree, ItemType& data);

void DeleteNode(TreeNode*& tree)
// Deletes the node pointed to by tree.
// Post: The user's data in the node pointed to by tree is no 
//       longer in the tree.  If tree is a leaf node or has only 
//       non-NULL child pointer the node pointed to by tree is 
//       deleted; otherwise, the user's data is replaced by its 
//       logical predecessor and the predecessor's node is deleted.
{
  ItemType data;
  TreeNode* tempPtr;

  tempPtr = tree;
  if (tree->left == NULL)
  {
    tree = tree->right;
    delete tempPtr;
  }
  else if (tree->right == NULL)
  {
    tree = tree->left;
    delete tempPtr;
  }
  else
  {
    GetPredecessor(tree->left, data);
    tree->info = data;
    Delete(tree->left, data);  // Delete predecessor node.
  }
}

void GetPredecessor(TreeNode* tree, ItemType& data)
// Sets data to the info member of the right-most node in tree.
{
  while (tree->right != NULL)
    tree = tree->right;
  data = tree->info;
}

void PrintTree(TreeNode* tree, std::ofstream& outFile) 
// Prints info member of items in tree in sorted order on outFile.
{
  if (tree != NULL)
  {
    PrintTree(tree->left, outFile);   // Print left subtree.
    outFile << tree->info;
    PrintTree(tree->right, outFile);  // Print right subtree.
  }
}

void TreeType::Print(std::ofstream& outFile) const
// Calls recursive function Print to print items in the tree.
{
  PrintTree(root, outFile);
}

TreeType::TreeType()
{
  root = NULL;
}

void Destroy(TreeNode*& tree);

TreeType::~TreeType()
// Calls recursive function Destroy to destroy the tree.
{
  Destroy(root);
}

void Destroy(TreeNode*& tree)
// Post: tree is empty; nodes have been deallocated.
{
  if (tree != NULL)
  {
    Destroy(tree->left);
    Destroy(tree->right);
    delete tree;
  }
}

void TreeType::MakeEmpty()
{
  Destroy(root);
  root = NULL;
}

void CopyTree(TreeNode*& copy, 
     const TreeNode* originalTree);

TreeType::TreeType(const TreeType& originalTree)
// Calls recursive function CopyTree to copy originalTree 
//  into root.
{
  CopyTree(root, originalTree.root);
}

void TreeType::operator= 
     (const TreeType& originalTree)
// Calls recursive function CopyTree to copy originalTree 
// into root.
{
  {
  if (&originalTree == this)
    return;             // Ignore assigning self to self
  Destroy(root);      // Deallocate existing tree nodes
  CopyTree(root, originalTree.root);
  }

}
void CopyTree(TreeNode*& copy, 
     const TreeNode* originalTree)
// Post: copy is the root of a tree that is a duplicate 
//       of originalTree.
{
  if (originalTree == NULL)
    copy = NULL;
  else
  {
    copy = new TreeNode;
    copy->info = originalTree->info;
    CopyTree(copy->left, originalTree->left);
    CopyTree(copy->right, originalTree->right);
  }
}
// Function prototypes for auxiliary functions.

void PreOrder(TreeNode*, QueType&);
// Enqueues tree items in preorder.

void InOrder(TreeNode*, QueType&);
// Enqueues tree items in inorder.

void PostOrder(TreeNode*, QueType&);
// Enqueues tree items in postorder.

void TreeType::ResetTree(OrderType order)
// Calls function to create a queue of the tree elements in 
// the desired order.
{
  switch (order)
  {
    case PRE_ORDER : PreOrder(root, preQue);
                     break;
    case IN_ORDER  : InOrder(root, inQue);
                     break;
    case POST_ORDER: PostOrder(root, postQue);
                     break;
  }
}

void PreOrder(TreeNode* tree, 
     QueType& preQue)
// Post: preQue contains the tree items in preorder.
{
  if (tree != NULL)
  {
    preQue.Enqueue(tree->info);
    PreOrder(tree->left, preQue);
    PreOrder(tree->right, preQue);
  }
}

void InOrder(TreeNode* tree, 
     QueType& inQue)
// Post: inQue contains the tree items in inorder.
{
  if (tree != NULL)
  {
    InOrder(tree->left, inQue);
    inQue.Enqueue(tree->info);
    InOrder(tree->right, inQue);
  }
}

void PostOrder(TreeNode* tree, 
     QueType& postQue)
// Post: postQue contains the tree items in postorder.
{
  if (tree != NULL)
  {
    PostOrder(tree->left, postQue);
    PostOrder(tree->right, postQue);
    postQue.Enqueue(tree->info);
  }
}

void TreeType::GetNextItem(ItemType& item, 
     OrderType order, bool& finished)
// Returns the next item in the desired order.
// Post: For the desired order, item is the next item in the queue.
//       If item is the last one in the queue, finished is true; 
//       otherwise finished is false.
{
  finished = false;
  switch (order)
  {
    case PRE_ORDER  : preQue.Dequeue(item);
                      if (preQue.IsEmpty())
                        finished = true;
                      break;
    case IN_ORDER   : inQue.Dequeue(item);
                      if (inQue.IsEmpty())
                        finished = true;
                      break;
    case  POST_ORDER: postQue.Dequeue(item);
                      if (postQue.IsEmpty())
                        finished = true;
                      break;
  }
}

• 수업자료 끝에 iterative version인 FindNode 함수와 그를 활용한 각종 메서드들이 나옴