思享工具箱

Java 实现二叉树的构建以及3种遍历方法

摘要：
转载自http://ocaicai.iteye.com/blog/1047397在我大二的第二学期，我在学习数据结构时使用C引入了二叉树。然而，当我热衷于java时，我并没有太关注二叉树。但我仍然对二叉树的构造和遍历深感担忧。今天我又遇到了这个问题，所以我花了整个下午的时间编写代码并生成介绍想法的文档！目录：1.将数组的值分配给二进制树2.特定代码1.树构建方法2.特定代码Java代码packagetree；我

转载自http://ocaicai.iteye.com/blog/1047397

大二下学期学习数据结构的时候用C介绍过二叉树，但是当时热衷于java就没有怎么鸟二叉树，但是对二叉树的构建及遍历一直耿耿于怀，今天又遇见这个问题了，所以花了一下午的时间来编写代码以及介绍思路的文档生成！ 


目录： 

1.把一个数组的值赋值给一颗二叉树 

2.具体代码 


1.树的构建方法 

Java 实现二叉树的构建以及3种遍历方法第1张

2.具体代码 

Java代码  收藏代码
  1. package tree;  
  2.   
  3. import java.util.LinkedList;  
  4. import java.util.List;  
  5.   
  6. /** 
  7.  * 功能：把一个数组的值存入二叉树中，然后进行3种方式的遍历 
  8.  *  
  9.  * 参考资料0:数据结构(C语言版)严蔚敏 
  10.  *  
  11.  * 参考资料1：http://zhidao.baidu.com/question/81938912.html 
  12.  *  
  13.  * 参考资料2：http://cslibrary.stanford.edu/110/BinaryTrees.html#java 
  14.  *  
  15.  * @author ocaicai@yeah.net @date: 2011-5-17 
  16.  *  
  17.  */  
  18. public class BinTreeTraverse2 {  
  19.   
  20.     private int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };  
  21.     private static List<Node> nodeList = null;  
  22.   
  23.     /** 
  24.      * 内部类：节点 
  25.      *  
  26.      * @author ocaicai@yeah.net @date: 2011-5-17 
  27.      *  
  28.      */  
  29.     private static class Node {  
  30.         Node leftChild;  
  31.         Node rightChild;  
  32.         int data;  
  33.   
  34.         Node(int newData) {  
  35.             leftChild = null;  
  36.             rightChild = null;  
  37.             data = newData;  
  38.         }  
  39.     }  
  40.   
  41.     public void createBinTree() {  
  42.         nodeList = new LinkedList<Node>();  
  43.         // 将一个数组的值依次转换为Node节点  
  44.         for (int nodeIndex = 0; nodeIndex < array.length; nodeIndex++) {  
  45.             nodeList.add(new Node(array[nodeIndex]));  
  46.         }  
  47.         // 对前lastParentIndex-1个父节点按照父节点与孩子节点的数字关系建立二叉树  
  48.         for (int parentIndex = 0; parentIndex < array.length / 2 - 1; parentIndex++) {  
  49.             // 左孩子  
  50.             nodeList.get(parentIndex).leftChild = nodeList  
  51.                     .get(parentIndex * 2 + 1);  
  52.             // 右孩子  
  53.             nodeList.get(parentIndex).rightChild = nodeList  
  54.                     .get(parentIndex * 2 + 2);  
  55.         }  
  56.         // 最后一个父节点:因为最后一个父节点可能没有右孩子，所以单独拿出来处理  
  57.         int lastParentIndex = array.length / 2 - 1;  
  58.         // 左孩子  
  59.         nodeList.get(lastParentIndex).leftChild = nodeList  
  60.                 .get(lastParentIndex * 2 + 1);  
  61.         // 右孩子,如果数组的长度为奇数才建立右孩子  
  62.         if (array.length % 2 == 1) {  
  63.             nodeList.get(lastParentIndex).rightChild = nodeList  
  64.                     .get(lastParentIndex * 2 + 2);  
  65.         }  
  66.     }  
  67.   
  68.     /** 
  69.      * 先序遍历 
  70.      *  
  71.      * 这三种不同的遍历结构都是一样的，只是先后顺序不一样而已 
  72.      *  
  73.      * @param node 
  74.      *            遍历的节点 
  75.      */  
  76.     public static void preOrderTraverse(Node node) {  
  77.         if (node == null)  
  78.             return;  
  79.         System.out.print(node.data + " ");  
  80.         preOrderTraverse(node.leftChild);  
  81.         preOrderTraverse(node.rightChild);  
  82.     }  
  83.   
  84.     /** 
  85.      * 中序遍历 
  86.      *  
  87.      * 这三种不同的遍历结构都是一样的，只是先后顺序不一样而已 
  88.      *  
  89.      * @param node 
  90.      *            遍历的节点 
  91.      */  
  92.     public static void inOrderTraverse(Node node) {  
  93.         if (node == null)  
  94.             return;  
  95.         inOrderTraverse(node.leftChild);  
  96.         System.out.print(node.data + " ");  
  97.         inOrderTraverse(node.rightChild);  
  98.     }  
  99.   
  100.     /** 
  101.      * 后序遍历 
  102.      *  
  103.      * 这三种不同的遍历结构都是一样的，只是先后顺序不一样而已 
  104.      *  
  105.      * @param node 
  106.      *            遍历的节点 
  107.      */  
  108.     public static void postOrderTraverse(Node node) {  
  109.         if (node == null)  
  110.             return;  
  111.         postOrderTraverse(node.leftChild);  
  112.         postOrderTraverse(node.rightChild);  
  113.         System.out.print(node.data + " ");  
  114.     }  
  115.   
  116.     public static void main(String[] args) {  
  117.         BinTreeTraverse2 binTree = new BinTreeTraverse2();  
  118.         binTree.createBinTree();  
  119.         // nodeList中第0个索引处的值即为根节点  
  120.         Node root = nodeList.get(0);  
  121.   
  122.         System.out.println("先序遍历：");  
  123.         preOrderTraverse(root);  
  124.         System.out.println();  
  125.   
  126.         System.out.println("中序遍历：");  
  127.         inOrderTraverse(root);  
  128.         System.out.println();  
  129.   
  130.         System.out.println("后序遍历：");  
  131.         postOrderTraverse(root);  
  132.     }  
  133.   
  134. }  



