文档章节

数据结构与算法分析 二叉树的遍历

Wetry文川
 Wetry文川
发布于 2017/05/08 13:24
字数 1187
阅读 10
收藏 0

数据结构与算法分析 二叉树的遍历

树的三种遍历,递归+非递归。深度优先,广度优先遍历二叉树


树的遍历(先中后)

递归版本

package cn.ustb.树的遍历;
//递归遍历
public class MyBinaryTree {
	static class Node{
		Node left;
		Node right;
		private int val;
		public Node(int val) {
			super();
			this.val = val;
		}
	}
	
	/*
	 * 递归版本 
	 */
	//前序
	public static void preOrder(Node node){
		if(node == null)
			return;
		System.out.print(node.val);
		preOrder(node.left);
		preOrder(node.right);
	}
	//中序
	public static void inOrder(Node node){
		if(node == null)
			return;
		inOrder(node.left);
		System.out.print(node.val);
		inOrder(node.right);
	}
	//后序
	public static void postOrder(Node node){
		if(node == null)
			return;
		postOrder(node.left);
		postOrder(node.right);
		System.out.print(node.val);
	}
	
	public static void main(String[] args) {
		/*
		 *       4
		 *     /   \
		 *    2     7
		 *   / \   / \
		 *  1   3 6   9
		 * 
		 */
		Node n1 = new Node(4);
		Node n2 = new Node(2);
		Node n3 = new Node(7);
		Node n4 = new Node(1);
		Node n5 = new Node(3);
		Node n6 = new Node(6);
		Node n7 = new Node(9);
		n1.left = n2;
		n1.right = n3;
		n2.left = n4;
		n2.right = n5;
		n3.left = n6;
		n3.right = n7;
		
		preOrder(n1);//4213769
		System.out.println();
		inOrder(n1);//1234679
		System.out.println();
		postOrder(n1);//1326974
	}
}

非递归版本

MyStack的数组实现

stack:数组实现,链表实现,Linkedlist实现 queue:数组实现,循环数组实现,链表实现,Linkedlist实现 更多关于queue和stack的实现见于:http://www.cnblogs.com/CherishFX/p/4608880.html

package cn.ustb.树的遍历;

import java.util.Arrays;

public class MyStack<T> {
	
	private T[] nodes;
	volatile int size = 0;
	private static final int PRIMARY_CAPACITY = 10;
	
	
	public MyStack() {
		super();
		this.nodes = (T[]) new Object[PRIMARY_CAPACITY];
		this.size = 0;
	}

	public void push(T t){
		ensureCapacity();
		nodes[size++] = t;
	}
	
	public T pop(){
		if(empty())
			throw new RuntimeException("空!");
		T temp = nodes[--size];
		nodes[size] = null;
		return temp;
	}
	public T peek(){
		if(empty())
			throw new RuntimeException("空!");
		return nodes[size-1];
	}
	
	private void ensureCapacity(){
		if(size == nodes.length){
			nodes = Arrays.copyOf(nodes, size<<2);
		}
	}
	
	public int size(){
		return size;
	}
	public boolean empty(){
		return size()==0;
	}
}
非递归
package cn.ustb.树的遍历;



public class MyBinaryTree2 {
	static class Node{
		Node left;
		Node right;
		private int val;
		public Node(int val) {
			super();
			this.val = val;
		}
	}
	
	/*
	 * 非递归版本,利用栈数据结构
	 */
	//前序遍历
	public static void preOrder(Node node){
		if(node == null)return;
		MyStack<Node> stack = new MyStack<>();
		while(node!=null||!stack.empty()){
			while(node!=null){
				System.out.print(node.val);//push之前先遍历
				stack.push(node);
				node = node.left;
			}
			if(!stack.empty()){
				node = stack.pop();
				node = node.right;
			}
		}
	}
	
