二叉树的遍历-(递归法)和(非递归法)

硅谷探秘者 4204 0 0

整理 二叉树的遍历-(递归法)和(非递归法)-笔记

先序遍历、中序遍历、后续遍历、层级遍历。

1.节点信息:

package tree;
public class Node<E> {
	private E e;//数据域
	private Node<E> left;//左子树
	private Node<E> right;//右子树
	private boolean b =true;//标记是否遍历
	public Node(E e) {
		super();
		this.e = e;
	}
	public E getE() {
		return e;
	}
	public void setE(E e) {
		this.e = e;
	}
	public Node<E> getLeft() {
		return left;
	}
	public void setLeft(Node<E> left) {
		this.left = left;
	}
	public Node<E> getRight() {
		return right;
	}
	public void setRight(Node<E> right) {
		this.right = right;
	}
	public boolean getB() {
		return b;
	}
	public void setB(boolean b) {
		this.b = b;
	}
	
}


2.构造二叉树以及遍历操作:

package tree;
import java.util.Queue;
import java.util.Stack;
import java.util.concurrent.ConcurrentLinkedQueue;
/**
 * 二叉树的遍历
 * @author Administrator
 *
 */
public class Tree {
	private Node<Integer> head;
	public Tree(){
	}
	/**
	 * 添加节点
	 * @param e
	 * @return
	 */
	public boolean addNode(Integer e){
		if(head==null){//空树
			head=new Node<Integer>(e);
			return true;
		}else{//非空
			Node<Integer> n=head;
			do{
				Integer a=n.getE();
				if(e>=a){
					if(n.getRight()==null){
						Node<Integer> node=new Node<Integer>(e);
						n.setRight(node);
						return true;
					}else{
						n=n.getRight();
					}
				}else{
					if(n.getLeft()==null){
						Node<Integer> node=new Node<Integer>(e);
						n.setLeft(node);
						return true;
					}else{
						n=n.getLeft();
					}
				}
			}while(n!=null);
		}
		return false;
	}
	/**
	 * 先序遍历(递归法)
	 */
	public void preErgodic(){
		pre(head);
		System.out.println();
	}
	private void pre(Node<Integer> node){
		if(node==null){
			return;
		}
		System.out.print(node.getE()+"  ");
		pre(node.getLeft());
		pre(node.getRight());
	}
	
	/**
	 * 中序遍历(递归法)
	 */
	public void midErgodic(){
		mid(head);
		System.out.println();
	}
	private void mid(Node<Integer> node){
		if(node==null){
			return;
		}
		mid(node.getLeft());
		System.out.print(node.getE()+"  ");
		mid(node.getRight());
	}
	
	/**
	 * 后续遍历(递归法)
	 */
	public void subErgodic(){
		sub(head);
		System.out.println();
	}
	private void sub(Node<Integer> node){
		if(node==null){
			return;
		}
		sub(node.getLeft());
		sub(node.getRight());
		System.out.print(node.getE()+"  ");
	}
	
	/**
	 * 先序遍历(非递归,基于栈)
	 */
	public void _preErgodic(){
		if(head==null){
			return;
		}
		Stack<Node<Integer>> stack=new Stack<>();
		Node<Integer> node=head;
		stack.push(node);
		while(!stack.isEmpty()){
			Node<Integer> n=stack.pop();
			System.out.print(n.getE()+"  ");
			if(n.getRight()!=null){
				stack.push(n.getRight());
			}
			if(n.getLeft()!=null){
				stack.push(n.getLeft());
			}
		}
		System.out.println();
	}
	
	/**
	 * 中序遍历(非递归,基于栈)
	 */
	public void _midErgodic(){
		if(head==null){
			return;
		}
		Stack<Node<Integer>> stack=new Stack<>();
		Node<Integer> n=head;
		operation(n, stack);
		while(!stack.isEmpty()){
			n=stack.pop();
			System.out.print(n.getE()+"  ");
			if(n.getRight()!=null){
				operation(n.getRight(),stack);
			}
		}
		System.out.println();
	}
	private void operation(Node<Integer> n,Stack<Node<Integer>> s){
		s.push(n);
		while(n.getLeft()!=null){
			s.push(n.getLeft());
			n=n.getLeft();
		}
	}
	
