한 걸음 한 걸음 알고리즘 (정렬 이 진 트 리)

【 성명: 판권 전부, 전재 환영, 상업 용도 로 사용 하지 마 십시오. 연락처: feixiaoxixing @ 163. com]
    앞에서 우 리 는 양 방향 링크 의 데이터 구 조 를 말 한 적 이 있다.모든 순환 노드 는 두 개의 지침 이 있 는데 하 나 는 앞의 노드 를 가리 키 고 하 나 는 후계 노드 를 가리 키 며 모든 노드 는 진주 처럼 한 개의 선 에 의 해 연결 된다.그러나 오늘 우리 가 토론 한 데이터 구 조 는 조금 다르다. 그것 은 세 개의 노드 가 있다.이것 은 이렇게 정의 합 니 다.

typedef struct _TREE_NODE
{
	int data;
	struct _TREE_NODE* parent;
	struct _TREE_NODE* left_child;
	struct _TREE_NODE* right_child;
}TREE_NODE;

    위의 데이터 구조 에 따 르 면 우 리 는 모든 데이터 노드 에 세 개의 지침 이 있 는 것 을 보 았 다. 각각 부 모 를 가리 키 는 지침, 왼쪽 아 이 를 가리 키 는 지침, 오른쪽 아 이 를 가리 키 는 지침 이다.모든 노드 는 지침 을 통 해 서로 연결된다.지침 과 연 결 된 관 계 는 모두 부자 관계 이다.그럼 정렬 이 진 트 리 는 무슨 뜻 인가요?사실은 매우 easy 입 니 다. 이 진 트 리 의 기본 정의 에 두 가지 기본 조건 을 추가 하면 됩 니 다. (1) 모든 왼쪽 트 리 의 노드 수 치 는 이 노드 의 수치 보다 작 습 니 다.(2) 모든 오른쪽 노드 의 수 치 는 이 노드 의 수치 보다 크다.
    노드 의 정 의 를 본 이상 우 리 는 일정한 순서에 따라 옮 겨 다 니 며 이 진 트 리 의 노드 를 특정한 순서에 따라 인쇄 할 수 있다.그러면 노드 의 생 성, 찾기, 옮 겨 다 니 는 것 은 어떻게 진행 되 는 것 입 니까? 이 진 트 리 의 높이 는 어떻게 계산 해 야 합 니까?우 리 는 하나하나 말 했다.
    1) 이 진 트 리 노드 만 들 기

TREE_NODE* create_tree_node(int data)
{
	TREE_NODE* pTreeNode = NULL;
	pTreeNode = (TREE_NODE*)malloc(sizeof(TREE_NODE));
	assert(NULL != pTreeNode);

	memset(pTreeNode, 0, sizeof(TREE_NODE));
	pTreeNode->data = data;
	return pTreeNode;
}

    분석: 이 진 트 리 노드 의 생 성 은 우리 가 본 링크 노드, 스 택 노드 의 생 성 과 본질 적 인 차이 가 없다 는 것 을 알 수 있 습 니 다.먼저 노드 에 메모 리 를 만 든 다음 메모리 초기 화 처 리 를 해 야 합 니 다.마지막 으로 입력 매개 변수 data 를 tree 에 입력 합 니 다.node 그 중 에 돼 요.
    2) 데이터 찾기

TREE_NODE* find_data_in_tree_node(const TREE_NODE* pTreeNode, int data)
{
	if(NULL == pTreeNode)
		return NULL;

	if(data == pTreeNode->data)
		return (TREE_NODE*)pTreeNode;
	else if(data < pTreeNode->data)
		return find_data_in_tree_node(pTreeNode->left_child, data);
	else
		return find_data_in_tree_node(pTreeNode->right_child, data);
}

    분석: 우리 의 검색 은 재 귀 교체 에 따라 진행 된다.전체 이 진 트 리 는 정렬 이 진 트 리 이기 때문에 우리 의 데 이 터 는 각 노드 와 순서대로 비교 하면 된다. 만약 에 수치 가 노드 데이터 보다 작다 고 가정 하면 왼쪽으로 계속 옮 겨 다 닐 수 있다.반대로 오른쪽으로 계속 옮 겨 다 니 세 요.옮 겨 다 니 면서 NULL 지침 을 만 났 다 고 가정 하면 현재 데이터 가 이 진 트 리 에 존재 하지 않 는 다 는 것 을 설명 할 수 있 습 니 다.
    3) 데이터 통계

