二叉树的线索化及遍历

2024-01-28 18:48
文章标签 二叉树 遍历 线索 化及

本文主要是介绍二叉树的线索化及遍历，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

一、需求

二、前序线索化

2.1  前序线索化图解

2.2  前序线索化代码实现

2.3  前序线索化的遍历

 三、中序线索化

3.1  中序线索化图解

3.2  中序线索化代码实现

3.3  中序线索化的遍历

四、后序线索化

4.1  后序线索化图解

4.2  后序线索化代码实现

五、完整代码

一、需求

/** 需求:实现线索化二叉树* 分析:*    A:因为结点的指针可能指向树或者前驱或者后继，为了分辨，需要增加结点的属性;*      a:当leftType=0时表示指向左子树，leftType=1表示指向前驱;*      b:当rightType=0表示指向右子树，rightType=1表示指向后继;*    B:进行前序线索化时，遵循的原则是'根左右'，要解决的问题是结点的前驱和后继问题,*      关于中序、后序线索化同理;*/

二、前序线索化

2.1  前序线索化图解

       蓝线表示树枝，红线表示线索。 

2.2  前序线索化代码实现

/*** 这个方法是二叉树的前序线索化*/public void preThreadedNodes(HeroNode node) {if(node == null) {return;}//线索化当前结点if(node.getLeft() == null) {node.setLeft(pre);node.setLeftType(1);}//第二个pre敲成了node，找了两天。。。if(pre != null && pre.getRight() == null) {pre.setRight(node);pre.setRightType(1);}pre = node;//线索化左子树if(node.getLeftType() == 0) {preThreadedNodes(node.getLeft());}//线索化右子树if(node.getRightType() == 0) {preThreadedNodes(node.getRight());}}

2.3  前序线索化的遍历

/*** 前序遍历线索二叉树的方法*/public void preThreadedList() {HeroNode node = root;while(node != null) {while(node.getLeftType() == 0) {System.out.println(node);node = node.getLeft();}System.out.println(node);node = node.getRight();}}

 三、中序线索化

3.1  中序线索化图解

3.2  中序线索化代码实现

/*** 这个方法是二叉树的中序线索化* @param node 当前需要线索化的结点*/public void infixThreadedNodes(HeroNode node) {if(node == null) {return;}infixThreadedNodes(node.getLeft());if(node.getLeft() == null) {node.setLeft(pre);node.setLeftType(1);}if(pre != null && pre.getRight() == null) {pre.setRight(node);pre.setRightType(1);}//每处理一个结点，让当前结点是下一个结点的前驱结点pre = node;infixThreadedNodes(node.getRight());}

3.3  中序线索化的遍历

/*** 中序遍历线索二叉树的方法*/public void infixThreadedList() {//定义临时变量HeroNode 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();}}

四、后序线索化

4.1  后序线索化图解

4.2  后序线索化代码实现

/*** 这个方法是二叉树的后序线索化* @param node*/public void postThreadedNodes(HeroNode node) {if(node == null) {return;}postThreadedNodes(node.getLeft());postThreadedNodes(node.getRight());if(node.getLeft() == null) {node.setLeft(pre);node.setLeftType(1);}if(pre != null && pre.getRight() == null) {pre.setRight(node);pre.setRightType(1);}pre = node;}

五、完整代码

package tree.find;/** 需求:实现线索化二叉树* 分析:*    A:因为结点的指针可能指向树或者前驱或者后继，为了分辨，需要增加结点的属性;*      a:当leftType=0时表示指向左子树，leftType=1表示指向前驱;*      b:当rightType=0表示指向右子树，rightType=1表示指向后继;*/
public class ThreadedBinaryTreeDemo {public static void main(String[] args) {// 定义结点HeroNode root = new HeroNode(1, "tom");HeroNode node2 = new HeroNode(3, "jack");HeroNode node3 = new HeroNode(6, "simth");HeroNode node4 = new HeroNode(8, "mary");HeroNode node5 = new HeroNode(10, "king");HeroNode node6 = new HeroNode(14, "dim");// 手动创建root.setLeft(node2);root.setRight(node3);node2.setLeft(node4);node2.setRight(node5);node3.setLeft(node6);// 创建线索二叉树对象ThreadedBinaryTree tb = new ThreadedBinaryTree();tb.setRoot(root);/** //测试前序线索化 tb.preThreadedNodes(); System.out.println("前序遍历结果为:");* tb.preThreadedList();*/// 测试中序线索化tb.infixThreadedNodes();System.out.println("中序遍历结果为:");tb.infixThreadedList();}}// 定义ThreadedBinaryTree二叉树
class ThreadedBinaryTree {private HeroNode root;// 增加前驱结点属性private HeroNode pre = null;public void setRoot(HeroNode root) {this.root = root;}// 重载线索化方法public void preThreadedNodes() {this.preThreadedNodes(root);}public void infixThreadedNodes() {this.infixThreadedNodes(root);}/*** 这个方法是二叉树的前序线索化*/public void preThreadedNodes(HeroNode node) {if (node == null) {return;}// 线索化当前结点if (node.getLeft() == null) {node.setLeft(pre);node.setLeftType(1);}// 第二个pre敲成了node，找了两天。。。if (pre != null && pre.getRight() == null) {pre.setRight(node);pre.setRightType(1);}pre = node;// 线索化左子树if (node.getLeftType() == 0) {preThreadedNodes(node.getLeft());}// 线索化右子树if (node.getRightType() == 0) {preThreadedNodes(node.getRight());}}/*** 这个方法是二叉树的中序线索化* * @param node*            当前需要线索化的结点*/public void infixThreadedNodes(HeroNode node) {if (node == null) {return;}infixThreadedNodes(node.getLeft());if (node.getLeft() == null) {node.setLeft(pre);node.setLeftType(1);}if (pre != null && pre.getRight() == null) {pre.setRight(node);pre.setRightType(1);}// 每处理一个结点，让当前结点是下一个结点的前驱结点pre = node;infixThreadedNodes(node.getRight());}/*** 这个方法是二叉树的后序线索化* * @param node*/public void postThreadedNodes(HeroNode node) {if (node == null) {return;}postThreadedNodes(node.getLeft());postThreadedNodes(node.getRight());if (node.getLeft() == null) {node.setLeft(pre);node.setLeftType(1);}if (pre != null && pre.getRight() == null) {pre.setRight(node);pre.setRightType(1);}pre = node;}/*** 前序遍历线索二叉树的方法*/public void preThreadedList() {HeroNode node = root;while (node != null) {while (node.getLeftType() == 0) {System.out.println(node);node = node.getLeft();}System.out.println(node);node = node.getRight();}}/*** 中序遍历线索二叉树的方法*/public void infixThreadedList() {// 定义临时变量HeroNode 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();}}/*** 后序遍历线索二叉树的方法*/public void postThreadedList() {HeroNode node = root;while (node.getLeftType() == 0) {node = node.getLeft();}System.out.println(node);}
}// 创建HeroNode结点
class HeroNode {private int id;private String name;private HeroNode left;private HeroNode right;// 增加结点属性private int leftType;private int rightType;// 构造方法public HeroNode(int id, String name) {this.id = id;this.name = name;}// 自动生成get,set方法public int getId() {return id;}public void setId(int id) {this.id = id;}public String getName() {return name;}public void setName(String name) {this.name = name;}public HeroNode getLeft() {return left;}public void setLeft(HeroNode left) {this.left = left;}public HeroNode getRight() {return right;}public void setRight(HeroNode right) {this.right = right;}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;}// toString方法@Overridepublic String toString() {return "HeroNode [id=" + id + ", name=" + name + "]";}
}

 

这篇关于二叉树的线索化及遍历的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/654471。

相关文章

leetcode105 从前序与中序遍历序列构造二叉树

leetcode105 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如，给出 前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树： 3/ \9 20/ \15 7   class Solution {public TreeNode buildTree(int[] pr
阅读更多...
PHP实现二叉树遍历(非递归方式，栈模拟实现)

PHP实现二叉树遍历(非递归方式，栈模拟实现)

二叉树定义是这样的：一棵非空的二叉树由根结点及左、右子树这三个基本部分组成，根据节点的访问位置不同有三种遍历方式： ① NLR：前序遍历(PreorderTraversal亦称(先序遍历)) ——访问结点的操作发生在遍历其左右子树之前。 ② LNR：中序遍历(InorderTraversal) ——访问结点的操作发生在遍历其左右子树之中(间)。 ③ LRN：后序遍历(PostorderT
阅读更多...
react笔记 8-17 属性绑定 class绑定 引入图片 循环遍历

react笔记 8-17 属性绑定 class绑定 引入图片 循环遍历

1、绑定属性 constructor(){super()this.state={name:"张三",title:'我是一个title'}}render() {return (<div><div>aaaaaaa{this.state.name}<div title={this.state.title}>我是一个title</div></div></div>)} 绑定属性直接使用花括号{}   注
阅读更多...
在二叉树中找到两个节点的最近公共祖先（基于Java）

在二叉树中找到两个节点的最近公共祖先（基于Java）

如题  题解 public int lowestCommonAncestor(TreeNode root, int o1, int o2) {//记录遍历到的每个节点的父节点。Map<Integer, Integer> parent = new HashMap<>();Queue<TreeNode> queue = new LinkedList<>();parent.put(roo
阅读更多...
数据结构--二叉树（C语言实现，超详细！！！）

数据结构--二叉树（C语言实现，超详细！！！）

文章目录 二叉树的概念代码实现二叉树的定义创建一棵树并初始化组装二叉树前序遍历中序遍历后序遍历计算树的结点个数求二叉树第K层的结点个数求二叉树高度查找X所在的结点查找指定节点在不在完整代码 二叉树的概念 二叉树（Binary Tree）是数据结构中一种非常重要的树形结构，它的特点是每个节点最多有两个子节点，通常称为左子节点和右子节点。这种结构使得二叉树在数据存储和查找等方面具
阅读更多...
hashmap的存值，各种遍历方法

hashmap的存值，各种遍历方法

package com.jefflee;import java.util.HashMap;import java.util.Iterator;import java.util.Map;public class HashmapTest {// 遍历Hashmap的四种方法public static void main(String[] args) {//hashmap可以存一个null，把
阅读更多...
Knight Moves -uva 简单的BFS遍历

Knight Moves -uva 简单的BFS遍历

昨天刚学了BFS的遍历，在uva上找了个题敲了出来，感觉还不错，最近敲代码挺有手感的，希望这种状态保持下去 #include<iostream>#include<stdio.h>#include<stdlib.h>#include<string.h>#define MAX_SIZE 10 + 5#define LEN 100 + 10using namespace std;in
阅读更多...
笔试强训,[NOIP2002普及组]过河卒牛客.游游的水果大礼包牛客.买卖股票的最好时机（二)二叉树非递归前序遍历

笔试强训,[NOIP2002普及组]过河卒牛客.游游的水果大礼包牛客.买卖股票的最好时机（二)二叉树非递归前序遍历

目录 [NOIP2002普及组]过河卒 牛客.游游的水果大礼包 牛客.买卖股票的最好时机（二) 二叉树非递归前序遍历 [NOIP2002普及组]过河卒 题里面给的提示很有用，那个马的关系，后面就注意，dp需要作为long的类型。 import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息publ
阅读更多...
222.完全二叉树的节点个数

222.完全二叉树的节点个数

（写给未来遗忘的自己） 题目： 代码： class Solution {public:int countNodes(TreeNode* root) {queue<TreeNode*>node_que;if(root==nullptr) return 0;node_que.push(root);int result;while(!node_que.empty()){int layer_s
阅读更多...
代码随想录 -- 二叉树 -- 平衡二叉树

代码随想录 -- 二叉树 -- 平衡二叉树

110. 平衡二叉树 - 力扣（LeetCode） 思路：仍然是递归调用 1. 定义一个递归函数 count 用来计算二叉树的层数 2. isBalanced 函数：如果传入根节点为空返回真；如果根节点 | 左子树的层数 - 右子树的层数 | 大于1，返回假；最后返回根节点左子树、右子树是否是平衡二叉树。 class Solution(object):def count(self,root
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2