MyException - 我的异常网
当前位置:我的异常网» 数据结构与算法 » JAVA实现二叉树(简易版-实现了二叉树的各种遍历)

JAVA实现二叉树(简易版-实现了二叉树的各种遍历)

www.MyException.Cn  网友分享于:2015-05-03  浏览:0次
JAVA实现二叉树(简易版--实现了二叉树的各种遍历)

1,个人感觉二叉树的实现主要还是如何构造一颗二叉树。构造二叉树函数的设计方法多种多样,本例采用 addNode 方法实现。以下程序通过定义内部类来表示二叉树的结点,然后再实现了二叉树这种数据结构的一些基本操作。

 2,说说以下程序的一些不足:

 a,56行中的判断树是否为空时,依据根结点的数据域是否为空来判断。而使用不带参数的构造函数构造二叉树时,根结点的不空的,此时说明树已经有了根结点,但是根结点的数据却是空的,此时的树高度为1,但是不能访问树根结点,因为树根结点的数据域没有值。

3,重点讲解下二叉树遍历的几个方法

先序遍历:将先序遍历过程中遇到的结点添加到ArrayList<TreeNode>中。根据先序遍历的递归的性质,调用addAll(Container c)方法完成遍历主要过程。

层序遍历:层序遍历需要使用队列,方法level_Traverse 中定义了ArrayDeque<TreeNode> 类型的队列。

  1 package tree;
  2 
  3 import java.util.ArrayDeque;
  4 import java.util.ArrayList;
  5 import java.util.List;
  6 import java.util.Queue;
  7 
  8 public class BinaryTree<E> {
  9     //为什么要用静态内部类?静态内部类中不能访问外部类的非静态成员
 10     public static class TreeNode{
 11 //        E data;
 12         Object data;
 13         TreeNode left;
 14         TreeNode right;
 15         public TreeNode(){
 16             
 17         }
 18         public TreeNode(Object data){
 19             this.data = data;
 20         }
 21         //构造一个新节点,该节点以left节点为其左孩子,right节点为其右孩子
 22         public TreeNode(Object data, TreeNode left, TreeNode right){
 23             this.data = data;
 24             this.left = left;
 25             this.right = right;
 26         }
 27     }
 28     
 29     private TreeNode root;//实现二叉树的类的数据域,即根结点来表示二叉树
 30     
 31     public BinaryTree(){
 32         this.root = new TreeNode();
 33     }
 34     //以指定的根元素创建一颗二叉树
 35     public BinaryTree(E data){
 36         this.root = new TreeNode(data);
 37     }
 38     
 39     //为指定的结点添加子结点
 40     public TreeNode addNode(TreeNode parent, E data, boolean isLeft){
 41         if(parent == null)
 42             throw new RuntimeException("父节点为空,无法添加子结点");
 43         if(isLeft && parent.left != null)
 44             throw new RuntimeException("节点已经左子节点,添加失败");
 45         if(!isLeft && parent.right != null)
 46             throw new RuntimeException("节点已经有右子节点,添加失败");
 47         TreeNode newNode = new TreeNode(data);
 48         if(isLeft)
 49             parent.left = newNode;
 50         else
 51             parent.right = newNode;
 52         return newNode;
 53     }
 54     
 55     public boolean empty(){
 56         return root.data == null;//根据根元素判断二叉树是否为空
 57     }
 58     
 59     public TreeNode root(){
 60         if(empty())
 61             throw new RuntimeException("树空,无法访问根结点");
 62         return root;
 63     }
 64     
 65     public E parent(TreeNode node){
 66         return null;//采用二叉树链表存储时,访问父结点需要遍历整棵二叉树,因为这里不实现
 67     }
 68     
 69     //访问指定节点的左结点,返回的是其左孩子的数据域
 70     public E leftChild(TreeNode parent){
 71         if(parent == null)
 72             throw new RuntimeException("空结点不能访问其左孩子");
 73         return parent.left == null ? null : (E)parent.left.data;
 74     }
 75     public E rightChild(TreeNode parent){
 76         if(parent == null)
 77             throw new RuntimeException("空结点不能访问其右孩子");
 78         return parent.right == null ? null : (E)parent.right.data;
 79     }
 80     
 81     public int deep(){
 82         return deep(root);
 83     }
 84     private int deep(TreeNode node){
 85         if(node == null)
 86             return 0;
 87         else if(node.left == null && node.right == null)
 88             return 1;
 89         else{
 90             int leftDeep = deep(node.left);
 91             int rightDeep = deep(node.right);
 92             int max = leftDeep > rightDeep ? leftDeep : rightDeep;
 93             return max + 1;
 94         }
 95     }
 96     
 97     /*二叉树的先序遍历,实现思想如下:树是一种非线性结构,树中各个结点的组织方式有多种方式
 98      * 先序,即是一种组织方式。它将结点的非线性变成了按照某种方式组织成的线性结构
 99      */
100     //返回一个list,树中结点以先序的方式存放在该list中
101     public List<TreeNode> preTraverse(){
102         return preOrderTraverse(root);
103     }
104     private List<TreeNode> preOrderTraverse(TreeNode node){
105         List<TreeNode> list = new ArrayList<TreeNode>();
106         list.add(node);
107         if(node.left != null)
108             list.addAll(preOrderTraverse(node.left));//递归的奇妙之处
109         if(node.right != null)
110             list.addAll(preOrderTraverse(node.right));
111         return list;
112     }
113     
114     //中序遍历
115     public List<TreeNode> inTraverse(){
116         return inOrderTraverse(root);
117     }
118     private List<TreeNode> inOrderTraverse(TreeNode node){
119         List<TreeNode> list = new ArrayList<TreeNode>();
120         if(node.left != null)
121             list.addAll(inOrderTraverse(node.left));
122         list.add(node);
123         if(node.right != null)
124             list.addAll(inOrderTraverse(node.right));
125         return list;
126     }
127     
128     //后序遍历
129     public List<TreeNode> postTraverse(){
130         return post_Traverse(root);
131     }
132     private List<TreeNode> post_Traverse(TreeNode node){
133         List<TreeNode> list = new ArrayList<TreeNode>();
134         if(node.left != null)
135             list.addAll(post_Traverse(node.left));
136         if(node.right != null)
137             list.addAll(post_Traverse(node.right));
138         list.add(node);
139         return list;
140     }
141     
142     //层序遍历
143     public List<TreeNode> levelTraverse(){
144         return level_Traverse(root);
145     }
146     private List<TreeNode> level_Traverse(TreeNode node){
147         Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
148         List<TreeNode> list = new ArrayList<TreeNode>();//按层序遍历定义的顺序将树中结点依次添加到数组列表中
149         if(root != null)//先将根结点入队列
150             queue.offer(root);
151         while(!queue.isEmpty())//队列不空时,说明遍历还未结束
152         {
153             list.add(queue.peek());//将队头元素添加到数组列表中
154             TreeNode p = queue.poll();//队头元素出队列
155             if(p.left != null)
156                 queue.offer(p.left);//队头元素的左孩子入队列
157             if(p.right != null)
158                 queue.offer(p.right);//队头元素的右孩子入队列
159         }
160         return list;
161     }
162 }

 

