用Java实现二叉树

【文章标题】用Java实现二叉树

【文章作者】曾健生

【作者邮箱】zengjiansheng1@126.com

【作者QQ】190678908

【作者MSN】zengjiansheng1@hotmail.com

【作者博客】blog.csdn.net/newjueqi

首先，确定二叉树的数据结构

package com.newjueqi;/** * 二叉树中叶子的数据结构 */public class Node {private Integer value; // 节点的数值private Node leftNode; // 左孩子结点private Node rightNode; // 右孩子结点public Node(Integer value) {this.value = value;}public Node() {}public Node getLeftNode() {return leftNode;}public void setLeftNode(Node leftNode) {this.leftNode = leftNode;}public Node getRightNode() {return rightNode;}public void setRightNode(Node rightNode) {this.rightNode = rightNode;}public Integer getValue() {return value;}}

生成二叉树的具体类

package com.newjueqi;import java.util.ArrayList;import java.util.List;/** * 生成二叉树的具体类 */public class BinaryTree {private Node root; // 指向二叉树的根节点private List<Integer> dataList; // 保持所有的原创数据Listprivate int index = 0; // 指向List的索引值// 获取根节点public Node getRoot() {return root;}public void setRoot(Node root) {this.root = root;}/** * 生成二叉树 */public BinaryTree(List<Integer> dataList) {this.dataList = dataList;// 创建根节点root = new Node(dataList.get(0));// 创建左孩子结点create(root, dataList.size(), 0);// 创建右孩子结点create(root, dataList.size(), 1);}/** * 用递归的方法生成一颗二叉树 * * @param node * 要生成节点的父节点 * @param index * 所指向List的索引 * @param length * 所指向List的总长度 * @param nodeType * 节点的类型,0为左孩子结点，1为右孩子结点 */public void create(Node node, int length, int nodeType) {index++; // 索引值加1// 判断叶子下是否已没有子节点if (index >= length) {return;}// 判断list中的数据已经读取完毕if (index < length && dataList.get(index) == null) {return;}// 临时变量Node tempNode = null;// 生成左孩子结点if (nodeType == 0) {tempNode = new Node(dataList.get(index));node.setLeftNode(tempNode);} else // 生成右孩子结点{tempNode = new Node(dataList.get(index));node.setRightNode(tempNode);}// 生成左节点create(tempNode, length, 0);// 生成右节点create(tempNode, length, 1);}}

最后是测试类：

package com.newjueqi;import java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.Map;public class ScanTree {/** * 用前序遍历的方法扫描整棵二叉树 * @param node 节点 */public static void scan( Node node ){//当节点为空返回if( node==null ){return ;}System.out.println(node.getValue());//分别递归扫描左右孩子结点scan( node.getLeftNode());scan( node.getRightNode());}public static void main(String[] args) {//用前序遍历的顺序插入二叉树的数据List<Integer> dataList=new ArrayList<Integer>();dataList.add(30);dataList.add(10);dataList.add(20);dataList.add(null);dataList.add(20);dataList.add(null);dataList.add(50);dataList.add(20);dataList.add(null);//创建一颗二叉树BinaryTree tree=new BinaryTree(dataList);//扫描整棵二叉树scan( tree.getRoot());}}

秒客网

用Java实现二叉树

相关文章