数据结构和算法-层次打印二叉树节点信息(以及树的层级遍历)

硅谷探秘者 7736 0 0
控制台打印效果
                    |                       
        /-----------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();
	}
}

 

猜你喜欢
数据结构与算法 4603 整理-(递归(非递归)-笔记先序、中序、后续。1.:packagetree;publicclassNodeE{ privateEe;//
数据结构与算法 5241 试题描述:思路:用组表示完全,用先序方式每一,用一个组储存每一,因为规模小于100000所用一个容量为17组即可。计完每一,再比较最小之最大
weblog 3884 什么是前驱后继?某前驱val值小于该val值并且值是最大那个。某后继val值大于该val值并且值是最小那个。下面给出一个
数据结构与算法 6856 题目:判断下方两棵右方是否为左方例1:||/-----------10(10)------\/-------10(10)------\||||/-------5(5
数据结构与算法 1057 prim(普里姆)求出。对于任何一个,理解实现只是一个方面,更重要是要明白它应用范围或应用场景,最小生成应用非常广泛,例如:假设要在n个城市之间建立通联络网,则连接n个
official 623 《计机组成原理》计机系统机系统概念,目前比较一致机系统如下图,其中左边是中各名字,右边是对应于不同某种编程语言表现形式。计机系统
official 498 leetcode第589题题目描述给定一个N,返回其前序。例如,给定一个3:返回其前序:[1,3,5,6,2,4]。解题思路递归,深度优先搜索代码(java
数据结构与算法 4353 堆排序(英语: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
标签
算法基础 linux 前端 c++ 数据结构 框架 数据库 计算机基础 储备知识 java基础 ASM 其他 深入理解java虚拟机 nginx git 消息中间件 搜索 maven redis docker dubbo vue 导入导出 软件使用 idea插件 协议 无聊的知识 jenkins springboot mqtt协议 keepalived minio mysql ensp 网络基础 xxl-job rabbitmq haproxy
目录
没有一个冬天不可逾越,没有一个春天不会来临。最慢的步伐不是跬步,而是徘徊,最快的脚步不是冲刺,而是坚持。