트 리 와 대량 데이터 처리

1. 이 진 트 리 재건
앞 순서 와 중간 순서 로 옮 겨 다 니 는 결과 에 따라 뒤 순 서 를 찾 아 옮 겨 다 니 세 요.

#include <stdio.h>
#include <string.h>

//                
int Find(char in[], char ch, int s, int e)
{
	while(s <= e && in[s] != ch)
	{
		s++;
	}
	return s;
}

void PostTraverse(char pre[], int ps, int pe, char in[], int is, int ie)
{
	int k;
	char c;
	if(is > ie ) return; //     
	if(is == ie) {printf("%c ", in[is]); return;} //         

	//                   
	c = pre[ps];
	k = Find(in, c, is, ie); //               
	PostTraverse(pre, ps + 1, ps + k - is, in, is, k - 1); //        
	PostTraverse(pre, ps + k - is + 1, pe, in, k + 1, ie); //        
	printf("%c ", c); //      
}

int main()
{
	char pre[] = "ABCDEGF";
	char in[] = "CBEGDFA";
	PostTraverse(pre, 0, strlen(in) - 1, in, 0, strlen(pre) - 1);
	printf("
");
	return 0;
}

2. 이 진 트 리 가 층 을 나 누 어 옮 겨 다 닌 다.
이 진 트 리 의 층 을 나 누 어 재 귀 를 통 해 이 루어 질 수 있 지만 상대 적 으로 효율 이 낮다.이 진 트 리 k 층 결점 에 접근 할 때 k - 1 층 결점 의 정 보 를 알 고 k - 1 층 결점 정 보 를 배열 에 저장 하여 cur 로 현재 방문 의 결점 을 표시 하고 last 는 현재 차원 의 마지막 결점 의 다음 위 치 를 표시 합 니 다. cur = = last 시 현재 층 차 방문 이 끝 납 니 다.k 층 에 접근 할 때 k + 1 의 모든 결산 점 을 배열 에 저장 하고 k 층 에 접근 할 때 모든 단계 에 접근 할 수 있 는 새로운 차원 이 있 는 지 판단 합 니 다.

#include <iostream>
#include <vector>
#include <string>
using namespace std;

typedef struct BiNode
{
	char data;
	struct BiNode *lchild;
	struct BiNode *rchild;
} BiTree;

/*      ,   ：abc##de#g##f### */
void CreateBiTree(BiTree *&root)
{
	char ch;
	cin >> ch;
	if(ch == '#')
	{
		root = NULL;
	}
	else
	{
		root = new BiNode;
		root->data = ch;
		root->lchild = root->rchild = NULL;
		CreateBiTree(root->lchild);
		CreateBiTree(root->rchild);
	}
}

/*        */
void PreOrderTraverse(const BiTree *root)
{
	if(root)
	{
		cout << root->data << " ";
		PreOrderTraverse(root->lchild);
		PreOrderTraverse(root->rchild);
	}
}

void PrintByLevel(BiTree *root)
{
	int cur = 0, last = 1;
	vector<BiTree *> vec;

	if(root == NULL)
		return;

	vec.push_back(root);
	while(cur < vec.size())
	{
		last = vec.size();
		while(cur < last)
		{
			cout << vec[cur]->data << " ";
			if(vec[cur]->lchild)
				vec.push_back(vec[cur]->lchild);
			if(vec[cur]->rchild)
				vec.push_back(vec[cur]->rchild);
			cur++;
		}
		cout << endl << endl;
	}
}

/*       */
void InOrderTraverse(const BiTree *root)
{
	if(root)
	{
		InOrderTraverse(root->lchild);
		cout << root->data << " ";
		InOrderTraverse(root->rchild);
	}
}

/*        */
void PostOrderTraverse(const BiTree *root)
{
	if(root)
	{
		PostOrderTraverse(root->lchild);
		PostOrderTraverse(root->rchild);
		cout << root->data << " ";
	}
}

int main()
{
	BiTree *root;
	CreateBiTree(root);
	/*PreOrderTraverse(root);
	cout << endl;
	InOrderTraverse(root);
	cout << endl;
	PostOrderTraverse(root);
	cout << endl;*/

	PrintByLevel(root);

	return 0;
}

3. 하나의 배열 을 지정 하고 배열 중의 요 소 는 오름차 순 으로 배열 하 며 그 중의 두 요소 의 합 이 m 인 수 대 를 구한다.
배열 a 의 요 소 를 a1, a2,..., an 으로 설정 하고 a1 < a2 <........................................................i = 1, j = n:
하면, 만약, 만약... > m, i < x < j 가 ai + ax = m 가 존재 할 수 있 음 을 설명 합 니 다.
하면, 만약, 만약... < m, i < x < j 로 인해 ax + aj = m 는 i + + 가 있 음 을 설명 합 니 다.
하면, 만약, 만약... = m, 설명 은 출력 (i, j)
만약 i > = j 는 배열 에 조건 을 만족 시 키 는 수량 이 존재 하지 않 는 다 는 것 을 의미한다.

#include <stdio.h>

#define ARRSIZE 10

int main()
{
	int m, i = 0, j = ARRSIZE - 1, n = 0;
	int a[ARRSIZE];

	for(i = 0; i < ARRSIZE; i++)
		scanf("%d", &a[i]);

	scanf("%d", &m);
	i = 0;
	while(i < j)
	{
		if(a[i] + a[j] > m)
			j--;
		else if(a[i] + a[j] < m)
			i++;
		else
		{
			printf("(%d, %d)
", a[i], a[j]);
			i++; j--; n++;
		}
	}
	if(i == 0)
		printf("      (i, j)  a[i] + a[j] == m");
	
	return 0;
}

4. 이 진 트 리 두 그루 가 같은 지 판단
두 그루 의 이 진 트 리 root 1 과 root 2 는 다음 과 같은 두 가지 상황 이 있다.
1. 루트 1 과 루트 2 가 모두 빈 나무 라면
2. 루트 1 의 왼쪽 나무 가 루트 2 의 왼쪽 나무 와 같 고 루트 1 의 오른쪽 나무 가 루트 2 의 오른쪽 나무 와 같다 면

#include <iostream>
#include <cstdio>
#include <string>
using namespace std;

typedef struct BiNode
{
	char data;
	struct BiNode *lchild;
	struct BiNode *rchild;
} BiTree;

/*            ：abc##de#g##f### */
void CreateBiTree(BiTree *&root)
{
	char ch;
	cin >> ch;
	if(ch == '#')
	{
		root = NULL;
	}
	else
	{
		root = new BiNode;
		root->data = ch;
		root->lchild = root->rchild = NULL;
		CreateBiTree(root->lchild);
		CreateBiTree(root->rchild);
	}
}

/*           ，    1，    0 */
int EqualTree(BiTree *root1, BiTree *root2)
{
	if(!root1 && !root2)
		return 1;
	if(!root1 || !root2)
		return 0;
	if(root1->data != root2->data)
		return 0;
	if(EqualTree(root1->lchild, root2->lchild) && EqualTree(root1->rchild, root2->rchild))
		return 1;
	return 0;
}

int main()
{
	BiTree *root1, *root2;
	CreateBiTree(root1);
	CreateBiTree(root2);
	if(EqualTree(root1, root2) == 1)
		cout << "equal" << endl;
	else
		cout << "not equal" << endl;

	return 0;
}

5. 대량의 데이터 중 주파수 가 가장 높 은 k 개 수 를 구하 십시오.