二叉树前、中、后线索化及对应前、中、后序线索化遍历_前序线索化图解过程-程序员宅基地

技术标签: leecode  算法  java  二叉树  数据结构  

二叉树前中后线索化及对应前中后序线索化遍历(图解)

二叉树线索化都是套路,会一种另外两种只是稍微修改一下代码

值得一提的是后序线索化输出,逆序思维将后序线索化看成前序,采用"前序线索化输出"代码更加简洁,也更好理解

线索化基本介绍
在这里插入图片描述
二叉树线索化百度百科介绍:
https://baike.baidu.com/item/%E7%BA%BF%E7%B4%A2%E4%BA%8C%E5%8F%89%E6%A0%91/10810037?fr=aladdin

以下面二叉树为例
在这里插入图片描述
前序化流程图解
在这里插入图片描述

创建节点对象 (使用数组更方便)

class TreeNode1 {
    

	private int no;

	private TreeNode1 left;
	private TreeNode1 right;

	/*
	 * 说明: 1.如果 letfType 或 rightType 为 0 表示 左子树或右子树 2.如果 letfType 或 rightType 为 1 表示
	 * 前驱或后驱节点
	 */
	private int leftType;
	private int rightType;

	public TreeNode1(int no) {
    
		this.no = no;
	}
	
	//getter/setter ...

	@Override
	public String toString() {
    
		return "TreeNode1 [no=" + no + "]";
	}

}

创建一个类实现线索化

class TreeManger1 {
    

	private TreeNode1 root;

	public void setRoot(TreeNode1 root) {
    
		this.root = root;
	}
	...线索化
}

## 中序最简单也最容易理解 所以先看一下中序线索化

// 为了实现 线索化,需要创建一个变量,指定向前节点的前驱节点
	// 在递归进行索化时,infixPre 总是保留前一个节点
	TreeNode1 infixPre = null;

	public void infixThreadTreeNode() {
    
		this.infixThreadTreeNode(root);
	}
	
	// 中序线索化
	public void infixThreadTreeNode(TreeNode1 node) {
    
		// 如果 node == null 则不能索化
		if (node == null) {
    
			return;
		}

		// 1.线索化左子树
		infixThreadTreeNode(node.getLeft());

		// 2.线索化当前节点
		if (node.getLeft() == null) {
    
			// 让当前节点的左指针指向前驱节点
			node.setLeft(infixPre);
			// 修改当前节点的左指针的类型,指向前驱节点
			node.setLeftType(1);

		}
		// 处理后继节点         
		if (infixPre != null && infixPre.getRight() == null) {
    
			// 让前驱节点的有指针指向当前节点
			infixPre.setRight(node);
			// 修改前驱节点的右指针类型
			infixPre.setRightType(1);
		}

		// !!!!!没处理一个节点后让当前节点指向下一个节点的前驱节点
		infixPre = node;

		// 3.线索化右子树
		infixThreadTreeNode(node.getRight());

	}

中序线索化遍历

// 中序线索化输出
	public void infixThreadTreeNodeOrde() {
    
		// 定义一个节点存储当前遍历的节点 从 root 开始
		TreeNode1 node = root;	
		while (node != null) {
    
			// 循环找到 leftType = 1 的节点
			while (node.getLeftType() == 0) {
    
				node = node.getLeft();
			}
			// 打印当前节点
			System.out.println(node);

			// 如果当前节点的右指针指向的是后继节点,就一直输出
			while (node.getRightType() == 1) {
    
				// 获取当前节点的后继节点
				node = node.getRight();
				System.out.println(node);
			}
			// 替换这个遍历的节点
			node = node.getRight();

		}

	}

前序线索化

TreeNode1 prePre = null;

	// 前序线索化
	public void preThread(TreeNode1 node) {
    

		if (node == null) {
    
			return;
		}

		// 线索化当前节点
		if (node.getLeft() == null) {
    

			node.setLeft(prePre);
			node.setLeftType(1);

		}

		if (prePre != null && prePre.getRight() == null) {
    

			prePre.setRight(node);
			prePre.setRightType(1);
		}

		prePre = node;

		// 线索化左子树
		if (node.getLeftType() != 1) {
    

			preThread(node.getLeft());
		}

		// 线索化右子树
		if (node.getRightType() != 1) {
    

			preThread(node.getRight());
		}

	}

