6. 트리 (Tree)

링크 표현의 class 선언

class Tree;		// 전방 선언

class TreeNode{
friend class Tree;
private:
   TreeNode *LeftChild;
   char data;
   TreeNode *RightChild;
};

class Tree {
public:
   // tree 연산
private:
   TreeNode *root;
};

 

 

 

중위순회

void Tree::inorder(){
// Driver
// tree class의 공용 멤버 함수
   inorder(root);
}

void Tree::inorder(TreeNode *CurrentNode){
// Workhorse
// tree class의 전용 멤버 함수
   if (CurrentNode) {
      inorder(CurrentNode->LeftChild);
      cout << CurrentNode->data;
      inorder(CurrentNode->RightChild);
   }
}

 

전위순회

void Tree::preorder(){
// Driver
// tree class의 공용 멤버 함수
   preorder(root);
}

void Tree::preorder(TreeNode *CurrentNode){
// Workhorse
// tree class의 전용 멤버 함수
   if (CurrentNode) {
      cout << CurrentNode->data;
      preorder(CurrentNode->LeftChild);
      preorder(CurrentNode->RightChild);
   }
}

 

후위순회

void Tree::postorder(){
// Driver
// tree class의 공용 멤버 함수
   postorder(root);
}

void Tree::postorder(TreeNode *CurrentNode){
// Workhorse
// tree class의 전용 멤버 함수
   if (CurrentNode) {
      postorder(CurrentNode->LeftChild);
      postorder(CurrentNode->RightChild);
      cout << CurrentNode->data;
   }
}

 

 

반복적 중위 순회 함수

void Tree::NonrecInorder(){
// stack 이용한 비순환적 tree 순회
   Stack<TreeNode *> s;		// stack 선언, 초기화
   TreeNode *CurrentNode = root;
   
   while(1) {
      while(CurrentNode) {		// left child로 이동
         s.Push(CurrentNode);	// stack에 삽입
         CurrentNode = CurrentNode->LeftChild;
      }
      
      if (! s.IsEmpty() ) {		// not empty stack
         CurrentNode = *s.Pop(CurrentNode);		// stack에서 삭제
         cout << CurrentNode->data << endl;
         CurrentNode = CurrentNode->RightChild;
      }
      else
         break;
   }
}

 

 

레벨 순서 순회

root부터 level 단위로 node 방문. 같은 level에서는 left->right로 방문

void Tree::LevelOrder(){
// queue를 이용한 level 순서 순회
   Queue<TreeNode*> q;
   
   while(CurrentNode) {
      cout << CurrentNode->data << endl;
      if (CurrentNode->LeftChild)
         q.Push(CurrentNode->LeftChild);
      if (CurrentNode->RightChild)
         q.Push(CurrentNode->RightChild);
      CurrentNode = *q.Pop(CurrentNode);
   }
}