9. 데이터 구조의 이 진 트 리
나무의 프로필
그 전에 우 리 는 1 차원 선형 데이터 구조의 2 단 링크, 동적 배열 과 그들의 변형 구조 스 택 과 대기 열, 그리고 그들의 조합 구조 hash 표를 접 하여 여러 가지 검색 과 저장 문 제 를 해결 했다. 그러나 선형 데이터 구 조 는 사용 에 있어 아직도 많은 문제점 이 존재 했다. 예 를 들 어 1 차원 선형 데이터 구조의 검색 효율 은 O (n) 의 시간 복잡 도 에 만 달 할 수 있다.그래서 상기 문 제 를 해결 하기 위해 우 리 는 1 차원 을 바탕 으로 확장, 도입 과 나무 구 조 를 실시 했다.
나무의 분류
트 리: n (n > = 1) 개의 유한 노드 로 차원 관 계 를 가 진 집합 입 니 다.우리 의 일상생활 에서 도 나무 구조의 모델 이 많다. 예 를 들 어 가정의 족 보 는 나무 모양 의 구조 이 고 회사 의 전체 직원 차원 도 나무 모양 의 구조 (서로 다른 부서, 조직) 이다.그것 의 저장 은 일정한 규칙 을 가지 고 있 기 때문에 (크기 순서에 따라, 모듈 에 따라) 여러 가지 트 리 구 조 를 설명 한다.
B 트 리 이 진 트 리 사전 트 리
……
이 진 트 리 의 구조
그 중에서 가장 흔히 볼 수 있 는 나무 구 조 는 바로 이 진 트 리 이다. 이 진 트 리 는 왼쪽 아이 와 오른쪽 아이 두 개의 후계 노드 가 있 는데 이것 은 우리 가 두 개의 이 진 트 리 노드 지침 을 사용 해 야 한다.이 진 트 리 를 구축 할 때 재 귀적 인 프로 그래 밍 사상 을 대량으로 사용 할 것 이다. 그 다음 에 우 리 는 이 진 트 리 의 생 성, 소각, 옮 겨 다 니 기, 그리고 각종 이 진 트 리 의 성질 에 착안 하여 (높이, 노드 개수, 균형 여부 등 특성) 이 진 트 리 의 일부 응용 을 소개 해 야 한다.
이 진 트 리 의 실현
이 진 트 리 의 생 성에 대해 우 리 는 먼저 이 진 트 리 의 노드 구 조 를 확인 해 야 한다. 데 이 터 를 저장 하 는 데이터 도 메 인 을 제외 하고 좌우 아 이 를 가리 키 는 지침 도 있어 야 한다.
//
typedef struct Tree_node Tree_node;
struct Tree_node{
char data; //
Tree_node *left_child;
Tree_node *right_child;
};
typedef Tree_node *Bin_tree; // 이 진 트 리 의 노드 를 설계 한 후에 우 리 는 이 진 트 리 의 인 터 페 이 스 를 열거 해 야 한다. 일부 인 터 페 이 스 는 필기시험 면접 의 중점 문제 이다.
//
//
Bin_tree create_tree(char **str); //
Bin_tree create_tree_by_pre_mid(char *pre_str, char *mid_str, int length); //
Bin_tree create_tree_by_mid_last(char *mid_str, char *last_str, int length); //
void destroy_tree(Bin_tree *root); //
void destroy_tree_nr(Bin_tree *root); //
void pre_order_print(Bin_tree root); //
void mid_order_print(Bin_tree root); //
void last_order_print(Bin_tree root); //
void pre_order_print_nr(Bin_tree root); //
void mid_order_print_nr(Bin_tree root); //
void last_order_print_nr(Bin_tree root); //
void level_order_print(Bin_tree root); //
Bin_tree copy_binary_tree(Bin_tree root); //
Boolean is_binarytree_equal(Bin_tree root1, Bin_tree root2); //
Boolean is_full_binary_tree(Bin_tree root); //
Boolean is_complete_binary_tree(Bin_tree root); //
Boolean is_balance_binary_tree(Bin_tree root); //
int get_binarytree_height(Bin_tree root); //
int get_binarytree_node_count(Bin_tree root); //
int get_binarytree_leaf_count(Bin_tree root); //
void swap_left_right(Bin_tree root); //
int get_binarytree_level_count(Bin_tree root, int level); //
Tree_node *find_value(Bin_tree root, char value); //
Tree_node *find_common_node(Tree_node *node1, Tree_node *node2 ); //
Tree_node *find_parent(Bin_tree root, Tree_node *node); //
Boolean is_include_tree(Bin_tree root1, Bin_tree root2); // 이 진 트 리 의 인 터 페 이 스 를 소개 한 후에 우 리 는 각 인터페이스의 실현 에 대해 상세 하 게 소개 해 야 한다.
1. 이 진 트 리 생 성
이 진 트 리 의 생 성 방식 은 매우 다양 합 니 다. 오늘 우 리 는 문자열 의 방식 으로 이 진 트 리 를 만 드 는 것 을 소개 합 니 다. 일반 문 자 를 만 났 을 때 우 리 는 이 진 트 리 노드 를 직접 만 듭 니 다. '\#' 문 자 를 만 났 을 때 우 리 는 이 진 트 리 노드 가 존재 하지 않 는 다 고 생각 합 니 다. 그리고 이 진 트 리 의 노드 가 존재 한 후에 일반 문 자 를 만 나 왼쪽 아이 라 고 생각 합 니 다.왼쪽 아이 가 존재 할 때 일반 문 자 를 만나면 우 리 는 오른쪽 아이 라 고 생각 합 니 다. 다음은 예 를 들 어 보 겠 습 니 다.
예 를 들 어 지정 한 문자열 은: ABC\#\# DE\#\# F\#\# GH\# I\#\# J\#\#
다음 그림 과 같이 대응 하 는 이 진 트 리 입 니 다.
이 진 트 리 그림
다음은 이 진 트 리 의 생 성 과정 을 소개 합 니 다. 코드 는 다음 과 같 습 니 다.
//
Bin_tree create_tree(char **str) //
{
Bin_tree root = NULL;
//ABC##DE##F##GH#I##J##
if(str != NULL && *str != NULL && **str != END){
// ，
root = create_node();
root->data = **str;
++*str; //
root->left_child = create_tree(str);
++*str;
root->right_child = create_tree(str);
}
return root;
}
결과 문자열 을 옮 겨 다 니 며 이 진 트 리 를 만 듭 니 다.
상기 생 성 방식 을 제외 하고 예전 의 학습 과정 에서 우 리 는 접촉 한 적 이 있다. 이 진 트 리 의 옮 겨 다 니 는 방식 은 먼저 뿌리 를 옮 겨 다 니 고 중 근 서 를 옮 겨 다 니 며 후 근 서 를 옮 겨 다 니 는 세 가지 방식 을 포함한다.
만약 에 선착순 과 중 서 를 옮 겨 다 니 는 결 과 를 알려 주 었 거나 후 서 를 옮 겨 다 니 며 중 서 를 옮 겨 다 니 는 결 과 를 알려 주 었 다 면 우 리 는 이 진 트 리 의 전체적인 결 과 를 추측 할 수 있다. 이런 결론 은 정확 하 다. 중 서 를 옮 겨 다 니 는 결 과 는 각 노드 가 아이들 노드 의 순 서 를 확정 할 수 있 고 선착순 과 후 서 를 가 진 결 과 는 뿌리 결점 의 위 치 를 설명 할 수 있 기 때문이다.
다음은 옮 겨 다 니 는 결 과 를 통 해 이 진 트 리 를 만 드 는 방법 을 알려 드 리 겠 습 니 다.
//
Bin_tree create_tree_by_pre_mid(char *pre_str,
char *mid_str, int length)
{
//A B C D E F G H I J pre
//C B E D F A H I G J mid
Bin_tree root = NULL;
char root_value = 0;
int index = -1;
//1. value，pre
if(pre_str == NULL || mid_str == NULL || length <= 0){
return root;
}
//2. value
root_value = pre_str[0];
root = create_node();
root->data = root_value;
//3. value ， ，
//
index = find_index(mid_str, root_value);
root->left_child = create_tree_by_pre_mid(pre_str + 1, mid_str, index);
root->right_child = create_tree_by_pre_mid(pre_str + index + 1,
mid_str + index + 1,
length - index - 1);
return root;
}중간 순서 와 뒷 순 서 를 통 해 이 진 트 리 생 성:
//
Bin_tree create_tree_by_ml(char *mstr, char *lstr, int length)
{
Bin_tree root = NULL;
int index = -1;
int root_value = 0;
if(mstr == NULL || lstr == NULL || length <= 0){
return root;
}
root_value = lstr[length - 1]; //
root = buy_node();
root->data = root_value;
index = find_char_index(mstr, root_value);
root->left_child = create_tree_by_ml(mstr, lstr, index);
root->right_child = create_tree_by_ml(mstr + index + 1,
lstr + index, length - index - 1);
return root;
}2. 이 진 트 리 소각
이 진 트 리 의 생 성 작업 을 완 성 했 습 니 다. 이 어 우 리 는 이 진 트 리 의 소각 을 소개 합 니 다. 많은 자료 에서 재 귀적 인 소각 방식 과 이 진 트 리 의 왼쪽 아 이 를 먼저 소각 한 다음 에 이 진 트 리 의 오른쪽 아 이 를 소각 하고 마지막 으로 현재 이 진 트 리 노드 를 소각 합 니 다.이런 방법 은 노드 주소 의 분실 을 방지 하기 위해 서 이다. 만약 에 현재 이 진 트 리 노드 를 먼저 없 애 면 아이의 주 소 를 좌우 로 잃 어 버 리 고 메모리 가 유출 되 기 때문에 재 귀 하 는 것 이 좋 은 해결 방안 이다.코드 예 시 는 다음 과 같다.
//
//
void destroy_tree(Bin_tree *root)
{
// ，
if(root == NULL || *root == NULL){
return ;
}
destroy(*root);
*root = NULL;
}
static void destroy(Bin_tree root)
{
if(root != NULL){
destroy(root->left_child); //
destroy(root->right_child); //
free(root);
}
}다시 한 번 문 제 를 생각 하 자 면 우리 가 재 귀적 인 방식 을 사용 하 는 것 은 이 진 트 리 좌우 아이의 주 소 를 기록 하기 위 한 것 일 뿐이다. 만약 에 대열 을 통 해 각 이 진 트 리 노드 의 좌우 아이의 주 소 를 기록 하면 교체 하 는 방식 으로 이 진 트 리 를 없 앨 수 있 기 때문에 층 차 를 옮 겨 다 니 는 사상 을 이용 하여 순환 작업 으로 이 진 트 리 를 없 앨 수 있다. 함수 의 재 귀적 호출 을 줄 이기 때문이다.그래서 효율 을 크게 높 일 수 있 습 니 다.
* 그 중에서 사 용 된 queue (대기 열) 데이터 구 조 는 이전의 선형 데이터 구조 에서 소개 되 었 다.
코드 예 시 는 다음 과 같다.
//
void destroy_tree_nr(Bin_tree *root) //
{
// ：
//
//
// A
// / \
// B C
//
// 1. n ， n + 1
//
Queue *queue = init_queue();
Tree_node *p_node = NULL;
if(root == NULL || *root == NULL){
return ;
}
p_node = *root;
*root = NULL;
in(queue, p_node);
while(!is_queue_empty(queue)){
get_queue_front(queue, (void **)&p_node);
out(queue);
// p_node ， p_node
if(p_node->left_child != NULL){
in(queue, p_node->left_child);
}
if(p_node->right_child != NULL){
in(queue, p_node->right_child);
}
free(p_node);
}
destroy_queue(&queue);
}3. 이 진 트 리 의 재 귀 방식 (재 귀)
이 진 트 리 의 재 귀 방식 은 매우 간단 합 니 다. 우 리 는 먼저 뿌리 순 서 를 예 로 들 면 이 진 트 리 의 데이터 내용 을 인쇄 한 다음 에 이 진 트 리 의 왼쪽 아이 부분 을 인쇄 한 다음 에 이 진 트 리 의 오른쪽 아이 부분 (모두 인쇄 함수 자 체 를 호출 하고 들 어 오 는 매개 변수 만 다 릅 니 다) 을 인쇄 합 니 다. 코드 예 는 다음 과 같 습 니 다.
void pre_order_print(Bin_tree root) //
{
if(root != NULL){
printf("%c ", root->data);
pre_order_print(root->left_child);
pre_order_print(root->right_child);
}
}
void mid_order_print(Bin_tree root) //
{
if(root != NULL){
mid_order_print(root->left_child);
printf("%c ", root->data);
mid_order_print(root->right_child);
}
}
void last_order_print(Bin_tree root) //
{
if(root != NULL){
last_order_print(root->left_child);
last_order_print(root->right_child);
printf("%c ", root->data);
}
}재 귀적 으로 옮 겨 다 니 는 방식 을 제외 하고 우 리 는 이 진 트 리 를 재 귀적 으로 옮 겨 다 닐 수 있다. 이것 은 스 택 을 통 해 옮 겨 다 니 는 노드 정 보 를 기록 하여 역 추적 효 과 를 얻 을 수 있다.코드 예 시 는 다음 과 같다.
//
void pre_order_print_nr(Bin_tree root) //
{
Stack *stack = init_stack(); //
Tree_node *p_node = NULL;
if(root == NULL){
return ;
}
p_node = root;
push(stack, p_node);
while(!is_stack_empty(stack)){
get_top(stack, (void **)&p_node);
printf("%c ", p_node->data);
pop(stack);
if(p_node->right_child != NULL){
push(stack, p_node->right_child);
}
if(p_node->left_child != NULL){
push(stack, p_node->left_child);
}
}
destroy_stack(&stack);
//
// A
// / \
// B G
// / \ / \
// C D H J
// / \ \
// E F I
//
// ：
//
// ， 、
//
//
//
//
// D
// G
//
//
// A B C
}
void mid_order_print_nr(Bin_tree root) //
{
Stack *stack = NULL;
Tree_node *p_node = NULL;
if(root == NULL){
return ;
}
stack = init_stack();
p_node = root;
while(!is_stack_empty(stack) || p_node != NULL){
while(p_node != NULL){ //
push(stack, p_node);
p_node = p_node->left_child;
}
get_top(stack, (void **)&p_node);
printf("%c ", p_node->data);
pop(stack);
p_node = p_node->right_child;
}
destroy_stack(&stack);
// A
// / \
// B G
// / \ / \
// C D H J
// / \ \
// E F I
//
// CBEDFAHIGJ
//
// ：
//
// 1.
// 2. ，
// 3.
}
void last_order_print_non(Bin_tree root) // （ ）
{
Tree_node *p_node = NULL;
Tree_node **temp = NULL;
Tree_node *prev = NULL;
Stack *stack = init_stack();
if(root == NULL){
return ;
}
p_node = root;
push(stack, p_node);
while(!is_stack_empty(stack)){
get_top(stack, (void **)&p_node);
if((p_node->left_child == NULL && p_node->right_child == NULL)
|| (prev != NULL && (p_node->left_child == prev || p_node->right_child == prev))){
// ，
// ， ，
printf("%c ", p_node->data);
pop(stack);
prev = p_node;
}else{ // ，
if(p_node->right_child != NULL){
push(stack, p_node->right_child);
}
if(p_node->left_child != NULL){
push(stack, p_node->left_child);
}
}
}
printf("
");
destroy_stack(&stack);
}
이 진 트 리 의 층 차 를 옮 겨 다 니 기: 이 진 트 리 의 한 층 노드 를 옮 겨 다 니 며 모든 높이 를 옮 겨 다 닐 때 까지.관건 은 현재 노드 를 옮 겨 다 닌 후 반드시 좌우 아 이 를 순서대로 옮 겨 다 니 는 대기 열 에 추가 하 는 것 이다.코드 예 시 는 다음 과 같다.
void level_print(Bin_tree root) //
{
Tree_node *p_node = NULL;
// A B G C D H E F
// 1. ， ，
// ， ，
if(root == NULL){
return ;
}
p_node = root;
Queue *queue = init_queue();
in(queue, p_node);
while(!is_queue_empty(queue)){
get_queue_front(queue, (void **)&p_node);
out(queue);
//sleep(1);
printf("%c ", p_node->data);
// p_node
if(p_node->left_child != NULL){
in(queue, p_node->left_child);
}
if(p_node->right_child != NULL){
in(queue, p_node->right_child);
}
}
destroy_queue(&queue);
}4. 이 진 트 리 의 관련 속성 (높이, 노드 개수, 잎 노드 트 리)
두 갈래 나무의 높이 얻 기:
int get_binarytree_height(Bin_tree root) //
{
//1. ：
//
// max( ， ) + 1；
if(root == NULL){
return 0;
}
return 1 + max(get_binarytree_height(root->left_child),
get_binarytree_height(root->right_child));
}이 진 트 리 의 노드 트 리 를 가 져 옵 니 다.
int get_binarytree_node_count(Bin_tree root) //
{
// = 1 + +
if(root == NULL){
return 0;
}
return 1 + get_binarytree_node_count(root->left_child)
+ get_binarytree_node_count(root->right_child);
}이 진 트 리 잎 사 귀 노드 개 나무 얻 기
int get_binarytree_leaf_count(Bin_tree root) //
{
//
if(root == NULL){
return 0;
}else if(root->left_child == NULL && root->right_child == NULL){
// ， 1
return 1;
}else{
//
return get_binarytree_leaf_count(root->left_child)
+ get_binarytree_leaf_count(root->right_child);
}
}5. 이 진 트 리 의 상태 판단 (동일 여부, 균형 여부, 완전, 만 이 진 트 리)
(1) 이 진 트 리 가 같은 지 판단
이 진 트 리 의 성질 에 따라 두 개의 이 진 트 리 가 같 으 면 현재 노드 데이터 내용 이 같 고 왼쪽 아이 와 오른쪽 아이의 데이터 내용 도 같 아야 하 며 이 진 트 리 의 구 조 는 같 아야 한다.코드 는 다음 과 같다.
Boolean is_binary_equal(Bin_tree root1, Bin_tree root2) //
{
// ：
//
//1. ，
//
//2.
// (1) ；
// (2) ；
// (3) ；
// (4) 。
if(root1 == NULL && root2 == NULL){
return TRUE;
}else if((root1 != NULL && root2 != NULL)
&& (root1->data == root2->data)
&& is_binary_equal(root1->left_child, root2->left_child)
&& is_binary_equal(root1->right_child, root2->right_child)){
return TRUE;
}else{
return FALSE;
}
}(2) 이 진 트 리 가 가득 찼 는 지 판단 하기
만 이 진 트 리 는 잎 노드 (좌우 아이 가 없 음) 를 제외 하고 다른 이 진 트 리 노드 는 반드시 좌우 아 이 를 동시에 가 져 야 한 다 는 것 을 의미한다.우 리 는 이 진 트 리 의 높이 h 와 이 진 트 리 의 노드 개 트 리 count 를 계산 할 수 있 습 니 다. 만약 에 이들 이 만족 하면 (2 ^ h - 1 = = count) 이 진 트 리 가 이 진 트 리 가 가득 하 다 는 것 을 설명 합 니 다.코드 예 시 는 다음 과 같다.
Boolean is_full_binary_tree(Bin_tree root) //
{
// height count
//
//
// 2^height - 1 == count
int height = 0;
int count = 0;
if(root == NULL){
return FALSE;
}
height = get_binarytree_height(root);
count = get_binarytree_node_count(root);
return (powl(2, height) - 1) == count;
}(3) 이 진 트 리 가 완전 이 진 트 리 인지 판단
완전 이 진 트 리 는 만 이 진 트 리 와 헷 갈 리 기 쉬 운 개념 이 고 완전 이 진 트 리 는 비슷 한 만 이 진 트 리 이다. 그 는 특정한 데이터 구조 (더미) 로 전환 할 수 있다. 다음은 이 진 트 리 가 완전 이 진 트 리 라 는 것 을 어떻게 판단 하 는 지 소개 한다.코드 는 다음 과 같다.
Boolean is_complete_binary_tree(Bin_tree root) //
{
// ， ，
// ，
Queue *queue = init_queue();
Tree_node *p_node = NULL;
Boolean find_last = FALSE; //
if(root == NULL){
return FALSE;
}
in(queue, root);
while(!is_queue_empty(queue)){
get_queue_front(queue, (void **)&p_node);
out(queue);
if(find_last == FALSE){
if(p_node->left_child != NULL && p_node->right_child != NULL){
//
in(queue, p_node->left_child);
in(queue, p_node->right_child);
}else if(p_node->left_child != NULL && p_node->right_child == NULL){
// ， ，
find_last = TRUE;
in(queue, p_node->left_child);
}else if(p_node->left_child == NULL && p_node->right_child != NULL){
// ，
return FALSE;
}else{
//
find_last = TRUE;
}
}else{
// ，
if(p_node->left_child != NULL || p_node->right_child != NULL){
return FALSE;
}
}
}
destroy_queue(&queue);
return TRUE;
}(4) 이 진 트 리 가 밸 런 스 이 진 트 리 인지 판단
균형 이 진 트 리 는 특수 한 요구 입 니 다. 즉, 이 진 트 리 의 좌우 아이들 의 높이 차 이 는 1 보다 크 면 안 됩 니 다. 일반적인 상황 에서 이런 엄격 한 요 구 는 이 진 트 리 를 찾 는 데 사 용 됩 니 다. 이 진 트 리 의 성질 은 다음 과 같 습 니 다. 요 소 를 찾 는 데 사 용 됩 니 다. 현재 노드 보다 작은 요 소 를 찾 으 면 현재 노드 의 왼쪽 트 리 부분 에서 찾 습 니 다. 현재 노드 보다 큰 요 소 를 찾 으 면현재 노드 의 오른쪽 하위 트 리 부분 에서 찾 습 니 다. 현재 노드 데이터 필드 의 요소 와 같 으 면 이미 찾 았 다 고 생각 합 니 다. 현재 노드 가 비어 있 으 면 전체 이 진 트 리 에서 찾 지 못 했다 고 생각 합 니 다.코드 예 시 는 다음 과 같다.
Boolean is_balance_binary_tree(Bin_tree root) //
{
int height_left = 0;
int height_right = 0;
Boolean left = FALSE;
Boolean right = FALSE;
// :
//
if(root == NULL){
return TRUE;
}
height_left = get_binarytree_height(root->left_child);
height_right = get_binarytree_height(root->right_child);
left = is_balance_binary_tree(root->left_child);
right = is_balance_binary_tree(root->right_child);
// ，
// 1
if(left == TRUE && right == TRUE
&& abs(height_left - height_right) <= 1){
return TRUE;
}else{
return FALSE;
}
}6. 이 진 트 리 기타 조작
(1) 이 진 트 리 의 미 러 를 얻 으 려 면 현재 이 진 트 리 노드 의 좌우 아이 주 소 를 교환 하고 좌우 아 이 를 재 귀적 으로 처리 해 야 합 니 다 (좌우 아 이 를 교환). 마지막 으로 원 이 진 트 리 를 미 러 대칭 적 으로 처리 해 야 합 니 다.코드 는 다음 과 같다.
void swap_left_right(Bin_tree root) //
{
if(root == NULL || (root->left_child == NULL
&& root->right_child == NULL)){
return ;
}
// ，
swap(&(root->left_child), &(root->right_child), sizeof(root->left_child));
swap_left_right(root->left_child);
swap_left_right(root->right_child);
}(2) 이 진 트 리 의 중간 값 이 value 인 노드 찾기
일반적인 이 진 트 리 라면, 우 리 는 나무 전 체 를 옮 겨 다 녀 야 한다.이것 은 이 진 트 리 의 노드 갯 수 에 의존 할 것 입 니 다. 현재 노드 의 데이터 값 이 조건 에 부합 되 는 지 먼저 판단 할 수 있 습 니 다. 만약 에 부합 되 지 않 으 면 좌우 서브 트 리 부분 을 선후 로 판단 할 수 있 습 니 다.코드 는 다음 과 같 습 니 다:
Tree_node *find_value(Bin_tree root, char value) // value
{
Tree_node *p_node = NULL;
if(root == NULL || root->data == value){
return root;
}
p_node = find_value(root->left_child, value);
if(p_node == NULL){
p_node = find_value(root->right_child, value);
}
return p_node;
}(3) 지정 한 노드 의 부모 노드 찾기
Tree_node *find_parent(Bin_tree root, Tree_node *node) //
{
Tree_node *p_node = NULL;
if(root == NULL || node == NULL
|| root->left_child == node || root->right_child == node){
// ，
return root;
}
// ， ，
// 。 ， NULL
p_node = find_parent(root->left_child, node);
if(p_node == NULL){
p_node = find_parent(root->right_child, node);
}
return p_node;
}(4) 두 노드 가 포함 관 계 를 가 지 는 지 판단 하려 면 먼저 두 개의 이 진 트 리 에 포 함 된 첫 번 째 노드 (뿌리 노드) 의 관 계 를 판단 해 야 한다. 만약 에 tree 2 의 뿌리 노드 가 tree 1 과 존재 한다 면 tree 2 의 다른 부분 을 판단 할 수 있다. tree 2 의 모든 노드 가 tree 1 에 존재 할 때 우 리 는 tree 2 가 tree 1 에 포함 되 어 있다 고 생각한다. 코드 예 는 다음 과 같다.
Boolean has_sub_tree(Bin_tree root1, Bin_tree root2) //
{
Boolean ok = FALSE;
if(root1 != NULL && root2 != NULL){
if(root1->data == root2->data){
// ，
ok = does_tree1_has_tree2(root1, root2);
}
if(ok == FALSE){
ok = has_sub_tree(root1->left_child, root2);
}
if(ok == FALSE){
ok = has_sub_tree(root1->right_child, root2);
}
}
return ok;
}
(5) 두 개의 나무 노드 를 찾 은 최근 의 공공 조상
이 문제 에 대해 우 리 는 두 가지 상황 에 대해 특별한 처 리 를 해 야 한다. 1. 이 두 노드 자체 가 직접적인 계승 관 계 를 가 질 때 (즉, 하 나 는 다른 노드 의 부모) 우 리 는 상부 에 그들의 조상 을 계속 찾 아야 한다.
2. 만약 에 이들 사이 에 계승 관계 가 없다 면 이 두 노드 의 위 치 를 판단 해 야 한다.
코드 예 시 는 다음 과 같다.
Tree_node *find_common_node(Bin_tree root, Tree_node *node1,
Tree_node *node2 ) //
{
// A
// / \
// B G
// / \ / \
// C D H J
// / \ \
// E F I
//
// 1. node1 node2 ，
//
// find_value
// find_parent
//
int height1 = get_binarytree_height(node1);
int height2 = get_binarytree_height(node2);
//
if(height1 > height2){
if(find_value(node1, node2->data) != NULL){
return find_parent(root, node1);
}
}else if(height1 < height2){
if(find_value(node2, node1->data) != NULL){
return find_parent(root, node2);
}
}
//
return find_common(root, node1, node2);
}
Tree_node *find_parent(Bin_tree root,
Tree_node *node) //
{
Tree_node *p_node = NULL;
if(root == NULL || root->left_child == node
|| root->right_child == node){
//root root
return root;
}
p_node = find_parent(root->left_child, node);
if(p_node == NULL){
p_node = find_parent(root->right_child, node);
}
return p_node;
}
static Tree_node *find_common(Bin_tree root,
Tree_node *node1, Tree_node *node2){
// ：
//
// node1 node2 root ， root ；
//
// （ ）， root （ ） ，
//
// node1 node2
if(find_value(root->left_child, node1->data)){
if(find_value(root->right_child, node2->data)){
return root;
}else{
return find_common(root->left_child, node1, node2);
}
}else{
if(find_value(root->left_child, node2->data)){
return root;
}else{
return find_common(root->right_child, node1, node2);
}
}
}상기 에서 우 리 는 이 진 트 리 에 관 한 많은 조작 을 한 다음 에 이런 조작 을 테스트 했다. 테스트 코드 는 다음 과 같다.
//
#include <stdio.h>
#include "binary_tree.h"
int main(int argc, char **argv)
{
Bin_tree root = NULL;
Bin_tree root1 = NULL;
Bin_tree root2 = NULL;
Tree_node *find = NULL;
char *str = "ABC##DE##F##GH#I##J##";
char *pre = "ABCDEFGHIJ";
char *mid = "CBEDFAHIGJ";
char *last = "CEFDBIHJGA";
Boolean equal = FALSE;
root = create_tree(&str); //
root1 = create_tree_by_pre_mid(pre, mid, strlen(pre));
printf("pre order:
");
pre_order_print(root);
printf("
");
printf("mid order:
");
mid_order_print(root);
printf("
");
printf("last order:
");
last_order_print(root);
printf("
");
printf("last order:
");
last_order_print(root1);
printf("
");
printf("level order:
");
level_order_print(root1);
printf("
");
printf("pre order:
");
pre_order_print_nr(root);
printf("
");
printf("mid order:
");
mid_order_print_nr(root);
printf("
");
root2 = copy_binary_tree(root1); //
if((equal = is_binarytree_equal(root1, root2)) == TRUE){
printf("two trees are equal!
");
}
printf("mid order:
");
mid_order_print_nr(root2);
printf("
");
printf("the height of root2:%d
", get_binarytree_height(root2));
printf("the count of root2:%d
", get_binarytree_node_count(root2));
printf("the leaves count of root2:%d
", get_binarytree_leaf_count(root2));
//
swap_left_right(root1);
printf("pre order:
");
pre_order_print_nr(root1);
printf("
");
//
if(is_full_binary_tree(root1) == TRUE){
printf("root1 is full!
");
}else{
printf("root1 is not full!
");
}
// n
printf("the %d level count is:%d
", 3, get_binarytree_level_count(root, 3));
if((find = find_value(root, 'H')) == NULL){
printf("H is not found!
");
}else{
printf("%c is found!
", find->data);
}
Tree_node *find1 = find_value(root, 'B');
Tree_node *find2 = find_value(root, 'I');
//
Tree_node *parent = find_common_node(root, find1, find2);
if(parent != NULL){
printf("(%c and %c) parent is:%c
",
find1->data, find2->data, parent->data);
}else{
printf("not have baba!
");
}
destroy_tree_nr(&root);
destroy_tree_nr(&root1);
destroy_tree_nr(&root2);
return 0;
}작은 매듭
이 진 트 리 는 매우 신기 한 데이터 구조 로 선형 데이터 구조의 검색 과 삽입 효율 의 병목 을 해결 하기 때문에 우 리 는 그의 구조 와 응용 을 깊이 이해 해 야 한다. 다음 장 에서 우 리 는 더 많은 이 진 트 리 유형 (이 진 트 리, 이 진 트 리 등) 과 다 진 트 리 (B 트 리) 를 소개 할 것 이다.기대 해 주세요.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