	/**
	 * 后序遍历(非递归,基于栈)
	 */
	public void _subErgodic(){
		if(head==null){
			return;
		}
		Stack<Node<Integer>> stack=new Stack<>();
		Node<Integer> n=head;
		stack.push(n);
		boolean b=true;
		while(!stack.isEmpty()){
			n=stack.peek();
			if(n.getRight()!=null&&n.getRight().getB()){
				stack.push(n.getRight());
				b=false;
			}
			if(n.getLeft()!=null&&n.getLeft().getB()){
				stack.push(n.getLeft());
				b=false;
			}
			if(b){
				n=stack.pop();
				System.out.print(n.getE()+"  ");
				n.setB(false);
			}
			b=true;
		}
		System.out.println();
	}
	
	public void hieErgodic(){
		if(head==null){
			return;
		}
		Queue<Node<Integer>> q=new ConcurrentLinkedQueue<Node<Integer>>();
		Node<Integer> n=head;
		q.add(n);
		while(!q.isEmpty()){
			n=q.poll();
			System.out.print(n.getE()+"  ");
			if(n.getLeft()!=null){
				q.add(n.getLeft());
			}
			if(n.getRight()!=null){
				q.add(n.getRight());
			}
		}
	}
}


3.测试:

package tree;

public class TestMain {
	public static void main(String[] args) {
		Tree tree=new Tree();
		tree.addNode(10);
		tree.addNode(5);
		tree.addNode(20);
		tree.addNode(2);
		tree.addNode(4);
		tree.addNode(15);
		tree.addNode(25);
		tree.addNode(0);
		tree.addNode(1);
		tree.addNode(3);
		tree.addNode(12);
		tree.addNode(16);
		
		System.out.print("先序遍历(递    归):");
		tree.preErgodic();
		System.out.print("中序遍历(递    归):");
		tree.midErgodic();
		System.out.print("后序遍历(递    归):");
		tree.subErgodic();
		
		System.out.println();
		
		System.out.print("先序遍历(非递归):");
		tree._preErgodic();
		
		System.out.print("中序遍历(非递归):");
		tree._midErgodic();
		
		System.out.print("后序遍历(非递归):");
		tree._subErgodic();
		
		System.out.println();
		
		System.out.print("层级遍历:");
		tree.hieErgodic();
		
	}
}

image.png


猜你喜欢
official 205 leetcode第589题题目描述给定一个N,返回其节点值前序。例如,给定一个3:返回其前序:[1,3,5,6,2,4]。解题思路,深度优先搜索代码(java
数据结构与算法 514 思想该算使用实现,思路为:每次将待排序数组在中间位置分成左右两组,分别对左右两个数组进行并排序,条件是数组长度必须大于等于3,所以当数组中只有两个数据时候可以直接进行比较排
数据结构与算法 2951 题目:在一个有序数组中查找指定数,如果存在返回其数组下标,否则返回-1packagetest;/*** 分查找*@author硅谷探秘者(jia)*/publicclassTestMain2
数据结构与算法 4028 实现全排列算c++描述#includeiostreamusingnamespacestd;//交换voidexchange(int*a,inti,intj){if(i==j){return
数据结构与算法 7300 )java代码实现importjava.util.LinkedList;/***结点类*@author硅谷探秘者(jia)*/classNode{ publicintdata; publicNodele
official 243 径。说明:叶子节点是指没有子节点节点。示例:输入:1/\23\5输出:["1-2-5","1-3"]解释:所有根节点到叶子节点路径为:1-2-5,1-3解题思路得方式(深度优先搜索),
数据结构与算法 1356 ; publicNode(intvalue,Nodenext){ super(); this.value=value; this.next=next; }}算实现packageclub.test;/***
数据结构与算法 3623 实现合并两增链表-合并后保持增序列java描述数据结构:单链表算链表节点packageclub.test;/****链表节点*@authorjiajia
归档
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月  6
标签
算法基础 linux 前端 c++ 数据结构 框架 数据库 计算机基础 储备知识 java基础 ASM 其他 深入理解java虚拟机 nginx git 消息中间件 搜索 maven redis docker dubbo vue 导入导出 软件使用 idea插件 协议 无聊的知识 jenkins springboot mqtt协议
目录
祝愿神州十三飞行乘组平安归来