输出结果： 

Java代码  收藏代码
    1. 先序遍历：  
    2. 1 2 4 8 9 5 3 6 7   
    3. 中序遍历：  
    4. 8 4 9 2 5 1 6 3 7   
    5. 后序遍历：  
    6. 8 9 4 5 2 6 7 3 1   

标签：#中序遍历#先序遍历#后序遍历#二叉树遍历#遍历 | 浏览：129 | 发布日期：

免责声明：文章转载自《Java 实现二叉树的构建以及3种遍历方法》仅用于学习参考。如对内容有疑问，请及时联系本站处理。

上篇【数据分析&amp;amp;数据挖掘】非数值型数据的哑变量转化、连续型数据离散化——等宽分组&amp;amp;等频分组一梦江湖费六年——QQ群聊天分析下篇

宿迁高防，2C2G15M，22元/月；香港BGP，2C5G5M，25元/月 雨云优惠码：MjYwNzM=

相关文章

将excel中的数据转为json格式

---恢复内容开始--- 用来总结工作中碰导一些错误，可以让自己在碰到相同错误的时候不至于重新走一遍。。。。　　　　　　　　昨天导入数据的时候，碰到了一个问题是将一个大数组里面的每一个元素中的一些不要的去提出掉，本身这些元素每一个本身也是数组，然后我去遍历大数组，又去遍历小数组，然后要赋值的条件就懵了，因为是双重循环，所以后面洗澡想起来可以用一个函数去跑内...

一个可以选择目录生成doc目录内容的小工具(二)-os库目录遍历

回到一目录遍历是一个经典话题，花些功夫也很值得。（好在之前了解过）实现目录遍历的方式有三种，递归、栈、队列。递归一般是函数自己调用自己，一直到满足退出的条件。栈和队列就是数据结构，栈stack是后进先出，队列queue是先进先出。很好理解。（在python里没有这两种数据对象，实现上就是个list，看你怎么捣鼓。一般目录遍历使用递归就可以，简单快捷。感觉堆...

pathlib

发现了遍历文件夹下文件更简单的方法库了，激动。 你就看看代码相比os模块有多简单： root = Path("./try—_python") new_dir = root/Path("test")　　#这句话相当于 new_dir = os.path.join(root, 'test') print(str(new_dir)) from pathlib...

MongoDB查询（游标操作、游标信息）

转自：http://blog.csdn.net/congcong68/article/details/46933609 一、简介 db.collection.find()可以实现根据条件查询和指定使用投影运算符返回的字段省略此参数返回匹配文档中的所有字段。并返回到匹配文档的游标，可以随意修改查询限制、跳跃、和排序顺序的功能。 二、db.collectio...

（转）Oracle存储过程

Oracle存储过程基本语法 存储过程 　　1 CREATE OR REPLACE PROCEDURE 存储过程名 　　2 IS 　　3 BEGIN 　　4 NULL; 　　5 END; 行1: 　　CREATE OR REPLACE PROCEDURE 是一个SQL语句通知Oracle数据库去创建一个叫做skeleton存储过程, 如果存在就覆盖它; 行...

Java通过遍历sessionId获取服务器所有会话session

　　Servlet2.1之后不支持SessionContext里面getSession(String id)方法，也不存在遍历所有会话Session的方法。但是，我们可以通过HttpSessionListener监听器和全局静态map自己实现一个SessionContext，然后用SessionContext管理一份服务器所有会话的Session。 1.w...

最新文章

随机推荐

思享工具箱导航