	//中序遍历
	public static void inOrder(Node node){
		if(node == null)return;
		
		MyStack<Node> stack = new MyStack<>();
		while(node!=null||!stack.empty()){
			while(node !=null){
				stack.push(node);
				node = node.left;
			}
			if(!stack.empty()){
				node = stack.pop();
				System.out.print(node.val);
				node = node.right;
			}
		}
	}
	//后序遍历
	public static void postOrder(Node node){
		if(node == null)return;
		MyStack<Node> stack = new MyStack<>();
		MyStack<Node> outputStack = new MyStack<>();//存储遍历顺序
		while(node!=null||!stack.empty()){
			while(node !=null){
				stack.push(node);
				outputStack.push(node);
				node = node.right;
			}
			if(!stack.empty()){
				node = stack.pop();
				node = node.left;
			}
		}
		while(!outputStack.empty())
			System.out.print(outputStack.pop().val);
	}
	//后序遍历方法2:
	public static void postOrder(Node node,String method2){
		if(node == null)return;
		MyStack<Node> stack = new MyStack<>();
		MyStack<Integer> stateStack = new MyStack<>();//存储对应位置node的输出状态
		while(node!=null||!stack.empty()){
			while(node !=null){
				stack.push(node);
				stateStack.push(0);//0代表默认不输出
				node = node.left;
			}
			while(!stack.empty()&&stateStack.peek()==1){//可以输出
				stateStack.pop();
				System.out.print(stack.pop().val);
			}
			if(!stack.empty()){//不可以输出 :node == null&&state == 0
				stateStack.pop();
				stateStack.push(1);
				node = stack.peek();
				node = node.right;
			}
		}
	}
	
	
	
	
	public static void main(String[] args) {
		/*
		 *       4
		 *     /   \
		 *    2     7
		 *   / \   / \
		 *  1   3 6   9
		 * 
		 */
		Node n1 = new Node(4);
		Node n2 = new Node(2);
		Node n3 = new Node(7);
		Node n4 = new Node(1);
		Node n5 = new Node(3);
		Node n6 = new Node(6);
		Node n7 = new Node(9);
		n1.left = n2;
		n1.right = n3;
		n2.left = n4;
		n2.right = n5;
		n3.left = n6;
		n3.right = n7;
		
		preOrder(n1);//4213769
		System.out.println();
		inOrder(n1);//1234679
		System.out.println();
		postOrder(n1);//1326974
		System.out.println();
		postOrder(n1,"");//1326974
	}
}

树的遍历(深度优先,广度优先)

深度优先+广度优先

package cn.ustb.树的遍历;


public class MyBinaryTree3 {
	static class Node{
		Node left;
		Node right;
		private int val;
		public Node(int val) {
			super();
			this.val = val;
		}
	}
	
	
	/*
	 * 深度优先
	 * 借助 栈  的数据结构实现
	 */
	public static void deptFirstOrder(Node node){
		if(node == null)return ;
		
		MyStack<Node> stack = new MyStack<>();
		stack.push(node);
		while(!stack.empty()){
			node = stack.pop();
			System.out.print(node.val);
			if(node.right!=null)
				stack.push(node.right);
			if(node.left!=null)
				stack.push(node.left);
		}
	}
	
	/*
	 * 广度优先
	 * 借助  队列  的数据结构实现
	 */
	public static void breadthFirstOrder(Node node){
		if(node == null)return;
		MyQueue<Node> queue = new MyQueue<>();//或者自己实现queue
		queue.offer(node);
		while(!queue.isEmpty()){
			node = queue.poll();
			System.out.print(node.val);
			if(node.left!=null)
				queue.offer(node.left);
			if(node.right!=null)
				queue.offer(node.right);
		}
	}
	
	
	
	public static void main(String[] args) {
		/*
		 *        4
		 *      /   \
		 *     2     7
		 *    / \   / \
		 *   1   3 6   9
		 *  / 
		 * 0
		 */
		Node n1 = new Node(4);
		Node n2 = new Node(2);
		Node n3 = new Node(7);
		Node n4 = new Node(1);
		Node n5 = new Node(3);
		Node n6 = new Node(6);
		Node n7 = new Node(9);
		Node n8 = new Node(0);
		n1.left = n2;
		n1.right = n3;
		n2.left = n4;
		n2.right = n5;
		n3.left = n6;
		n3.right = n7;
		n4.left = n8;
		
		deptFirstOrder(n1);//42103769
		System.out.println();
		breadthFirstOrder(n1);//42713690
		System.out.println();
		
	}
}
MyQueue的数组实现

个人理解:循环数组不存在扩容机制 Queue的其他实现见于:http://www.cnblogs.com/CherishFX/p/4608880.html

package cn.ustb.树的遍历;

import java.util.Arrays;

public class MyQueue<T> {
	private T[] nodes;
	
