- 浏览: 604251 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
对于一个n个节点的链式二叉树,有n+1个空指针域,如果把这些空指针域用来指向当前节点的前驱或者后继,叫做把二叉树线索化。线索化后的二叉树遍历比较方便,不需要递归,效率快。以下使用java实现二叉树的线索化(中序线索二叉树)
下载源码:
一、节点类 public class Node { private int data; private Node left; private boolean leftIsThread;//左孩子是否为线索 private Node right; private boolean rightIsThread;//右孩子是否为线索 public Node(int data){ this.data = data ; this.left = null ; this.leftIsThread = false ; this.right = null ; this.rightIsThread = false ; } public int getData() { return data; } public void setData(int data) { this.data = data; } public Node getLeft() { return left; } public void setLeft(Node left) { this.left = left; } public boolean isLeftIsThread() { return leftIsThread; } public void setLeftIsThread(boolean leftIsThread) { this.leftIsThread = leftIsThread; } public Node getRight() { return right; } public void setRight(Node right) { this.right = right; } public boolean isRightIsThread() { return rightIsThread; } public void setRightIsThread(boolean rightIsThread) { this.rightIsThread = rightIsThread; } } 二、二叉树线索化(中序) public class ThreadTree { private Node root;// 根节点 private int size;// 大小 private Node pre = null ;//线索化的时候保存前驱 public ThreadTree(){ this.root = null ; this.size = 0 ; this.pre = null ; } public ThreadTree(int[] data){ this.pre = null ; this.size = data.length ; this.root = createTree(data , 0) ;//创建二叉树 } /** * 创建二叉树 * @param data */ public Node createTree(int[] data , int index){ if(2*index+2 > data.length){ return null ; } Node node = new Node(data[index]) ; Node left = createTree(data , 2*index+1) ; Node right = createTree(data , 2*index+2) ; node.setLeft(left) ; node.setRight(right) ; return node ; } /** * 将以root为根节点的二叉树线索化,使之成为中序线索二叉树 * @param root */ public void inThread(Node root){ if(root != null){ inThread(root.getLeft()) ;//线索化左孩子 if(null == root.getLeft()){//左孩子为空 root.setLeftIsThread(true) ;//将左孩子设置为线索 root.setLeft(pre) ; } if(pre!=null&&null == pre.getRight()){//右孩子为空 pre.setRightIsThread(true) ; pre.setRight(root) ; } pre = root ; inThread(root.getRight()) ;//线索化右孩子 } } /** * 根据线索输出线索二叉树中中序遍历信息。根据线索中序遍历二叉树 * @param root */ public void inThreadList(Node root){ if(root != null){ while(root!=null && !root.isLeftIsThread()){//如果左孩子不是线索 root = root.getLeft() ;// } do{ System.out.print(root.getData() + ","); if(root.isRightIsThread()){//如果右孩子是线索 root = root.getRight() ; }else{//有右孩子 root = root.getRight() ; while(root!=null && !root.isLeftIsThread()){ root = root.getLeft() ; } } }while(root != null) ; } } /** * 先序遍历递归算法 * @param root */ public void preList(Node root){ if(root != null){ System.out.print(root.getData() + ","); preList(root.getLeft()) ; preList(root.getRight()) ; } } /** * 中序遍历 * @param root */ public void inList(Node root){ if(root != null){ inList(root.getLeft()) ; System.out.print(root.getData() + ","); inList(root.getRight()) ; } } public Node getRoot() { return root; } public void setRoot(Node root) { this.root = root; } public int getSize() { return size; } public void setSize(int size) { this.size = size; } } 三、测试: public class ThreadTreeTest { public static void main(String[] args) { int[] data = {1,2,3,4,5,6,7,8,9,10,0,0,0,0,0,0,0,0,0,0,0} ; ThreadTree tt = new ThreadTree(data) ;//创建普通二叉树 tt.inList(tt.getRoot()) ;//中序递归遍历二叉树 System.out.println(""); tt.inThread(tt.getRoot()) ;//采用中序遍历将二叉树线索化 tt.inThreadList(tt.getRoot()) ;//中序遍历线索化二叉树 } }
下载源码:
- ex.zip (1.8 KB)
- 下载次数: 1
发表评论
-
求二叉树上任意两个节点的最近公共父节点
2013-01-09 10:24 2404北大百练题2756: 如上图所示,由正整数1, 2 ... -
JAVA判断二叉树是否是二叉平衡树
2013-01-07 18:59 1988import java.util.*; ... -
大顶堆应用:POJ2010
2012-12-23 20:59 1912POJ2010题意: 奶牛学校招生,c头奶牛报名,要选 ... -
二维树状数组学习之二:练习POJ 1195
2012-12-12 21:40 1400接前文:二维树状数组学习之一:彻底理解http://128kj ... -
二维树状数组学习之一:彻底理解
2012-12-12 20:54 2472当要频繁的对数组元素进行修改,同时又要频繁的查询数组内 ... -
图的深搜+树状数组练习 POJ 3321(JAVA)
2012-12-11 11:13 1843关于树状数组:参看:http://128kj.iteye.co ... -
树状数组练习:POJ 3067
2012-12-09 17:10 1845关于树状数组,参看:http://128kj.iteye.co ... -
树状数组练习:POJ 2481(JAVA)
2012-12-08 18:11 1823关于树状数组,请参考:http://128kj.iteye.c ... -
初步了解树状数组
2012-12-07 14:18 1791一、树状数组是干什么的? 平常我们会遇到一些对数组进 ... -
线段树求逆序数(离散化)POJ 2299
2012-12-06 08:25 2122POJ2299题意: 给出长度为n的序列,每次只能交换 ... -
利用线段树求逆序数(JAVA)
2012-12-04 22:46 2597设A[1…n]是一个包含n个不同数的数组。如果在i< ... -
线段树入门学习(三)懒操作(兼解POJ1823) JAVA
2012-12-02 15:37 2139继续上文"线段树入门学习(二)" ht ... -
线段树入门学习(二)(兼解POJ3468) JAVA
2012-11-30 16:55 2561继续上文http://128kj.iteye. ... -
线段树入门学习(兼解HDU1754)
2012-11-30 11:24 2729先看网上的介绍: 线段树也叫区间树,顾名思义,线段树是 ... -
AVL树及JAVA实现
2012-11-26 16:34 2307一棵AVL树是其每个节点的左子树和右子树的高度最多差1的二 ... -
图解平衡二叉树
2012-11-26 11:34 2064形态匀称的二叉树 ... -
深度优先遍历字典树(统计单词出现的个数)
2012-11-23 22:18 2856例:给出一个字符文本,每行一个字符串,统计不同的字符串出现的百 ... -
学习使用字典树(JAVA)
2012-11-22 09:25 2148字典树 又称单词 ... -
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
2012-11-17 21:50 18735堆有最大堆和最小堆之分,最大堆就是每个节点的值都>= ... -
并查集入门精讲,实例2个(JAVA)
2012-10-30 14:47 4070一、什么是并查集 ...
相关推荐
"threadtree1"这个文件可能是实现二叉树线索化中序遍历的代码示例或者测试用例。在实际编程中,通常会包含一个二叉树节点的结构定义,以及线索化和中序遍历的函数。通过分析和运行这个文件,你可以更深入地理解线索...
二叉树的中序线索化是指将二叉树转换成线索二叉树的过程。线索二叉树是一种特殊的二叉树,它的每个节点都有一个指向其前驱节点的指针和一个指向其后继节点的指针。这种数据结构可以方便地实现二叉树的遍历。 在本文...
在实际应用中,为了在非递归情况下高效地进行中序遍历,引入了线索二叉树的概念,特别是中序线索化二叉树。 中序线索化二叉树是在二叉链表的基础上进行修改,使得在任何时刻,通过线索可以确定某个节点是前驱还是...
个人认为比较简洁 使用递归方式 创建使用扩展二叉树更加便捷 且有部分先序线索化代码 不够完善
先根顺序建立二叉树,并对其进行线索化,实现先序遍历和中序遍历
根据给定的文件信息,我们将深入探讨“将二叉树按中序线索化的算法”这一主题,特别是通过C语言实现该算法的过程。 ### 一、什么是中序线索化 在理解具体的实现之前,我们首先需要了解什么是“中序线索化”。在...
中序线索二叉树(建立二叉树,线索化,输出二叉树)
2. **中序线索二叉树**:基于二叉树的中序遍历来构建。 3. **后序线索二叉树**:基于二叉树的后序遍历来构建。 4. **层序线索二叉树**:基于二叉树的层序遍历来构建。 #### 五、中序线索链表实例 以中序线索二叉树...
### C语言实现二叉树线索化 #### 一、引言 在计算机科学领域中,二叉树是一种常见的数据结构,被广泛应用于多种算法和数据处理任务中。线索化二叉树是二叉树的一种变形,它通过对空指针进行重新利用来提高二叉树的...
通过前序序列创建线索二叉树 1:中序遍历 2:查找节点前驱后继 3:插入节点 4:删除节点 0:退出
对先序线索二叉树、中序线索二叉树和后序线索二叉树进行了 C 语言实现,主要包括线索二叉树的建立和遍历过程。
实验3-二叉树线索化 本实验报告的主要内容是介绍二叉树的结构和一些基本操作,如二叉树的中序线索化、先序线索化、后序线索化,以及二叉树的建立、中序遍历线索化二叉树、先序遍历线索化二叉树等等。下面是实验报告...
右键单击绘制根节点,左键绘制其它节点,节点之间连线产生关系,节点可以拖动。只能应用二叉树,没有封闭纠错。点击confirm,用绿线标出线索。
总之,中序线索化是二叉树非递归遍历的一种优化手段,通过在二叉链表节点中添加线索指针,使得在中序遍历过程中可以方便地进行双向移动。掌握这一技巧对于理解和处理复杂的数据结构问题至关重要。
中序线索化二叉树的非递归算法 中序线索化二叉树的非递归算法是指对二叉树进行中序遍历,并将其转换为线索化二叉树的算法。这里,我们将详细介绍该算法的实现过程和相关知识点。 算法思想 中序线索化二叉树的非...
3. **进行中序线索化**:利用递归的方式进行中序遍历,并在此过程中完成线索化工作。 - 在遍历到某个节点时,检查其左子节点是否为空。如果为空,则将左子节点指针改为指向当前节点的前驱节点,并将`LTag`设置为`...
中序线索化是将非线索二叉树转化为线索二叉树的过程,目的是为了方便在不使用栈的情况下进行中序遍历,特别是在查找某个结点的前驱和后继时。本程序专注于中序线索化二叉树并确定指定结点的前驱。 中序线索化的基本...
Java实现二叉树中序线索化 左键画节点 右键画跟 点可以拖动 两个节点可以连线 确认进行线索化 并画出线索
1. **threadedInOrder(node)**:用于中序线索化。这个方法会遍历给定的节点,并根据中序遍历的规则设置线索。 2. **threadedPreOrder(node)**:用于前序线索化。这个方法会遍历给定的节点,并根据前序遍历的规则...