横向打印二叉树

问题描述

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

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

比如，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

这个题并没有做出来，首先手打了一个二叉搜索树，然后中序遍历，遍历的结果就是这个横向打印的二叉树的从下向上的值，如样例中的：

5　　10　　20　　8　　4　　7

中序遍历的结果是：

4　　5　　7　　8　　10　　20

也刚好是排序之后的结果。

在这里我还有一个问题没有解决，那就是求每个节点的深度，或是每个深度都有哪些节点。这样子的话，我们就能找到每个值在二叉树中的具体位置（只要我们把这个树看成一个网格）

但是这个二叉树的第一个指针指向的不是根节点，而是最后一个我们插入的值。最终也没能算出每个节点的深度。

  1 #include<iostream>
  2 #include<string>
  3 
  4 using namespace std;
  5 
  6 struct node{
  7     int val;
  8     node *lc, *rc;
  9 }; 
 10 
 11 // 插入 
 12 node* insert(node *p, int x)
 13 {
 14     if(p == NULL){
 15         node *q = new node;
 16         q -> val = x;
 17         q -> lc = q -> rc = NULL;
 18         return q;
 19     }
 20     else{
 21         if(x < p -> val) p -> lc = insert(p -> lc, x);
 22         else p -> rc = insert(p -> rc, x);
 23         return p;
 24     }
 25 }
 26 
 27 // 查找
 28 int find(node* p, int x, int dp)
 29 {
 30     if(p == NULL) return -1;
 31     else if(x == p -> val) return dp;
 32     else if(x < p -> val) return find(p -> lc, x, dp+1);
 33     else return find(p -> rc, x, dp+1);
 34  } 
 35 
 36 
 37  
 38 // 删除
 39 node* remove(node *p, int x)
 40 {
 41     if(p == NULL) return NULL;
 42     else if(x < p -> val) p -> lc = remove(p -> lc, x);
 43     else if(x > p -> val) p -> rc = remove(p -> rc, x);
 44     else if(p -> lc == NULL){
 45         node *q = p -> rc;
 46         delete p;
 47         return q;
 48     }
 49     else if(p -> lc -> rc == NULL){
 50         node *q = p -> lc;
 51         q -> rc = p -> rc;
 52         delete p;
 53         return q;
 54     }
 55     else{
 56         node *q;
 57         for(q = p -> lc;q -> rc -> rc != NULL;q = q -> rc);
 58         node *r = q -> rc;
 59         q -> rc = r -> lc;
 60         r -> lc = p -> lc;
 61         r -> rc = p -> rc;
 62         delete p;
 63         return r; 
 64     }
 65     return p;
 66  } 
 67 
 68 // 回忆一下整数快速幂 
 69 int pow(int x, int n)
 70 {
 71     int ret = 1;
 72     if(n == 0) return 1;
 73     while(n)
 74     {
 75         if(n&1) ret *= x;
 76         x *= x;
 77         n >>= 1;
 78     }
 79     return ret;
 80 }
 81 
 82 // 中序遍历 
 83 int ret[109] = {0};
 84 int NUM = 0;
 85 void InOder(node *b)
 86 {
 87     if(b != NULL){
 88         InOder(b -> lc);
 89         // cout<<b -> val<<endl;
 90         ret[++NUM] = b -> val;
 91         InOder(b -> rc);
 92     }
 93 }
 94 
 95 // 求节点的深度 
 96 int find_deep(node *p, int x, int dp)
 97 {
 98     // cout<<dp<<endl;
 99     if(p -> val == x) return dp;
100     if(p != NULL)
101     {
102         find_deep(p -> rc, x, ++dp);
103         find_deep(p -> lc, x, ++dp);
104     }
105 }
106 
107 /*-----------------------------*/
108 // 查找某个节点的深度 
109 static int depth=0;
110 void print_depth(node *p)
111 {
112     depth++;
113     if(!p)
114         goto out;
115     else{
116         printf("node %d: %d
", p -> val, depth);
117         print_depth(p -> rc);
118         print_depth(p -> lc);
119     }
120     out:
121            depth--;
122 }
123 /*----------------------------*/
124 void level_sum_out(node *p, int level){  
125   
126     if(!p){  
127         return;  
128     }  
129   
130     if(1==level){  
131         printf("%d ",p->val);  
132     }else{  
133         level_sum_out(p->lc,level-1);  
134         level_sum_out(p->rc,level-1);  
135     }  
136 }  
137 
138 //如何求出二叉树的高度?  
139 int getHeight(node *p){  
140     if(NULL==p){  
141         return 0;  
142     }else{  
143         int lh=getHeight(p->lc);  
144         int rh=getHeight(p->rc);  
145         return (lh>rh)?(lh+1):(rh+1);  
146     }  
147 }  
148 /*----------------------------*/
149 int main()
150 {
151     string s;
152     // 输入没有说明长度, getline 好点 
153     getline(cin, s);
154     int an = 0;
155     // 先记录一下根节点 
156     for(int i=0;i<s.size();i++){
157         if(s.at(i) == ' ') break;
158         an += (int(s.at(i)) - '0') * pow(10, i);
159     } 
160     // cout<<"an: "<<an<<endl; 
161     // 建立二叉搜索树 
162     node *t = NULL;
163     s = " " + s;
164     // 反向迭代器可以避免考虑数的位数 
165     string::reverse_iterator rite;
166     int k = 0, num = 0;
167     for(rite = s.rbegin();rite!=s.rend();rite++){
168         if(*rite == ' '){
169             // cout<<num<<endl;
170             t = insert(t, num);
171             k = num = 0;
172             continue;
173         }
174         num += (int(*rite)-'0') * pow(10, k++);
175     }
176     // 接下来就是想办法将它打印出来 
177     // 中序遍历
178     InOder(t);
179     for(int i=1;i<=NUM;i++)
180         cout<<ret[i]<<" "; 
181     cout<<'
';
182 
183     // cout<<"high"<<getHeight(t)<<endl; 
184     cout<<t -> val<<endl;
185     int y = find_deep(t, 4, 1);
186     // int y = find(t, 5, 1);
187     cout<<y<<endl;
188     
189     return 0;
190 }

View Code

2019-02-20

08:32:26