前序线索化输出

// 前序索化输出
	public void preThreadOrder() {
    

		TreeNode1 node = root;

		while (node != null) {
    

			while (node.getLeftType() != 1) {
    
				System.out.println(node);
				node = node.getLeft();
			}

			System.out.println(node);

			node = node.getRight();

		}

	}

后序线索化


	TreeNode1 postPre = null;

	// 后序序线索化
	public void postThread(TreeNode1 node) {
    

		if (node == null) {
    
			return;
		}

		// 线索化左子树
		postThread(node.getLeft());

		// 线索化右子树
		postThread(node.getRight());

		// 线索化当前节点
		if (node.getLeft() == null) {
    

			node.setLeft(postPre);
			node.setLeftType(1);

		}

		if (postPre != null && postPre.getRight() == null) {
    
			postPre.setRight(node);
			postPre.setRightType(1);
		}

		postPre = node;

	}

后序线索化输出

/*
	 * 后线索化输出
	 * 
	 * 逆序前线索化,将其压入栈中,最后依次弹出即可
	 * 
	 */
	public void postThreadOrde() {
    

		Stack<TreeNode1> stack = new Stack<TreeNode1>();

		TreeNode1 node = root;

		while (node != null) {
    

			while (node.getRightType() != 1) {
    

				stack.push(node);

				node = node.getRight();

			}

			stack.push(node);

			node = node.getLeft();

		}

		while (!stack.isEmpty()) {
    
			System.out.println(stack.pop());
		}

	}

一张图对比一下 其实都是套路
在这里插入图片描述
全部代码

package com.kc.c09_tree._02threadbinarytree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class T {
    
	public static void main(String[] args) {
    

		TreeNode1 n11 = new TreeNode1(11);

		TreeNode1 n21 = new TreeNode1(21);
		TreeNode1 n31 = new TreeNode1(31);

		TreeNode1 n14 = new TreeNode1(14);
		TreeNode1 n15 = new TreeNode1(15);
		TreeNode1 n61 = new TreeNode1(61);
		TreeNode1 n71 = new TreeNode1(71);

		TreeNode1 n81 = new TreeNode1(81);
		TreeNode1 n91 = new TreeNode1(91);

		n11.setLeft(n21);
		n11.setRight(n31);

		n21.setLeft(n14);
		n21.setRight(n15);
		n31.setLeft(n61);
		n31.setRight(n71);

		n14.setLeft(n81);
		n14.setRight(n91);

		TreeManger1 tm = new TreeManger1();
		tm.setRoot(n11);

//		tm.preThread(n11);
//		tm.infixThreadTreeNode(n11);
		tm.postThread(n11);
//		

		// 检验
		TreeNode1 left11 = n11.getLeft();
		TreeNode1 right11 = n11.getRight();
		System.out.println("no11 : left = " + left11 + ",right = " + right11);

		TreeNode1 left21 = n21.getLeft();
		TreeNode1 right21 = n21.getRight();
		System.out.println("no21 : left = " + left21 + ",right = " + right21);

		TreeNode1 left31 = n31.getLeft();
		TreeNode1 right31 = n31.getRight();
		System.out.println("no31 : left = " + left31 + ",right = " + right31);

		TreeNode1 left14 = n14.getLeft();
		TreeNode1 right14 = n14.getRight();
		System.out.println("no14 : left = " + left14 + ",right = " + right14);

		TreeNode1 left81 = n81.getLeft();
		TreeNode1 right81 = n81.getRight();
		System.out.println("no81 : left = " + left81 + ",right = " + right81);

		TreeNode1 left91 = n91.getLeft();
		TreeNode1 right91 = n91.getRight();
		System.out.println("no91 : left = " + left91 + ",right = " + right91);

		TreeNode1 left15 = n15.getLeft();
		TreeNode1 right15 = n15.getRight();
		System.out.println("no15 : left = " + left15 + ",right = " + right15);

		TreeNode1 left61 = n61.getLeft();
		TreeNode1 right61 = n61.getRight();
		System.out.println("no61 : left = " + left61 + ",right = " + right61);

		TreeNode1 left71 = n71.getLeft();
		TreeNode1 right71 = n71.getRight();
		System.out.println("no71 : left = " + left71 + ",right = " + right71);

//		tm.preThreadOrder();
//		tm.infixThreadTreeNodeOrde();
		tm.postThreadOrde();

	}
}

