2013.07.31
上课内容:二叉树
首先我们回顾一下上节课的内容,上节课我们讲的是链表。
我们知道了双链表每个节点是由一个三部分组成,一部分存储数据,另外两个部分分别存储上一个节点的地址和下一个节点的地址。那么我们今天要讲的二叉树其实与双链表里节点的组成是相同的,只不过除了存储数据部分外,另外两个分别存储以该节点作为根节点的左子树和右子树的地址。二叉树和链表的最大区别在于链表是一条链子,是特殊的二叉树,而二叉树更像一个树木,有根和叶子。
下面我们来具体地介绍一下二叉树:
首先二叉树有一个最顶端的节点,叫做根节点,然后在根节点下有很多的节点我们称之为叶子节点。每个节点都会存储数据和它的左右子树的地址,如果没有就为null。二叉树和树的最大区别在于二叉树每个节点只能开两个叉,而我们生活中的树可以开多个叉,又可以说二叉树是树的一个特例。
二叉树的遍历方式:前序遍历,中序遍历,后序遍历,深度优先遍历,广度优先遍历,层序遍历。我们这里介绍前三种比较基本的遍历方式:前序遍历,中序遍历和后序遍历。
前序遍历:先遍历根节点,然后遍历其左节点,最后遍历其右节点。若根节点下左节点还有子树的话,就要以它为根节点按同样规则遍历其子树。前序遍历可以用三个字来精辟地概括:根左右。同理我们也可以概括中序遍历:左根右,后序遍历:左右根。
理论总归是理论,实践才能出真知,下面我们开始一个二叉树:
首先我们还是构建一个节点类:
public class Node { private int data;// 节点的数据 private Node left;// 左节点 private Node right;// 右节点 /** * 构造方法 * * @param data要输入的数据 */ public Node(int data) { this.data = data; } /** * 构造方法 * * @param data要输入的数据 * @param left左节点 * @param right右节点 */ public Node(int data, Node left, Node right) { this.data = data; this.left = left; this.right = right; } public int getData() { return data; } public void setData(int data) { this.data = data; } public Node getLeft() { return left; } public void setLeft(Node left) { this.left = left; } public Node getRight() { return right; } public void setRight(Node right) { this.right = right; } }
创建好节点类,我们开始构建我们的二叉树,包括增加节点,删除节点,和三种遍历方式:
public class NodeTree { private Node root;// 根节点 /** * 增加一个节点 * * @param node所要增加的节点 */ public void add(Node node) { // 如果根节点为空 if (root == null) { // 将node设置为根节点 root = node; } else { // 否则调用方法进入节点 querynode(root, node); } } /** * 移除节点的的方法 * * @param root根节点 * @param node指定节点 * @return */ public boolean remove(Node root, Node node) { // 如果指定节点就是根节点 if (root == node) { // 设置根节点为空 root = null; } // 如果找到跟节点,返回true else if (findnode(root, node)) { return true; } // 如果没找到,返回false return false; } /** * 找节点的方法 * * @param node1根节点 * @param node2要找的节点 * @return */ public boolean findnode(Node node1, Node node2) { // 如果左边的节点不为空 if (node1.getLeft() != null) { // 如果左边就是要找的节点 if (node1.getLeft() == node2) { // 设置其根节点的左边为空,并返回true node1.setLeft(null); return true; }// 否则,继续找它的左子叶 else { findnode(node1.getLeft(), node2); } } // 如果右边的节点不为空 if (node1.getRight() != null) { // 如果右边就是要找的节点 if (node1.getRight() == node2) { // 设置其根节点的右边为空,并返回true node1.setRight(null); return true; }// 否则,继续找它的右子叶 else { findnode(node1.getRight(), node2); } } return false; } /** * 插入节点的方法 * * @param node1根节点 * @param node2要插入的节点 */ public void querynode(Node node1, Node node2) { // 如果根节点小于子叶节点 if (node1.getData() < node2.getData()) { // 判断其右子叶是否为空如果不为空,继续朝下遍历 if (node1.getRight() != null) { querynode(node1.getRight(), node2); } else { // 若右子叶为空,将节点放在这里 node1.setRight(node2); } } else { // 判断其左子叶是否为空如果不为空,继续朝下遍历 if (node1.getLeft() != null) { querynode(node1.getLeft(), node2); } else { // 若左子叶为空,将节点放在这里 node1.setLeft(node2); } } } /** * 前序遍历 * * @param node根节点 */ public void preorder(Node root) { // 如果输入的节点不为空 if (root != null) { // 访问根节点 visit(root); // 遍历其左子树 preorder(root.getLeft()); // 遍历右字数 preorder(root.getRight()); } } /** * 中序遍历 * * @param root根节点 */ public void inorder(Node root) { if (root != null) { // 如果左子树不为空 if (root.getLeft() != null) { // 遍历其左子树 inorder(root.getLeft()); } // 访问根节点 visit(root); // 如果右子树不为空 if (root.getRight() != null) { // 遍历其右子树 inorder(root.getRight()); } } } /** * 后序遍历 * * @param root根节点 */ public void postorder(Node root) { if (root != null) { // 如果左子树不为空 if (root.getLeft() != null) { // 遍历其左子树 postorder(root.getLeft()); } // 如果右子树不为空 if (root.getRight() != null) { // 遍历其右子树 postorder(root.getRight()); } // 访问根节点 visit(root); } } /** * 得到根节点 * * @return 根节点 */ public Node getRoot() { return root; } /** * 访问节点 * * @param node要被访问的节点 */ public void visit(Node node) { // 输出节点的data System.out.print(node.getData() + " "); } }
这样二叉树就构建完成了,没学之前感觉挺复杂的,但是通过努力觉得其实没有想象中的那么难,不怕不会,就怕被问题给吓倒,同志们,努力吧!
相关推荐
用Java编写的二叉树代码,非常有用的东西,希望大家多多支持。
简单的描述了JAVA实现二叉树
java实现的二叉树源码,包括建立、前序、中序、后序遍历算法,查找算法
包括 add delete find 等方法,适用于搞java/android开发的同学学习和了解二叉树的结构以及实现。
java二叉树代码,该二叉树为可视化二叉树,可视化为swing中group的嵌套,通过点击add按钮添加子叶,通过点击delete删除子叶,同时会删除它下面的所有子树。图形化的操作非常适合二叉树的理解。
本代码由java语言实现二叉树的各种操作 包括树的创建,查找,删除,按层遍历,输出所有路径,中序遍历等操作
一个简单的课程设计,使用Java来实现二叉树的中序遍历
数据结构java树与二叉树PPT课件.pptx
平衡二叉树Java实现,平衡二叉树Java实现,平衡二叉树Java实现,平衡二叉树Java实现,
基于JAVA开发的二叉树课程设计与实现,程序代码和文档都有。
用JAVA写的二叉树,大一的作品,很多细节没有弄好,仅供初学者参考,
文档中是我自己实现的用java语言实现(1)判断给定的二叉树是否平衡;(2)二叉树插入新数据后,如果失衡自我旋转调整的方法。
java数据结构二叉树的打印,通过队列,栈等,最后前序中序后序和层次四种遍历。。。
二叉树的查找、插入、删除和输出根节点到当前节点的路径 二叉树的前序遍历,中序遍历和后续遍历 TreeNode.java --定义树节点 Mytree.java----创建树结构和上述功能函数 TestTree.java --测试上述的功能
java编写的二叉树的各种操作,其中包括二叉排序树和平衡二叉树的各项操作,用于学习数据结构,可以运行
java实现二叉树非递归前序中序后序遍历
Java实现二叉树中序线索化 左键画节点 右键画跟 点可以拖动 两个节点可以连线 确认进行线索化 并画出线索
二叉树的遍历 基于Java实现的二叉树的创建以及三种遍历.zip基于Java实现的二叉树的创建以及三种遍历.zip基于Java实现的二叉树的创建以及三种遍历.zip
二叉树是每个结点最多有两个子树的有序树。java 二叉树新增删除,遍历二叉树
java实现二叉树遍历demo,一个简单是实例