이 진 트 리 의 트 리 인쇄

예 쁜 이 진 트 리 인쇄 하기
원래 의 기초 위 에서 이 진 트 리 출력의 자리 표시 자 에 대해 동적 변 화 를 실현 하여 인쇄 범 위 를 넓 힐 수 있 지만, 다시 디 스 플레이 출력 을 교정 할 수 있 는 경 우 를 제외하고는 예 쁘 지 않다 고 할 수 밖 에 없다.더 좋 은 해결책 이 있 을 거 라 고 생각 합 니 다.제 이해: 주어진 나무의 높이 는 서로 다른 깊이 의 노드 의 수량 범 위 를 추측 하고 서로 다른 깊이 의 노드 의 폭 을 예상 하여 자리 표시 자의 합 리 적 인 설정 을 실현 할 수 있 습 니 다.기능 이 실 현 된 함수 부터 시작 합 시다!

//      
int getHeight(const linklist node) {	//      
	int treeHeight = 0;
	if (node != NULL) {
		int leftHeight = getHeight(node->lchild);
		int rightHeight = getHeight(node->rchild);
		treeHeight = leftHeight >= rightHeight? leftHeight + 1:rightHeight + 1;
	}
	return treeHeight;
}

void postorder(linklist p) {
int height = getHeight(p);
	for (int i = 0 ; i < getHeight(p); i ++) {
		printRow(p, height, i);
		height--;
	}
}

상기 코드 는 매우 간단 합 니 다. 주로 * printRow () * 함수 입 니 다. 지금 은 깊이 알 아 보 겠 습 니 다.

void printRow(const linklist p, const int height, int depth) {
	vector vec;
	int placeholder=-1;
	getLine(p, depth, vec);
	int flag=height;
	cout << setw(pow(2,flag)-1); // scale setw with depth
	bool toggle = true; // start with left
	if (vec.size() > 1) {
		for (int v=0; v

getLine () 에서 실 행 된 작업: 같은 깊이 를 가 진 모든 노드 를 vec 에 저장 합 니 다.이것 은 코드 입 니 다:

void getLine(const linklist root, int depth, vector& vals) {
	int placeholder=-1;
	if (depth <= 0 && root != NULL) {
		vals.push_back(root->value);
		return;
	}
	if (root->lchild != NULL)
		getLine(root->lchild, depth-1, vals);
	else if (depth-1 <= 0)
		vals.push_back(placeholder);
	if (root->rchild != NULL)
		getLine(root->rchild, depth-1, vals);
	else if (depth-1 <= 0)
		vals.push_back(placeholder);
}

이제 * printRow () * 함수 로 돌아 갑 니 다. 각 줄 에 대해 우 리 는 이 진 트 리 의 깊이 에 따라 흐름 폭 을 설정 합 니 다. 그러면 서로 다른 깊이 의 이 진 트 리 에 합 리 적 인 자리 표시 자 를 분배 하고 이 진 트 리 를 가능 한 한 아름 답 게 인쇄 하 는 데 유리 합 니 다. 여기 서 저 는 이 진 트 리 를 예 로 들 어 자리 표시 자 를 설명 합 니 다.
depth
left
mid-data
1
2^(n-1)-1
2^n-1
…
…
…
n-3
7
15
n-2
3
7
n-1
1
3
n
0
1
depth: 이 진 트 리 의 깊이;왼쪽 첫 번 째 요소 에서 왼쪽 임계 에 있 는 자리 표시 자 (빈 칸);mid - data: 각 층 의 인접 데이터 간격 사이 의 자리 표시 자
깊이 가 조금 클 때 는 그다지 예 뻐 보이 지 않 으 니 보완 해 주시 기 바 랍 니 다.나무 가 대체로 균형 이 잡 히 고 작 으 면 좋아 질 것 이다.자리 표시 자가 있어 야 "/" 와 "\" 문 자 를 정확하게 정렬 할 수 있 습 니 다.또한 getLine () 을 통 해 줄 을 가 져 올 때 깊이 가 지정 한 노드 가 없 으 면 자리 표시 자 를 삽입 합 니 다.자리 표시 자 는 모든 표지 로 설정 할 수 있 습 니 다.그러나 이것 은 완벽 하지 않다. 왜냐하면 자리 표시 자 안에 저 장 된 것 은 효과 적 인 노드 값 일 수 있 기 때문이다.
순차 삽입 데이터: 10, 5, 1, 7, 12, 15

     10
  /      \
  5     12
/  \     \
1  7    15