import java.util.Scanner;
class Tree{
private Integer data;
private String notes;
private Tree lchild;
private Tree rchild;
public Integer getData() {
return data;
}
public void setData(Integer data) {
this.data = data;
}
public Tree getLchild() {
return lchild;
}
public void setLchild(Tree lchild) {
this.lchild = lchild;
}
public Tree getRchild() {
return rchild;
}
public void setRchild(Tree rchild) {
this.rchild = rchild;
}
public String getNotes() {
return notes;
}
public void setNotes(String notes) {
this.notes = notes;
}
public Tree() {
super();
}
public Tree(Integer data) {
super();
this.data = data;
}
public void addNode(Tree tree){
if(tree.data < this.data){
if(this.lchild == null) {
this.lchild = tree;
}else{
this.lchild.addNode(tree);
}
}
else{
if(this.rchild == null) {
this.rchild=tree;
}else{
this.rchild.addNode(tree);
}
}
}
//后序
public void printTree(){
if(rchild!=null) this.rchild.printTree();
System.out.println(this.data);
if(lchild!=null) this.lchild.printTree();
}
public void addNodeNotes(Tree tree){
if(tree.data < this.data){
if(this.lchild == null) {
String notes = this.notes.replaceAll("[0-9]",".").replaceAll("-", ".")+"-"+tree.getData()+"-|";
tree.setNotes(notes);
this.lchild = tree;
}else{
this.lchild.addNodeNotes(tree);
}
}
else{
if(this.rchild == null){
String notes = this.notes.replaceAll("[0-9]",".").replaceAll("-", ".")+"-"+tree.getData()+"-|";
tree.setNotes(notes);
this.rchild=tree;
}else{
this.rchild.addNodeNotes(tree);
}
}
}
// flag 0:left 1:right
//连续两次left,right 连续两次0 or 1，则需要去掉一个"|"
public void addNodeNotes(Tree tree,int flag){
if(tree.data < this.data){
if(this.lchild == null) {
String notes = this.notes.replaceAll("[0-9]",".").replaceAll("-", ".")+"-"+tree.getData()+"-|";
if(flag == 0){
String s = this.notes.replaceAll("[0-9]",".").replaceAll("-", ".").substring(0,this.notes.length()-1);
int index = s.lastIndexOf("|");
notes = s.substring(0, index)+"."+s.substring(index+1, s.length())+"|-"+tree.getData()+"-|";
}
tree.setNotes(notes);
this.lchild = tree;
}else{
this.lchild.addNodeNotes(tree,0);
}
}
else{
if(this.rchild == null){
String notes = this.notes.replaceAll("[0-9]",".").replaceAll("-", ".")+"-"+tree.getData()+"-|";
if(flag == 1){
String s = this.notes.replaceAll("[0-9]",".").replaceAll("-", ".").substring(0,this.notes.length()-1);
int index = s.lastIndexOf("|");
notes = s.substring(0, index)+"."+s.substring(index+1, s.length())+"|-"+tree.getData()+"-|";
}
tree.setNotes(notes);
this.rchild=tree;
}else{
this.rchild.addNodeNotes(tree,1);
}
}
}
//带注释
//后序
public void printTreeNotes(){
if(rchild!=null){
this.rchild.printTreeNotes();
}
if(lchild == null && rchild == null) System.out.println(this.notes.substring(0, this.notes.length()-2));
else System.out.println(this.notes);
if(lchild!=null){
this.lchild.printTreeNotes();
}
}
}
public class Main {
public static void main(String[] args) {
int[] a = new int[100];
String[] ss = new String[100];
Scanner scan=new Scanner(System.in);
String s = scan.nextLine();
ss = s.split(" ");
for(int i=0;i<ss.length;i++)
a[i] = Integer.parseInt(ss[i]);
Tree root = new Tree(a[0]);
root.setNotes(root.getData()+"-|");
for(int i=1;i<ss.length;i++){
root.addNodeNotes(new Tree(a[i]),-1);
}
root.printTreeNotes();
}
}
代码
转载请注明原文地址: https://ju.6miu.com/read-36613.html