class TreeManger1 {
    

	private TreeNode1 root;

	public void setRoot(TreeNode1 root) {
    
		this.root = root;
	}

	/********* 线索化二叉树 *********/

	/******************************************/

	TreeNode1 prePre = null;

	// 前序线索化
	public void preThread(TreeNode1 node) {
    

		if (node == null) {
    
			return;
		}

		// 线索化当前节点
		if (node.getLeft() == null) {
    

			node.setLeft(prePre);
			node.setLeftType(1);

		}

		if (prePre != null && prePre.getRight() == null) {
    

			prePre.setRight(node);
			prePre.setRightType(1);
		}

		prePre = node;

		// 线索化左子树
		if (node.getLeftType() != 1) {
    

			preThread(node.getLeft());
		}

		// 线索化右子树
		if (node.getRightType() != 1) {
    

			preThread(node.getRight());
		}

	}

	// 前序索化输出
	public void preThreadOrder() {
    

		TreeNode1 node = root;

		while (node != null) {
    

			while (node.getLeftType() != 1) {
    
				System.out.println(node);
				node = node.getLeft();
			}

			System.out.println(node);

			node = node.getRight();

		}

	}

	/******************************************/

	TreeNode1 postPre = null;

	// 后序序线索化
	public void postThread(TreeNode1 node) {
    

		if (node == null) {
    
			return;
		}

		// 线索化左子树
		postThread(node.getLeft());

		// 线索化右子树
		postThread(node.getRight());

		// 线索化当前节点
		if (node.getLeft() == null) {
    

			node.setLeft(postPre);
			node.setLeftType(1);

		}

		if (postPre != null && postPre.getRight() == null) {
    
			postPre.setRight(node);
			postPre.setRightType(1);
		}

		postPre = node;

	}

	/*
	 * 后线索化输出
	 * 
	 * 逆序前线索化,将其压入栈中,最后依次弹出即可
	 * 
	 */
	public void postThreadOrde() {
    

		Stack<TreeNode1> stack = new Stack<TreeNode1>();

		TreeNode1 node = root;

		while (node != null) {
    

			while (node.getRightType() != 1) {
    

				stack.push(node);

				node = node.getRight();

			}

			stack.push(node);

			node = node.getLeft();

		}

		while (!stack.isEmpty()) {
    
			System.out.println(stack.pop());
		}

	}

	/*************************************/

	// 为了实现 线索化,需要创建一个变量,指定向前节点的前驱节点
	// 在递归进行索化时,infixPre 总是保留前一个节点
	TreeNode1 infixPre = null;

	public void infixThreadTreeNode() {
    
		this.infixThreadTreeNode(root);
	}

	// 中序线索化
	public void infixThreadTreeNode(TreeNode1 node) {
    
		// 如果 node == null 则不能索化
		if (node == null) {
    
			return;
		}

		// 1.线索化左子树
		infixThreadTreeNode(node.getLeft());

		// 2.线索化当前节点
		if (node.getLeft() == null) {
    
			// 让当前节点的左指针指向前驱节点
			node.setLeft(infixPre);
			// 修改当前节点的左指针的类型,指向前驱节点
			node.setLeftType(1);

		}
		// 处理后继节点
		if (infixPre != null && infixPre.getRight() == null) {
    
			// 让前驱节点的有指针指向当前节点
			infixPre.setRight(node);
			// 修改前驱节点的右指针类型
			infixPre.setRightType(1);
		}

		// !!!!!没处理一个节点后让当前节点指向下一个节点的前驱节点
		infixPre = node;

		// 3.线索化右子树
		infixThreadTreeNode(node.getRight());

	}

