- 浏览: 584900 次
- 来自: ...
文章分类
最新评论
-
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 2330北大百练题2756: 如上图所示,由正整数1, 2 ... -
JAVA判断二叉树是否是二叉平衡树
2013-01-07 18:59 1949import java.util.*; ... -
大顶堆应用:POJ2010
2012-12-23 20:59 1831POJ2010题意: 奶牛学校招生,c头奶牛报名,要选 ... -
二维树状数组学习之二:练习POJ 1195
2012-12-12 21:40 1357接前文:二维树状数组学习之一:彻底理解http://128kj ... -
二维树状数组学习之一:彻底理解
2012-12-12 20:54 2421当要频繁的对数组元素进行修改,同时又要频繁的查询数组内 ... -
图的深搜+树状数组练习 POJ 3321(JAVA)
2012-12-11 11:13 1770关于树状数组:参看:http://128kj.iteye.co ... -
树状数组练习:POJ 3067
2012-12-09 17:10 1677关于树状数组,参看:http://128kj.iteye.co ... -
树状数组练习:POJ 2481(JAVA)
2012-12-08 18:11 1756关于树状数组,请参考:http://128kj.iteye.c ... -
初步了解树状数组
2012-12-07 14:18 1705一、树状数组是干什么的? 平常我们会遇到一些对数组进 ... -
线段树求逆序数(离散化)POJ 2299
2012-12-06 08:25 2025POJ2299题意: 给出长度为n的序列,每次只能交换 ... -
利用线段树求逆序数(JAVA)
2012-12-04 22:46 2488设A[1…n]是一个包含n个不同数的数组。如果在i< ... -
线段树入门学习(三)懒操作(兼解POJ1823) JAVA
2012-12-02 15:37 2036继续上文"线段树入门学习(二)" ht ... -
线段树入门学习(二)(兼解POJ3468) JAVA
2012-11-30 16:55 2501继续上文http://128kj.iteye. ... -
线段树入门学习(兼解HDU1754)
2012-11-30 11:24 2606先看网上的介绍: 线段树也叫区间树,顾名思义,线段树是 ... -
AVL树及JAVA实现
2012-11-26 16:34 2222一棵AVL树是其每个节点的左子树和右子树的高度最多差1的二 ... -
图解平衡二叉树
2012-11-26 11:34 2014形态匀称的二叉树 ... -
深度优先遍历字典树(统计单词出现的个数)
2012-11-23 22:18 2789例:给出一个字符文本,每行一个字符串,统计不同的字符串出现的百 ... -
学习使用字典树(JAVA)
2012-11-22 09:25 2063字典树 又称单词 ... -
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
2012-11-17 21:50 18578堆有最大堆和最小堆之分,最大堆就是每个节点的值都>= ... -
并查集入门精讲,实例2个(JAVA)
2012-10-30 14:47 3989一、什么是并查集 ...
相关推荐
二叉树 中序遍历 线索化 先序输入 树形输出
二叉树的中序线索化及中序遍历,代码可运行
个人认为比较简洁 使用递归方式 创建使用扩展二叉树更加便捷 且有部分先序线索化代码 不够完善
先根顺序建立二叉树,并对其进行线索化,实现先序遍历和中序遍历
中序线索二叉树(建立二叉树,线索化,输出二叉树)
//运行环境:MS Visual C++ 6.0
中序线索化的C程序 中序线索化的C程序 中序线索化的C程序 中序线索化的C程序 中序线索化的C程序
通过前序序列创建线索二叉树 1:中序遍历 2:查找节点前驱后继 3:插入节点 4:删除节点 0:退出
对先序线索二叉树、中序线索二叉树和后序线索二叉树进行了 C 语言实现,主要包括线索二叉树的建立和遍历过程。
二叉树的先序线索化 中序线索化 后序线索化 二叉树先序线索遍历 中序线索遍历 后序线索遍历
本节主要讲述二叉树的线索链表存储结构和相关操作
右键单击绘制根节点,左键绘制其它节点,节点之间连线产生关系,节点可以拖动。只能应用二叉树,没有封闭纠错。点击confirm,用绿线标出线索。
目录链式存储线索二叉树中序线索二叉树中序线索化实现实现的代码过程中序线索二叉树的遍历遍历代码中序线索二叉树可运行代码先序线索二叉树先序线索化实现先序线索二叉树的遍历遍历代码先序线索二叉树可运行代码后序...
Java实现二叉树中序线索化 左键画节点 右键画跟 点可以拖动 两个节点可以连线 确认进行线索化 并画出线索
java实现的中序与前序线索二叉树代码,能直接运行,能实现二叉树的中序线索化和前序线索化
本程序对二叉树进行中序线索化,并求指定结点的前驱
中序线索化的二叉树 能够对二叉树先线索化然后再中序排列 并且输出
二叉树的中序线索化,包括进行线索化和遍历线索二叉树。
线索二叉树 先序构建 中序线索化 中序遍历