예비 지식

나무의 귀속 정의: 한 그루의 나무는 일부 노드의 집합이고 이런 집합은 빈 집합일 수 있다.만약 비어 있지 않다면, 한 그루의 나무는 뿌리 노드 r와 0개 이상의 비어 있지 않은 자목 T1, T2,..., Tk로 구성되어 있으며, 이 자목 중의 모든 뿌리는 뿌리 r의 한 줄기에서 가장자리로 연결되어 있다.
나무의 이러한 귀속 정의는 나무와 관련된 프로그램을 작성할 때 귀속적으로 작성하는 것이 비교적 편리하다.
 
노드 n1에서nk까지의 경로의 길이는 이 경로의 상단의 수로 정의됩니다.
 
임의의 노드 니에 대해 니의 깊이는 뿌리에서 니까지의 유일한 경로입니다.루트의 깊이는 0입니다.
니의 높이는 니에서 나뭇잎까지의 가장 긴 경로이다.모든 나뭇잎의 높이는 0이다.나무 한 그루의 높이는 그 뿌리의 높이와 같다.
한 그루의 나무의 깊이는 가장 깊은 나뭇잎의 깊이와 같고 뿌리의 높이와 같다.
 
나무의 실현은 왼쪽 아이와 오른쪽 형제의 방법을 채택할 수 있다.
 

트리의 반복 및 응용

1. UNIX, VAX/VMS 및 DOS 등 많은 일반 운영 체제의 디렉토리 구조로 사용됩니다.
서로 다른 디렉터리 아래의 두 파일은 이름이 같을 수 있습니다. 왜냐하면 서로 다른 디렉터리 아래의 두 파일은 반드시 나무 뿌리에서 시작하는 서로 다른 경로 이름이 있기 때문입니다.
선서적 반복: 선서적 반복에서 노드에 대한 처리 작업은 그의 모든 아들 노드가 처리되기 전에 진행된다.
2. 각 파일이 디스크 블록을 차지하는 개수를 계산합니다.
후서적 반복: 후서적 반복에서 노드에 대한 처리 작업은 실제 아들 노드가 계산된 후에 이루어진다.
 

두 갈래 나무

노드마다 두 아들보다 많은 나무가 있을 수 없다.
N개의 노드가 있는 두 갈래 트리마다 N+1개의 NULL 포인터가 필요합니다.
 
표현식 트리:
앞의 순서: 노드, 왼쪽, 오른쪽
중역: 왼쪽, 노드, 오른쪽
후순 반복: 왼쪽, 오른쪽, 노드
 

두 갈래 찾기 트리:

#include "BinarySearchTree.h"
#include <iostream>
using namespace std;

struct TreeNode {
	ElementType Element;
	SearchTree Left;
	SearchTree Right;
};

SearchTree MakeEmpty(SearchTree T)
{
	if (T!=NULL) {
		MakeEmpty(T->Left);
		MakeEmpty(T->Right);
		delete T;
	}
	return NULL;
}

Position Find(ElementType X, SearchTree T)
{
	if (T==NULL)
		return NULL;
	else if (T->Element<X)
		return Find(X, T->Right);
	else if (T->Element>X)
		return Find(X, T->Left);
	else
		return T;
}

Position FindMin(SearchTree T)
{
	if (T==NULL)
		return NULL;
	else if (T->Left==NULL)
		return T;
	else
		return FindMin(T->Left);
}

Position FindMax(SearchTree T)
{
	if (T==NULL)
		return NULL;
	else if (T->Right==NULL)
		return T;
	else
		return FindMax(T->Right);
}

SearchTree Insert(ElementType X, SearchTree T)
{
	if (T==NULL) {
		T = new struct TreeNode;
		if (T==NULL) {
			cout<<"out of memory, new element failed"<<endl;
			return NULL;
		} else {
			T->Element = X;
			T->Left = T->Right = NULL;
		}
	} else  if (T->Element<X)
			T->Right = Insert(X, T->Right);
	 else if (T->Element>X)
		T->Left = Insert( X, T->Left);
	//else T->Element==X,we will do nothing
	return T;
}

SearchTree Delete(ElementType X, SearchTree T)
{
	Position TempCell;
	if (T==NULL) {
		cout<<"Element not found"<<endl;
		return NULL;
	} else if (T->Element<X)
		T->Right = Delete(X, T->Right);
	else if (T->Element>X)
		T->Left = Delete(X, T->Left);
	else if (T->Left && T->Right) {
		TempCell = FindMin(T->Right);
		T->Element = TempCell->Element;
		T->Right = Delete(T->Element, T->Right);
	} else {
		TempCell = T;
		if (T->Left==NULL)
			T = T->Right;
		else if (T->Right==NULL)
			T = T->Left;
		delete TempCell;
	}
	return T;
}

void PrintTree(SearchTree T)
{
	if (T==NULL)
		return;
	else {
		cout<<T->Element<<" ";
		PrintTree(T->Left);
		PrintTree(T->Right);
	}
}
int main(int argc, char **argv)
{
	Position T = NULL;
	T = Insert(6, T);
	T = Insert(2, T);
	T = Insert(8, T);
	T = Insert(1, T);
	T = Insert(4, T);
	T = Insert(3, T);
	cout<<(FindMin(T))->Element<<endl;
	cout<<(FindMax(T))->Element<<endl;
	PrintTree(T);cout<<endl;
	Delete(1, T);
	PrintTree(T);cout<<endl;
	Delete(6, T);
	PrintTree(T);cout<<endl;

	system("pause");
	return 0;
}