横向打印二叉树

问题描述

二叉树可以用于排序。其原理很简单：对于一个排序二叉树添加新节点时，先与根节点比较，若小则交给左子树继续处理，否则交给右子树。

当遇到空子树时，则把该节点放入那个位置。

比如，10 8 5 7 12 4 的输入顺序，应该建成二叉树如下图所示，其中.表示空白。

...|-12
10-|
...|-8-|
.......|...|-7
.......|-5-|
...........|-4

本题目要求：根据已知的数字，建立排序二叉树，并在标准输出中横向打印该二叉树。

输入格式

输入数据为一行空格分开的N个整数。 N<100，每个数字不超过10000。

输入数据中没有重复的数字。

输出格式

输出该排序二叉树的横向表示。为了便于评卷程序比对空格的数目，请把空格用句点代替：

样例输入1

10 5 20

样例输出1

...|-20
10-|
...|-5

样例输入2

5 10 20 8 4 7

样例输出2

.......|-20
..|-10-|
..|....|-8-|
..|........|-7
5-|
..|-4

其实就是按照右子树根左子树的顺序遍历，每个输出占一行，写一个递归遍历的函数，traversal(BST *node,int h),h是空白的位数，当然空白中可能也有'|'，对于结点node先遍历

它的右子树即最先输出的，node和他的右子树之间是竖线连接的，即他们之间这些行每行相同位置都是’|‘取代'.'，一共多少行(node右子树的左子树结点总数），后面左子树的情况类似。不过这里右子树的情况需要加个判断，因为遍历是从node右子树的右子树开始。num记录行数，tar记录这个判断条件也就是node的右结点Data，只有比这个值小才满足。

代码：

#include <iostream>
#include <cstdio>
#include <map>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;
struct BST {
    int Data,l,r;
    BST *Left = NULL,*Right = NULL;
    BST(int d) {
        Data = d;
        l = 0,r = 0;///记录左子树结点个数以及右子树的  后面遍历用到
    }
}*head;
int num[2000];
int tar[2000];
BST* Insert(BST *h,int d) {
    if(h == NULL) {
        h = new BST(d);
    }
    else if(d < h -> Data) {
        h -> Left = Insert(h -> Left,d);
        h -> l ++;
    }
    else {
        h -> Right = Insert(h -> Right,d);
        h -> r ++;
    }
    return h;
}
int nc(int d) {
    int c = 0;
    while(d) {
        c ++;
        d /= 10;
    }
    return c;
}
void traversal(BST *node,int h) {///中序遍历  右 中 左
    if(node == NULL) return;
    int ht = nc(node -> Data);///h是上层空白的个数，ht记录这一层的数字占的空间那么下一层需要输出的空白就是h + ht
    if(h) ht += 2;///不是根  数字前要输出 |-   所以这是两个位
    if(node -> Left || node -> Right) ht ++;///有子树需要输出 -|  竖线重合不算在内
    if(node -> Right) {
        num[h + ht] += node -> Right -> l;///右子树的左子树的结点个数 表示 后面在输出右子树的左子树的时候h + ht位置不输出'.'而是输出'|'
        tar[h + ht] = node -> Right -> Data;///因为这中间情况会先遍历右子树的右子树 为了避免提前输出'|'所以设置当Data小于tar时才输出
        traversal(node -> Right,h + ht);
    }
    for(int i = 0;i < h;i ++) {
        if(num[i] && (tar[i] == 10001 || node -> Data < tar[i])) {
            putchar('|');
            num[i] --;
        }
        else putchar('.');
    }
    if(h) printf("|-");
    printf("%d",node -> Data);
    if(node -> Left || node -> Right) printf("-|");
    putchar('
');
    if(node -> Left) {
        num[h + ht] += node -> Left -> r;
        tar[h + ht] = 10001;///跟前面不同
        traversal(node -> Left,h + ht);
    }
}
int main() {
    int d;
    while(~scanf("%d",&d)) {
        head = Insert(head,d);
    }
    traversal(head,0);
}