[자료구조] Tree(트리) - 이진 트리의 연산

 

1. 노드의 개수 구하기

// recursive
int get_node_cnt(TreeNode* p) {
	int cnt = 0;
    	if (p != NULL) {
    		cnt = 1 + get_node_cnt(p->left) + get_node_cnt(p->right);
    	}
    	return cnt;
}

 

 

2. 리프 노드 개수 구하기

int get_leafnode_cnt(TreeNode* p) {
	int cnt = 0;
    if (p != NULL) {
    	if (p->right == NULL && p->left == NULL)
        	return 1;
        else 
        	cnt = get_leafnode_cnt(p->left) + get_leafnode_cnt(p->right);
    }
    return cnt;
}

 

 

3. 높이 구하기

int get_height(TreeNode* p) {
	int height = 0;
	if (p != NULL)
    		height = 1 + max(get_height(p->left), get_height(p->right));
    	return height;
}

 

 

4. 노드가 같은지 검사

int equal(TreeNode* t1, TreeNode* t2) {
	return (!t1 && !t2) || ((t1 && t2) && equal(t1->left, t2->left) && 
    			equal(t1->right,t2->right) && (t1->data == t2->data));
}

 

5. 균형 트리 검사

int get_height(TreeNode* p) {
	int height = 0;
    if (p != NULL) {
    	height = 1 + max(height(p->left), height(p->right));
    }
   	return height;
}


int isBalanced(TreeNode* p) {
	int balance = 0;
	if (p != NULL) {
    		balance = get_height(p->left) - get_height(p->right);
            	if (balance > 1 && balance < -1) return 0
    		else return (isBalanced(p->left) && isBalanced(p->right));
}

 

 

6. 트리의 합 구하기

int SumOfTree(TreeNode* p) {
	int sum = 0;
    	if (p != NULL) {
        	sum += p->data + SumOfTree(p->left) + SumOfTree(p->right);
        }
      	return sum;
}

 

 

7. 정해진 값보다 작으면 노드 값 출력하기

int lower_value(TreeNode* p, int value) {
	int v = 0;
	if (p != NULL) {
    	if (p->data < value) 
        	v = lower_value(p, p->data);
        else
            	return min(lower_value(p->left, value), lower_value(p->right, value));
    }
    return v;
}

 

 

8. 한쪽 노드만 있는 노드의 개수 출력하기

int get_OneChild_cnt(TreeNode* p) {
	if (p != NULL) {
    		if (p->left != NULL && p->right == NULL)
            		return 1 + get_OneChild_cnt(p->left);
              	else if (p->left == NULL && p->right != NULL)
			return 1 + get_OneChild_cnt(p->right);
            	else
            		return get_OneChild_cnt(p->left) + get_OneChild_cnt(p->right);
        }
        return 0;
}

 

 

 

9. 트리에 저장된 데이터 값을 모두 1씩 제거하기

void minus_one(TreeNode* p) {
	if (p != NULL) {
    		p->data -= 1;
        	minus_one(p->left);
        	minus_one(p->right);
    	}
}