数据结构和算法-层次打印二叉树节点信息(以及树的层级遍历)
控制台打印效果
|
/-----------10(10)------\
| |
/-------5(5)\ /-----15(15)\
| | | |
3(3)\ 7(7)\ 12(12) 18(18)
| |
4(4) 8(8)
java代码实现
import java.util.LinkedList;
/**
* 二叉树结点类
* @author 硅谷探秘者(jia)
*/
class Node{
public int data;
public Node left;
public Node right;
public Node(Node left,Node right,int data) {
this.left=left;
this.right=right;
this.data=data;
}
public Node(int data) {
this.data=data;
}
}
public class A1 {
static Node root;
public static void main(String[] args) {
/**
* 构造二叉树
*/
Node n4=new Node(4);
Node n8=new Node(8);
Node n12=new Node(12);
Node n18=new Node(18);
Node n3=new Node(null,n4,3);
Node n7=new Node(null,n8,7);
Node n5=new Node(n3,n7,5);
Node n15=new Node(n12,n18,15);
Node n10=new Node(n5,n15,10);
root=n10;
/**
* 层次遍历
*/
cengDis(root);
}
/**
* 层级遍历(用jdk提供的LinkedList充当栈或队列)
* @param p
*/
public static void cengDis(Node p) {
LinkedList<Node> stack=new LinkedList<>();
LinkedList<Node> dui=new LinkedList<>();
PrintfTree tree = null;
dui.add(p);
while(true){
Node f=null;
if(dui.size()>0) {
f=dui.removeFirst();
}
if(f==null) {
Node d=null;
if(stack.size()>0) {
d=stack.removeFirst();
}
if(d==null) {
tree.show();
return ;
}else {
dui.addLast(d);
while(true) {
d=null;
if(stack.size()>0) {
d=stack.removeFirst();
}
if(d==null) {
break;
}else {
dui.addLast(d);
}
}
}
}else {
if(tree==null) {
tree=new PrintfTree(""+f.data+"("+f.data+")");
}else {
tree.add(new PrintfTree(""+f.data+"("+f.data+")"));
}
Node left=f.left;
if(left!=null) {
stack.addLast(left);
}
Node right=f.right;
if(right!=null) {
stack.addLast(right);
}
}
}
}
}
/**
* 打印二叉树工具类
* @author 硅谷探秘者(jia)
*/
class PrintfTree{
private String v;
private PrintfTree l;
private PrintfTree r;
public PrintfTree(String v){
this.v = v;
}
public void add(PrintfTree the){
if(new Integer(the.v.substring(0,the.v.lastIndexOf("("))) < new Integer(v.substring(0,v.lastIndexOf("(")))){
if(l==null) l = the;
else l.add(the);
}
else{
if(r==null) r = the;
else r.add(the);
}
}
public int getHeight(){
int h = 2;
int hl = l==null? 0 : l.getHeight();
int hr = r==null? 0 : r.getHeight();
return h + Math.max(hl,hr);
}
public int getWidth(){
int w = (""+v).length();
if(l!=null) w += l.getWidth();
if(r!=null) w += r.getWidth();
return w;
}
public void show(){
char[][] buf = new char[getHeight()][getWidth()];
printInBuf(buf, 0, 0);
showBuf(buf);
}
private void showBuf(char[][] x){
for(int i=0; i<x.length; i++){
for(int j=0; j<x[i].length; j++)
System.out.print(x[i][j]==0? ' ':x[i][j]);
System.out.println();
}
}
private void printInBuf(char[][] buf, int x, int y){
String sv = "" + v;
int p1 = l==null? x : l.getRootPos(x);
int p2 = getRootPos(x);
int p3 = r==null? p2 : r.getRootPos(p2+sv.length());
buf[y][p2] = '|';
for(int i=p1; i<=p3; i++) buf[y+1][i]='-';
for(int i=0; i<sv.length(); i++) buf[y+1][p2+i]=sv.charAt(i);
if(p1<p2) buf[y+1][p1] = '/';
if(p3>p2) buf[y+1][p3] = '\\';
if(l!=null) l.printInBuf(buf,x,y+2);
if(r!=null) r.printInBuf(buf,p2+sv.length(),y+2);
}
private int getRootPos(int x){
return l==null? x : x + l.getWidth();
}
}
评论区
请写下您的评论...
猜你喜欢
blog
二叉树的遍历-(递归法)和(非递归法)
数据结构与算法
5054
整理二叉树的遍历-(递归法)和(非递归法)-笔记先序遍历、中序遍历、后续遍历、层级遍历。1.节点信息:packagetree;publicclassNodeE{ privateEe;//数据域
blog
数据结构-算法-完全二叉树的权值
数据结构与算法
5660
试题描述:思路:用数组表示完全二叉树,用先序遍历的方式遍历每一层的节点,用一个数组储存每一层的和,因为数据规模小于100000所以用一个容量为17的数组即可。计算完每一层的和,再比较层数最小之和最大
weblog
5360
什么是二叉树的前驱节点和后继节点?某节点的前驱节点的val值小于该节点的val值并且值是最大的那个节点。某节点的后继节点的val值大于该节点的val值并且值是最小的那个节点。下面给出一个二叉树节点类
数据结构与算法
7311
题目:判断下方两棵二叉树右方的二叉树是否为左方二叉树的子树例1:||/-----------10(10)------\/-------10(10)------\||||/-------5(5
数据结构与算法
1506
prim(普里姆)算法求出。对于任何一个数据结构或算法,理解和实现只是一个方面,更重要的是要明白它的应用范围或应用场景,最小生成树算法的应用非常广泛,例如:假设要在n个城市之间建立通信联络网,则连接n个
ofc
计算机系统的层次结构
official
1186
《计算机组成原理》计算机系统的层次结构计算机系统层次结构的概念,目前比较一致的计算机系统的层次结构如下图,其中左边是层次结构中各层次的名字,右边是对应于不同层的某种编程语言表现形式。计算机系统的层次
ofc
N叉树的前序遍历
official
832
leetcode第589题题目描述给定一个N叉树,返回其节点值的前序遍历。例如,给定一个3叉树:返回其前序遍历:[1,3,5,6,2,4]。解题思路递归遍历,深度优先搜索代码(java
blog
数据结构+算法-堆排序
数据结构与算法
4695
堆排序(英语:Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。以最小堆为例下沉操
最新发表
归档
2018-11
12
2018-12
33
2019-01
28
2019-02
28
2019-03
32
2019-04
27
2019-05
33
2019-06
6
2019-07
12
2019-08
12
2019-09
21
2019-10
8
2019-11
15
2019-12
25
2020-01
9
2020-02
5
2020-03
16
2020-04
4
2020-06
1
2020-07
7
2020-08
13
2020-09
9
2020-10
5
2020-12
3
2021-01
1
2021-02
5
2021-03
7
2021-04
4
2021-05
4
2021-06
1
2021-07
7
2021-08
2
2021-09
8
2021-10
9
2021-11
16
2021-12
14
2022-01
7
2022-05
1
2022-08
3
2022-09
2
2022-10
2
2022-12
5
2023-01
3
2023-02
1
2023-03
4
2023-04
2
2023-06
3
2023-07
4
2023-08
1
2023-10
1
2024-02
1
2024-03
1
2024-04
1
标签
算法基础
linux
前端
c++
数据结构
框架
数据库
计算机基础
储备知识
java基础
ASM
其他
深入理解java虚拟机
nginx
git
消息中间件
搜索
maven
redis
docker
dubbo
vue
导入导出
软件使用
idea插件
协议
无聊的知识
jenkins
springboot
mqtt协议
keepalived
minio
mysql
ensp
网络基础
xxl-job
rabbitmq
haproxy
srs
音视频
webrtc
javascript
目录
没有一个冬天不可逾越,没有一个春天不会来临。最慢的步伐不是跬步,而是徘徊,最快的脚步不是冲刺,而是坚持。