	// 中序线索化输出
	public void infixThreadTreeNodeOrde() {
    
		// 定义一个节点存储当前遍历的节点 从 root 开始
		TreeNode1 node = root;

		while (node != null) {
    
			// 循环找到 leftType = 1 的节点
			while (node.getLeftType() == 0) {
    
				node = node.getLeft();
			}
			// 打印当前节点
			System.out.println(node);

			// 如果当前节点的右指针指向的是后继节点,就一直输出
			while (node.getRightType() == 1) {
    
				// 获取当前节点的后继节点
				node = node.getRight();
				System.out.println(node);
			}
			// 替换这个遍历的节点
			node = node.getRight();

		}

	}

}

class TreeNode1 {
    

	private int no;

	private TreeNode1 left;
	private TreeNode1 right;

	private int leftType;
	private int rightType;

	public int getLeftType() {
    
		return leftType;
	}

	public void setLeftType(int leftType) {
    
		this.leftType = leftType;
	}

	public int getRightType() {
    
		return rightType;
	}

	public void setRightType(int rightType) {
    
		this.rightType = rightType;
	}

	public TreeNode1(int no) {
    
		this.no = no;
	}

	public int getNo() {
    
		return no;
	}

	public void setNo(int no) {
    
		this.no = no;
	}

	public TreeNode1 getLeft() {
    
		return left;
	}

	public void setLeft(TreeNode1 left) {
    
		this.left = left;
	}

	public TreeNode1 getRight() {
    
		return right;
	}

	public void setRight(TreeNode1 right) {
    
		this.right = right;
	}

	@Override
	public String toString() {
    
		return "TreeNode1 [no=" + no + "]";
	}

}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_44760145/article/details/106065880

智能推荐

java后台利用POI将excle转换成html实现在线预览_javaexcel转html-程序员宅基地

文章浏览阅读6.6k次。 前一阵项目有office系列文件在线预览需求,所以查询了一些资料,参考其他一些博客,实现了通过POI将excle转化为html,后来需求被砍掉,没有继续深入研究,这里将查询到的一些资料做一个记录. 首先实现office系列文件在线预览主要查到有如下解决方案:1.flash 的flexpaper 将文档转换为swf格式,然后使用flash在网页中浏览 2.使用开源的软件openoffice+p..._javaexcel转html

html热点 位置不低,热点图 页面缩放不改变位置-程序员宅基地