	private int start;
	private int end;
	
	private static final int PRIMARY_CAPACITY = 10;
	
	
	public MyQueue() {
		super();
		nodes = (T[]) new Object[PRIMARY_CAPACITY];
		start = end = 0;
	}
	public void offer(T t){
		ensureCapacity();
		nodes[end++] = t;
	}
	public T poll(){
		if(isEmpty())
			throw new RuntimeException("empty!");
		T temp = nodes[start];
		nodes[start++] = null;
		return temp;
	}
	public T peek(){
		if(isEmpty())
			throw new RuntimeException("empty!");
		return nodes[start];
	}
	
	private void ensureCapacity(){
		if(end == nodes.length){
			nodes = Arrays.copyOf(nodes, end<<2);//4倍扩容
		}
	}
	
	public int size(){
		return end-start;
	}
	public boolean isEmpty(){
		return size()==0;
	}
}

© 著作权归作者所有

上一篇: Redis学习(1)
下一篇: JDK1.8新特性
Wetry文川
粉丝 1
博文 11
码字总数 26464
作品 0
东城
私信 提问
别再翻了,面试二叉树看着 11 个就够了~

写在前边 数据结构与算法: 不知道你有没有这种困惑,虽然刷了很多算法题,当我去面试的时候,面试官让你手写一个算法,可能你对此算法很熟悉,知道实现思路,但是总是不知道该在什么地方写,...

一个不甘平凡的码农
09/09
0
0
数据结构分析之二叉树

概述 在分析树形结构之前,先看一下树形结构在整个数据结构中的位置 数据结构 当然,没有图,现在还没有足够的水平去分析图这种太复杂的数据结构,表数据结构包含线性表跟链表,也就是经常说...

wustor
2017/11/06
0
0
最全BAT算法面试100题:阿里、百度、腾讯、京东、美团、今日头条

第一:复杂度估算和排序算法(上) 1) 时间复杂度和空间复杂度 2)认识对数器 3)冒泡排序 4)选择排序 5)插入排序 6)如何分析递归过程的时间复杂度 7)归并排序 8)小和问题 第二:复杂度...

编程SHA
04/25
66
0
Java学习资料-Java常用算法-二叉树算法

二叉树算法的数据结构: 二叉树结点Node实现与c中的区别是,c中采用的是结构体,而java中是用类来实现,而在c++的教材中,类是一种自定义数据结构。 二叉树的leftchild和rightchild在c中是利...

晓阳
2015/01/28
714
0
最全BAT算法面试130题:阿里、百度、腾讯、京东、美团、今日头条

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/t4i2b10X4c22nF6A/article/details/86133621 【百度、阿里、腾讯、京东、美团、今日头条】等公司都会必考关于...

JAVA高级架构v
01/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

当阿里云工程师回到了家乡......

根据真实故事改编 略有浮夸 但重要的是 9月25日13:30-16:30 云栖大会「5G边缘计算专场」 一定要来哦 !!! 本文作者:樰篱 原文链接 本文为云栖社区原创内容,未经允许不得转载。...

Mr_zebra
1分钟前
0
0
文件操作工具类 FileUtils常用方法

文件操作工具类(FileUtils) 使用该工具类的前提是项目里导入commons-io 包 import org.apache.commons.io.FileUtils; List<String> lines=new ArrayList<String>(); lines.add("欢迎访问:......

AndLong
8分钟前
0
0
maven-shade-plugin

最近,用规则引擎(drools)的封装了一个jar包,给别人使用。用的是maven-assembly-plugin打的包,可以把多个jar包里的class 给打成一个jar,感觉还是满好用的,但是打包成功后,发现报空指针错...

internetafei
12分钟前
0
0
Cassandra repair 工具使用

前言 Cassandra是一款去中心化的分布式数据库。一份数据会分布在多个对等的节点上,即有多个副本。我们需要定期的对多个副本检查,看是否有不一致的情况。比如因为磁盘损坏,可能会导致副本丢...

阿里云官方博客
15分钟前
0
0
element-vue使用富文本编辑器【前端】

一、前言 1.富文本编辑器选择的为vue-quill-editor 官方地址:https://quilljs.com/docs/quickstart/ 2.安装 cnpm install vue-quill-editor cnpm install quill 3.在对应的页面引入,在com...

一代码农码一代
21分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部