[PHP] 이진트리 만들기

첫 글로 어떤 글을 올려볼까 하고 고민을 좀 했습니다. 

자료구조 중 스택 (LIFO) 를 올려볼까 큐(FIFO)를 올려볼까 아니면 데큐 를 올려볼까 하다가 오래전에 이진트리를 만들어 본 경험이 있습니다. 

해당 부분을 정리해서 올리면서 하단에 제가 구현한 소스도 올려보려고 합니다. 

자료구조를 배우거나 알고리즘을 배울 때는 보통 알려진 목차가 있어요. 

위에서 설명드린 것과 같이 자료구조들이 있어요. 그전에 빅O도 구하고요.

 

본 포스팅에서는 제목처럼 이진트리 구현한 내용을 적어보려고 합니다. 

 

제가 만든 소스에는 전위,중위,후위 순회가 가능하도록 구현되어있습니다. 

트리에 대한 기초내용은 타 블로거님들이 내용을 자세히 올려두셔서 제가 여기에서 반복하진 않겠습니다. 

개념은 동일하기에 여기에서는 제 구현 소스를 올려드리고, 해당 소스가 이 글을 보시는 분에게 작으나마 도움이 되셨으면 해서 올려드립니다. 

 

제 소스는 일단 위와 같이 노드 트리를 생성하고 각 노드들을 방문해보는 로직입니다. 

 

<?php
    $root = null;

    class Node
    {   
        public $left;
        public $right;     
        public $data;
        public function __construct($data)
        {            
            $this->right = '';
            $this->data = $data;
            $this->left = '';
        }
    }

    class binaryTree
    {
      public $answer;
      public $root;

        public function __construct($msg, $order)
        {
          $this->answer = [];          
          $tree = $this->insertLevelOrder($msg, null, 0);
          switch ($order)
          {
            case "mid" :            
              $this->inOrder($tree);
              break;
            case "pre" :
              $this->preOrder($tree);
              break;
            case "post" :
              $this->postOrder($tree);
              break;
          }
        }

        public function insertLevelOrder($arr, $root, $i)
        {
            if ($i < strlen($arr))
            {
                $root = new Node($arr[$i]);
                $root->left = $this->insertLevelOrder($arr, $root->left, $i*2+1);
                $root->right = $this->insertLevelOrder($arr, $root->right, $i*2+2);
            }
            return $root;
        }

        public function inOrder($root)
        {
            if (isset($root->data)) {
              $this->inOrder($root->left);
              array_push($this->answer, $root->data);
              $this->inOrder($root->right);
            }
        }

        public function preOrder($root)
        {
          if (isset($root->data)) {
            array_push($this->answer, $root->data);            
            $this->preOrder($root->left);
            $this->preOrder($root->right);
            
          }
        }

        public function postOrder($root)
        {
          if (isset($root->data)) {            
            $this->postOrder($root->left);
            $this->postOrder($root->right);            
            array_push($this->answer, $root->data);
          }
        }
    }

    $letters = "ABCDEFGH";
    print_r(str_split($letters));
    echo ("\n상단 배열을 이진트리로 만든 후, 재정렬");

    // 클래스 인스턴스 생성 후, 처리     
    echo "\n\n상단 배열을 중위순회로 정렬\n";
    $generateTree = new binaryTree($letters, "mid");
    print_r($generateTree->answer);        
    echo "\n\n최상단 배열을 전위순회로 정렬\n";    
    $generateTree_pre = new binaryTree($letters, "pre");
    print_r($generateTree_pre->answer);    
    echo "\n\n최상단 배열을 후위순회로 정렬\n";
    $generateTree_post = new binaryTree($letters, "post");
    print_r($generateTree_post->answer);

위와 같이 구현했습니다. 

실행결과는 다음과 같습니다.

위와 같이 방문하여 노드를 가져와 새로운 배열에 담고 그 배열을 출력한 모습입니다. 

공부하시는데에 도움이 되셨으면 합니다. 

그럼 오늘도 열공하세요.