文章浏览阅读281次。文章时间:2019年5月29日 23:42:02解决问题:热点图 随着页面的缩放比例而不改变其所在的位置推荐画图工具:Adobe Dreamweaver CC头部我们需要3个东西,请直接复制即可直接复制这段代码然后用设计模式画图就行了。任意地方加这段js代码。$("img[usemap]").each(function () {var img = $(this);var newImg = new ..._h5地图热点放大缩小如何不跑偏

maven打包报错_error locating assembly descriptor: src/main/assem-程序员宅基地

文章浏览阅读2k次。项目场景:maven打包报错:Failed to execute goal org.apache.maven.plugins:maven-assembly-plugin:2.4:single (make-assembly) on project hiveudf2: Error reading assemblies: Error locating assembly descriptor: assembly.xml问题描述:项目上执行目标org.apache.maven.plugins:maven-as_error locating assembly descriptor: src/main/assembly/assembly.xml

Chrome开发者工具使用教程-主要功能简介(一)_谷歌后台调测执行sql-程序员宅基地

文章浏览阅读1.4k次。Chrome开发者工具是谷歌浏览器自带的一款开发者工具,它可以给开发者带来很大的便利。主要作用有:快速定位问题查看站点页面加载信息在线页面样式调整前端代码调试前端日志分析浏览器存储查看在线性能分析等…1.如何调出开发者工具按F12键CTRL+SHIFT+I 或在页面上右键,点击“检查”按钮,如下图:2.面板功能简介元素(Elements):用于查看或修改H..._谷歌后台调测执行sql

C语言文件指针偏移的使用(点阵字库txt文件取字)_c语言指针偏移-程序员宅基地

文章浏览阅读3.5k次。从点阵字库txt取字,指向文件内容位置的文件指针是唯一的,无法多个副本分别定位(无法一个文件使用多个指针),这与传统上内存中的指针不同。_c语言指针偏移

Oracle Partition 分区详细总结_partition by range-程序员宅基地

文章浏览阅读651次。此文从以下几个方面来整理关于分区表的概念及操作: 1.表空间及分区表的概念 2.表分区的具体作用 3.表分区的优缺点 4.表分区的几种类型及操作方法 5.对表分区的维护性操作.(1.) 表空间及分区表的概念表空间: 是一个或多个数据文件的集合,所有的数据对象都存放在指定的表_partition by range

随便推点

transform,translation和animation-程序员宅基地

文章浏览阅读587次。css3在原来的基础上增加了变形和动画相关的属性,动画三兄弟:transform、transition和animation,通过使用这三个属性可以达到很炫酷的效果。需要注意的是这三个属性都是css3新增的属性,各大浏览器支持方面还不是特别好,使用时要特别注意浏览器的兼容性。Transform浏览器支持情况:Internet Explorer 10、Firefox、Opera_translation和animation

[redis] SpringBoot整合SpringDataRedis配置文件_spring boot 192.168.110.130-程序员宅基地

文章浏览阅读1.7k次。SpringBoot整合SpringDataRedis pom文件添加依赖 全局配置文件 配置类pom文件添加依赖<dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-data-redis<..._spring boot 192.168.110.130

JAVA安卓4.4.4,Could not find support-v4.jar (com.android.support:support-v4:24.0.0)-程序员宅基地

文章浏览阅读318次。Error:A problem occurred configuring project ':app'.Could not find support-v4.jar (com.android.support:support-v4:24.0.0). Searched in the following locations: https://jcenter.bintray.com/com/android/..._supportv4.jar

OpenLayers Map理解-程序员宅基地

文章浏览阅读165次。OpenLayers Map理解 1,视口坐标的原点在左上角,水平向右为x轴正向,垂直向下为y 轴正向;2,地图坐标原点为初始图层的中心点,水平向右为x轴正向,垂直向上为y轴正向;3,视口中心点永远与地图中心点重合,不一定与瓦片中心点重合;4,拖动图层的逻辑描述:地..._openlayer this.map.getsize()

vue运用 vue-qr 生成二维码-程序员宅基地

文章浏览阅读5.4k次,点赞4次,收藏18次。第一步,先安装 vue-qr 插件npm install vue-qr --save第二步,在想要生成vueQr 的Vue页面引入组件import vueQr from 'vue-qr'第三步,在components中引入VueQr组件components: { VueQr }最后就在在html上引用<VueQr :margin='8' :size='280' :whiteMargin="true" :logoMargin="3" :logoCornerRadius_vue-qr

各品牌电脑PE中找不到硬盘的解决方法/bios设置_联想ideapad710s进pe找不到硬盘-程序员宅基地

文章浏览阅读1.3w次。  大部分小伙伴遇到系统坏了之后,都会自己用U盘装系统,但是在u盘装系统过程中却容易遇到问题,特别是PE中找不到硬盘的情况,大家遇到这种情况该怎么解决呢,所以今天跟着快启动小编的脚步一起来详细了解一二吧。  首先,我们要了解硬盘的两种模式,一种是比较新的SATA模式,现在的新电脑大多采用此模式,而另一种则是比较旧的PATA模式,而这两种模式都需要配置驱动程序,但它们的驱动程序是不一样的。  然而,..._联想ideapad710s进pe找不到硬盘

推荐文章

热门文章

相关标签