测试遍历的程序如下:

import java.util.ArrayList;
import java.util.List;

public class BinaryTreeTest {
    public static void main(String[] args) {
        BinaryTree<String> bt = new BinaryTree<String>("根节点");
        BinaryTree.TreeNode tn1 = bt.addNode(bt.root(),"第二层左子结点", true);
        BinaryTree.TreeNode tn2 = bt.addNode(bt.root(), "第二层右子结点", false);
        BinaryTree.TreeNode tn3 = bt.addNode(tn2,"第三层左子结点",true);
        
        List<BinaryTree.TreeNode> list1 = new ArrayList<BinaryTree.TreeNode>();
        list1 = bt.inTraverse();
        System.out.println("inorder traverse");
        for(BinaryTree.TreeNode node : list1)
            System.out.print(node.data + " ");
        
        List<BinaryTree.TreeNode> list2 = new ArrayList<BinaryTree.TreeNode>();
        list2 = bt.preTraverse();
        System.out.println("\n preorder traverse");
        for(BinaryTree.TreeNode node : list2)
            System.out.print(node.data + " ");
        List<BinaryTree.TreeNode> list3 = new ArrayList<BinaryTree.TreeNode>();
        list3 = bt.levelTraverse();
        System.out.println("\n level traverse");
        for(BinaryTree.TreeNode node : list3)
            System.out.println(node.data + " ");
    }
}

 

文章评论

我的丈夫是个程序员
我的丈夫是个程序员
我是如何打败拖延症的
我是如何打败拖延症的
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
每天工作4小时的程序员
每天工作4小时的程序员
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
如何成为一名黑客
如何成为一名黑客
程序员应该关注的一些事儿
程序员应该关注的一些事儿
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
2013年中国软件开发者薪资调查报告
2013年中国软件开发者薪资调查报告
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
旅行,写作,编程
旅行,写作,编程
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
那些争议最大的编程观点
那些争议最大的编程观点
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
老程序员的下场
老程序员的下场
程序员都该阅读的书
程序员都该阅读的书
那些性感的让人尖叫的程序员
那些性感的让人尖叫的程序员
鲜为人知的编程真相
鲜为人知的编程真相
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
程序员和编码员之间的区别
程序员和编码员之间的区别
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
为什么程序员都是夜猫子
为什么程序员都是夜猫子
10个调试和排错的小建议
10个调试和排错的小建议
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
Java程序员必看电影
Java程序员必看电影
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
总结2014中国互联网十大段子
总结2014中国互联网十大段子
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
 程序员的样子
程序员的样子
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
一个程序员的时间管理
一个程序员的时间管理
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
中美印日四国程序员比较
中美印日四国程序员比较
Google伦敦新总部 犹如星级庄园
Google伦敦新总部 犹如星级庄园
代码女神横空出世
代码女神横空出世
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有