二叉树是一种基本的数据结构，它要么为空，要么由根节点，左子树和右子树组成，同时左子树和右子树也分别是二叉树。
当一颗二叉树高度为m-1m−1时，则共有mm层。除mm层外，其他各层的结点数都达到最大，且结点节点都在第mm层时，这就是一个满二叉树。
现在，需要你用程序来绘制一棵二叉树，它由一颗满二叉树去掉若干结点而成。对于一颗满二叉树，我们需要按照以下要求绘制：
1、结点用小写字母“o”表示，对于一个父亲结点，用“/”连接左子树，同样用“\”连接右子树。
2、定义[i,j[i,j]为位于第ii行第jj列的某个字符。若[i,j][i,j]为“/”，那么[i-1,j+1][i−1,j+1]与[i+1,j-1][i+1,j−1]要么为“o”，要么为“/”。若[i,j][i,j]为“\”，那么[i-1,j-1][i−1,j−1]与[i+1,j+1][i+1,j+1]要么为“o”，要么为“\”。同样，若[i,j][i,j]为第1-m1−m层的某个节点（即“o”），那么[i+1,j-1][i+1,j−1]为“/”，[i+1,j+1][i+1,j+1]为“\”。
3、对于第mm层节点也就是叶子结点，若两个属于同一个父亲，那么它们之间由3由3个空格隔开，若两个结点相邻但不属于同一个父亲，那么它们之间由11个空格隔开。第mm层左数第11个节点之前没有空格。
最后需要在一颗绘制好的满二叉树上删除nn个结点（包括它的左右子树，以及与父亲的连接），原有的字符用空格替换（ASCII 32，请注意空格与ASCII 0的区别(若用记事本打开看起来是一样的，但是评测时会被算作错误答案！)）。
输入格式第11行包含22个正整数mm和nn，为需要绘制的二叉树层数已经从mm层满二叉树中删除的结点数。 按照题目要求绘制的二叉树。 欢迎分享，转载请注明来源：内存溢出
接下来nn行，每行两个正整数，表示第ii层第jj个结点需要被删除（1
java代码实现
输入：
4 0
输出：
o
/ \
/ \
/ \
/ \
/ \
o o
/ \ / \
/ \ / \
o o o o
/ \ / \ / \ / \
o o o o o o o o
输入:
4 3
3 2
4 1
3 4
输出：
o
/ \
/ \
/ \
/ \
/ \
o o
/ /
/ /
o o
\ / \
o o o
package com.piziwang.luogu.p1185;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
/**
* @author PIZIWANG
* @date 2022-05-14 16:53
**/
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
String s0 = input.nextLine();
String[] s2 = s0.split(" ");
// 树的高度
int m = Integer.parseInt(s2[0]);
// 待删除的节点数目
int n= Integer.parseInt(s2[1]);
int maxHeight = (int) (Math.pow(2,m-2)*3);
int maxWidth = (int) (Math.pow(2,m-1)*3-1);
// 初始化为空格
char[][] treeGraph = new char[maxHeight+1][maxWidth+1];
for (int i = 0; i < treeGraph.length; i++) {
for (int j = 0; j < treeGraph[i].length; j++) {
treeGraph[i][j]=32;
}
}
/**
* 生成满二叉树
*/
// 1. 插入元素(判断是否到达边界)
insert(treeGraph,0,maxWidth/2+1,m);
char[][] spared = new char[maxHeight + 1][maxWidth + 1];
for (int i = 0; i < spared.length; i++) {
for (int j = 0; j < spared[i].length; j++) {
spared[i][j] = treeGraph[i][j];
}
}
// 2.删除节点
for (int i = 0; i < n; i++) {
String s = input.nextLine();
String[] s1 = s.split(" ");
// 第i层
int xi = Integer.parseInt(s1[0]);
int xj = Integer.parseInt(s1[1]);
remove(treeGraph,xi,xj,m,spared);
}
printTreeGraph(treeGraph);
}
/**
* 删除
* 删除xi 层 xj个节点
* @param treeGraph 树图
* @param xi 习
* @param xj xj
* @param m 树的总高度，虽然可以算出来，但是传入还是更方便
*/
private static void remove(char[][] treeGraph, int xi, int xj,int m,char[][] spared) {
// 1.根据层数和第几个节点，获取到待删除节点在数组中的具体位置
Map<String,Integer> absoluteIndex = absoluteIndex(spared,m,xi,xj);
int x = absoluteIndex.get("x");
int y= absoluteIndex.get("y");
removeTreeGraph(treeGraph,x,y,m-xi+1);
}
/**
* 删除数组中的值，
* @param treeGraph 树图
* @param x 待删除根节点x坐标
* @param y 待删除根节点y坐标
* @param height 树的高度
*/
private static void removeTreeGraph(char[][] treeGraph, int x, int y, int height) {
if (height==0) {
return;
}
// 1.删除当前节点
treeGraph[x][y] = 32;
// 2.删除指向父亲节点的斜线
int flx = x-1,fly = y-1;
int frx = x-1,fry = y+1;
while (fly>0 && treeGraph[flx][fly]=='\') {
treeGraph[flx--][fly--] = 32;
if(flx<0 || fly<1){
break;
}
}
while (fry<treeGraph[0].length-1 && treeGraph[frx][fry]=='/') {
treeGraph[frx--][fry++] = 32;
if(frx<0 || fry>(fry*2-1)){
break;
}
}
int removeLength = (int) (Math.pow(2,height-2)*3)/2-1;
if (height == 2) {
removeLength = 1;
}
int lx =x+1,ly=y-1;
int rx = x+1,ry =y+1;
while (removeLength > 0) {
removeLeftLine(treeGraph,lx++,ly--);
removeRightLine(treeGraph,rx++,ry++);
removeLength--;
}
height--;
removeTreeGraph(treeGraph,lx,ly,height);
removeTreeGraph(treeGraph,rx,ry,height);
}
private static void removeRightLine(char[][] treeGraph, int i, int j) {
treeGraph[i][j]=32;
}
private static void removeLeftLine(char[][] treeGraph, int i, int j) {
treeGraph[i][j]=32;
}
/**
* 计算某层，第几个节点在数组中的绝对索引
* @param m 树的高度
* @param xi 层
* @param xj 第几个
* @return {@link Map}<{@link String}, {@link Integer}>
*/
private static Map<String, Integer> absoluteIndex(char[][] spared,int m, int xi, int xj) {
Map<String, Integer> result = new HashMap<>();
// x位置，3*2^(m-2)- 3*2^(m-xi-1)
int x = (int) (3*Math.pow(2,m-2))-(int) (3*Math.pow(2,m-xi-1));
result.put("x",x);
// y位置，
int count =0;
int i =0;
for (; i < spared[x].length; i++) {
if (spared[x][i] == 'o') {
count++;
}
if (count == xj) {
break;
}
}
result.put("y",i);
return result;
}
/**
* 插入
* 插入节点
* @param treeGraph 树图
* @param x 在x行
* @param y 在y列
* @param m 层
*/
private static void insert(char[][] treeGraph, int x, int y,int m) {
if (m==0) {
return;
}
treeGraph[x][y] = 'o';
int printLength = (int) (Math.pow(2,m-2)*3)/2-1;
if (m == 2) {
printLength = 1;
}
int lx =x+1,ly=y-1;
int rx = x+1,ry =y+1;
while (printLength > 0) {
insertLeftLine(treeGraph,lx++,ly--);
insertRightLine(treeGraph,rx++,ry++);
printLength--;
}
m--;
insert(treeGraph,lx,ly,m);
insert(treeGraph,rx,ry,m);
}
/**
* 插入右侧斜线
* @param h h
* @param w w
*/
private static void insertRightLine(char[][] treeGraph,int h, int w) {
treeGraph[h][w]='\';
}
/**
* 插入左侧斜线
* @param h h
* @param w w
*/
private static void insertLeftLine(char[][] treeGraph,int h, int w) {
treeGraph[h][w]='/';
}
private static void printTreeGraph(char[][] treeGraph) {
for (int i = 0; i < treeGraph.length-1; i++) {
for (int j = 1; j < treeGraph[i].length; j++) {
System.out.print(treeGraph[i][j]);
}
System.out.println();
}
}
}
微信扫一扫
支付宝扫一扫
评论列表（0条）