数据结构和算法的Java实现二叉树

《数据结构和算法的Java实现二叉树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《Java高级程序设计》专业教程理论讲解部分Ver3.120061课程概述二叉树的相关概念二叉树的实现二叉树的查询二叉树的删除二叉树的遍历重点二叉树的实现难点二叉树的实现学习目标掌握二叉树的使用20062二叉树综合了有序数组与链表得优点.有序数组具有较快得查找速度,链表具有非常好得插入删除效率.树结合了两者得有点,使得它具有很高得插入删除及查找得效率.它得实现与其结构密切相关,下面我们来看看它的结构.6.6二叉树2006312345678这是一棵很简单的树.树主要是由结点及结点之间得关系组成的下

2、面给出一些相关得概念6.6二叉树20064二叉树或者是一棵空树，或者是一棵由一个根结点和两棵互不相交的分别称根的左子树和右子树所组成的非空树，左子树和右子树又同样都是一棵二叉树.右图为一棵二叉树二叉树:1234566.6二叉树20065路径:顺着连接节点的边从一个节点走到另一个节点，所经过的节点的顺序排列就称为“路径”。123456其中橙色得线就代表一条路径6.6二叉树20066根:树得顶端称为根.每棵树只有一个根.123456右图中1为根父结点与子结点:除根结点外,其余结点都有另外一个结点指向

3、它.那么指向其它结点的结点称为父结点.被指向的结点称为子结点.右图中3为6的父结点,6为3的子结点6.6二叉树20067123456叶结点:没有子结点的结点称为叶结点.图中4,5,6均为叶结点.子树:每一个结点都可以看作是其子孙结点的根.这样将其与其子孙结点的集合称为子树图中2,4,5可以看作是一棵子树.6.6二叉树20068123456遍历:根据某种规则,对树中所有的结点全部访问一次称作一次遍历.例如:1,2,3,4,5,6就是一次遍历.它是按照由高到低的顺序遍历的.或者称为广度优先遍历.层:

4、树中从根开始计算的“辈分”.0126.6二叉树20069实现二叉树首先就要实现它的结点.它的每一个结点除了要保存相应的数据之外,还要保存其子结点的引用.其数据需要两个域,一个保存键值,另一个保存该键值所对应的数据.privateclassNode{intkey;intvalue;Nodeleft;Noderight;}6.6二叉树200610当我们拥有了结点以后,就可以着手创建我们的树了.一颗数最特殊的结点就是它的根结点,当拥有了根结点就意味着你拥有了整棵树.所以我们要用一个变量来保存这个非常重

5、要的根.privateNoderoot;6.6二叉树200611二叉树的初始化非常的简单.只需要有个根就可以了,而且树是空的.所以甚至连根的初始化都可以省略.publicMyTree(){super();root=null;}这里唯一的一句root=null;都可以省略.因为对象在初始化时,其成员变量自动是空.为了清晰,还是把它加上.6.6二叉树200612二叉树的插入是保证起有序性的重要环节.如果随意的插入则无法保证其有序性.二叉树的顺序一棵有序的二叉树叫搜索二叉树.其定义是根要大于左子树所有

6、结点,小于右子树所有结点.其子树仍然遵循这个规律.我们要建立的便是一棵这样的搜索二叉树.6.6二叉树200613102131516如图,该树便是一棵搜索二叉树.下面我们要讨论如何将7插入该树.首先我们要访问根结点,判断这个7应该放在其左子树还是右子树.7<10,所以7应该放在左子树中.6.6二叉树200614102131516然后,对根的左子树进行检查.判断该子树是否为空,若空则将7加入.非空则继续判断在该子树中的位置.根的左子树非空且值为2,后判断2<7,则7应该在该子树的右子树中.6.6二叉

7、树200615102131516依次继续,直到判断到5后,7应该在5的右子树中,且5的右子树为空.于是将7加入5的右子树中76.6二叉树200616privatevoidinsertNode(NodesubtreeRoot,NodenewNode){Nodecurrent=subtreeRoot;while(true){if(newNode.key

8、ent=current.left;}}else{if(current.right==null){current.right=newNode;return;}else{current=current.right;}}}}这是插入结点代码的实现其中subtreeRoot是要查询子树的根newNode是要插入的结点新结点在当前结点的左子树新结点在当前结点的右子树左结点空加入左结点非空继续查询右结点空加入右结点非空继续查询6.6二叉树200617此时,我们可以通过使用结点Node来建立一棵树.并且,可以