[DS] Binary tree Traversal

DFS

LVR : inorder

void inorder(tree root)
{
	if(root == nullptr) return;
    
    inorder(root->left);
    cout << root->key;
    inorder(root->right);
    
}

LRV : postorder

VLR : preorder

BFS

Level order

상위 Level부터 하위 Level로 모든 node를 탐색

void levelorder(tree root, vector<int>& vec) {
	DPRINT(cout << ">levelorder";);
	
	if (empty(root)) return;

	tree curr = root;	
	queue<tree> q;
	q.push(curr);

	while(!q.empty())
	{
		vec.push_back(q.front()->key);
		curr = q.front();

		if(curr->left != nullptr) q.push(curr->left);
		if(curr->right != nullptr) q.push(curr->right);

		q.pop();
	}

	DPRINT(cout << "<levelorder size=" << vec.size() << endl;);
}

ORDER TEST

Methods

Size

int size(tree node) 
{
  if (empty(node)) return 0;
  return size(node->left) + size(node->right) + 1;
}

Height

int height(tree node) 
{
  if (empty(node)) return -1;
  int left = height(node->left);
  int right = height(node->right);
  return max(left, right) + 1;
}

FindBT( )

bool containsBT(tree root, int key) 
{
  if (empty(root)) return false;
  if (key == root->key) return true;
  return containsBT(root->left, key) || containsBT(root->right, key);
}

maximumBT( )

max 값을 판단할 때 반드시 nullptr이 아님을 확인해야 한다.

tree maximumBT(tree node) 
{
  if (node == nullptr) return node;
  tree max = node;
  tree x = maximumBT(node->left);
  tree y = maximumBT(node->right);
  
  if(x !=nullptr && x->key > max->key) max = x;
  if(y !=nullptr && y->key > max->key) max = y;
  
  return max;
}

growBT( )

Completry binary tree 형식이 되도록, level order 순으로 node를 추가한다.

tree growBT(tree root, int key) {

	if(root == nullptr) return new TreeNode(key);
	queue<tree> q;
	tree curr = root; 
	q.push(curr);
	while(!q.empty())
	{
		curr = q.front();

		if(curr->left != nullptr) q.push(curr->left);
		else
		{
			curr->left = new TreeNode(key);
			break;
		}
		
		if(curr->right != nullptr) q.push(curr->right);
		else
		{
			curr->right = new TreeNode(key);
			break;
		}

		q.pop();
	}


	return root;    // eventually returns the original root node
}