int count_node_number_in_tree(const TREE_NODE* pTreeNode)
{
	if(NULL == pTreeNode)
		return 0;

	return 1 + count_node_number_in_tree(pTreeNode->left_child)
		+ count_node_number_in_tree(pTreeNode->right_child);
}

    분석: 위 에서 데 이 터 를 찾 는 것 과 마찬가지 로 통계 작업 도 간단 하 다.노드 포인터 라 고 가정 하면 0 으로 돌아 가면 됩 니 다. 그렇지 않 으 면 왼쪽 노드 트 리 의 노드 갯 수, 오른쪽 노드 트 리 의 노드 갯 수 를 각각 통계 해 야 합 니 다. 그러면 모든 노드 총 수 를 합치 면 됩 니 다.
    4) 작은 것 부터 큰 것 까지 의 순서에 따라 노드 의 데 이 터 를 출력 한다.

void print_all_node_data(const TREE_NODE* pTreeNode)
{
	if(pTreeNode){
		print_all_node_data(pTreeNode->left_child);
		printf("%d
", pTreeNode->data);
		print_all_node_data(pTreeNode->right_child);
	}
}

    분석: 이 진 트 리 자체 의 특수성 때문에 이 진 트 리 를 순서대로 인쇄 하 는 함수 자체 도 비교적 간단 하 다.먼저 왼쪽 트 리 의 노드 를 인쇄 한 다음 에 이 노드 의 수 치 를 인쇄 하고 마지막 으로 오른쪽 트 리 노드 의 수 치 를 인쇄 하면 모든 노드 의 수 치 를 인쇄 할 수 있 습 니 다.
    5) 통계 나무의 높이

int calculate_height_of_tree(const TREE_NODE* pTreeNode)
{
	int left, right;
	if(NULL == pTreeNode)
		return 0;

	left = calculate_height_of_tree(pTreeNode->left_child);
	right = calculate_height_of_tree(pTreeNode->right_child);
	return (left > right) ? (left + 1) : (right + 1);
}

    분석: 나무의 높이 는 사실상 모든 잎 노드 에서 뿌리 노드 에서 잎 노드 까지 의 최대 높이 가 얼마나 될 수 있 는 지 를 말한다.물론 프로그램 에서 매우 명확 하 게 표 시 했 습 니 다. 노드 가 비어 있다 고 가정 하면 매우 유감 입 니 다. 노드 의 높이 는 0 입 니 다.반대로 왼쪽 나무의 높이 가 오른쪽 나무의 높이 보다 크다 고 가정 하면 전체 이 진 트 리 의 노드 높이 는 왼쪽 나무의 높이 에 1 을 더 하 는 것 이다.오른쪽 나무의 높이 가 왼쪽 나무의 높이 보다 크다 고 가정 하면 전체 이 진 트 리 의 높이 는 바로 오른쪽 나무의 높이 에 1 을 더 하 는 것 이다.나무의 높이 를 계산 하 는 것 은 우리 가 균형 이 잡 힌 이 진 트 리 를 디자인 할 때 매우 실 용적 입 니 다. 특히 테스트 할 때 많은 이해 와 숙련 을 바 랍 니 다.
요약:
    1) 이 진 트 리 는 모든 나무의 기초 입 니 다. 가능 한 균형 이 진 트 리, 선형 이 진 트 리, 붉 은 검 은 나무, 복합 이 진 트 리, b 나무, b + 나 무 는 모두 이 를 바탕 으로 열심히 공부 하 시기 바 랍 니 다.
    2) 이 진 트 리 의 매우 많은 조작 은 스 택 과 밀접 한 관 계 를 가진다. 만약 에 여러분 이 일시 적 으로 재 귀 를 이해 하지 못 한다 고 가정 하면 순환 이나 스 택 으로 대체 할 수 있다.
    3) 진지 한 지식 을 실천 하면 정렬 이 진 트 리 의 코드 를 많이 연습 할 수 있 습 니 다.저 는 개인 적 으로 균형 이 잡 힌 이 진 트 리 를 20 번 도 넘 게 쓰 지 않 습 니 다. 그래도 매번 정확 하 다 는 보장 은 없습니다.그럼 에 도 불구 하고 나 는 코드 를 쓸 때마다 다른 느낌 을 받는다.
[예고: 다음 블 로 그 는 균형 트 리 의 삽입 과 삭 제 를 소개 합 니 다]