黑马程序员技术交流社区

标题: 二叉树 [打印本页]

作者: huangxuanheng 时间: 2014-8-3 10:37
标题: 二叉树
本帖最后由 huangxuanheng 于 2014-8-6 21:44 编辑

树的结构很简单，只有一个根节点，其他都是子节点，子节点中可能有兄弟，子节点可能还会有子节点。但每一个子节点只有一个父节点。这就是二叉树的结构。那么，如何利用自定义的类模拟创建二叉树呢？

作者: 王松朝 时间: 2014-8-3 15:08
class Tree { public Tree left;
public Tree right;
}

作者: 怀念黑海岸 时间: 2014-8-3 16:27
本帖最后由怀念黑海岸于 2014-8-3 16:29 编辑

这应该跟实现自己的双向链表一样，你首先要清楚二叉树的数据结构模式吧：双向链表的结构单元是一个节点（Node），有一个前节点（pro）和后节点（next），pro指向当前节点的前节点，next指向当前节点的后节点。当pro=null意味着当前节点是链表的第一个元素，next=null则表示是最后一个元素。而二叉树的结构单元也应该是类似的吧，有一个左节点（left），右节点（right），还应该有一个父节点（father）指向上一级的二叉树节点。左右节点分别指向比当前节点大或者小的元素，而当父节点father=null的话意味当前节点是根节点。当left=null&right=null的时候就表示是最小的二叉树节点了。
全是个人浅见，回答不好请担待。

作者: alvinbx 时间: 2014-8-3 16:59
定义一个Node类，里面记录lastNode(及父节点)，然后leftchild，rightchild.至于CRUD可以参考源码或者百度下

作者: huangxuanheng 时间: 2014-8-3 20:04

怀念黑海岸发表于 2014-8-3 16:27
这应该跟实现自己的双向链表一样，你首先要清楚二叉树的数据结构模式吧：双向链表的结构单元是 ...

回答很好，这些我也懂，不过应该怎么模拟呢？

作者: huangxuanheng 时间: 2014-8-3 20:06

alvinbx 发表于 2014-8-3 16:59
定义一个Node类，里面记录lastNode(及父节点)，然后leftchild，rightchild.至于CRUD可以参考源码或者百度下 ...

谢谢......

作者: huangxuanheng 时间: 2014-8-3 20:15

王松朝发表于 2014-8-3 15:08
class Tree { public Tree left;
public Tree right;
}

:handshake.............

作者: 小乖乖灬浩歌 时间: 2014-8-3 20:36
一个存节点类一个存根节点类

作者: bbdeyouxang 时间: 2014-8-3 21:59
建一个二叉树类，名字可以叫BinaryTree，再建一个节点类，可以叫Node。Node可以是BinaryTree的内部类，也可以不是，这个无所谓。BinaryTree里面要有一个Node，做为根节点，也是找其他叶子节点的开始。关键的的是Node类，里面需要定义左叶子，右叶子，二者都是Node，还需要一个nodeValue，做为Node本身的值，之后就是初始化了，二叉树的左右叶子节点和父节点的节点有2n和2n+1的关系，一般都是用这个关系来初始化的。后面就是前中后三种二叉树的遍历了，用递归的话比较简单，希望对楼主有用

作者: huangxuanheng 时间: 2014-8-6 21:43

bbdeyouxang 发表于 2014-8-3 21:59
建一个二叉树类，名字可以叫BinaryTree，再建一个节点类，可以叫Node。Node可以是BinaryTree的内部类，也可 ...

说得太好了:hug::victory:

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2