二叉树的Java实现及特点总结

企鹅博客
18926
文章
0
评论
2020年1月12日16:13:31 评论 9 views 4173字阅读13分54秒

二叉树是一种非常重要的数据结构,它同时具有数组和链表各自的特点:它可以像数组一样快速查找,也可以像链表一样快速添加。但是他也有自己的缺点:删除操作复杂。

我们先介绍一些关于二叉树的概念名词。

二叉树:是每个结点最多有两个子树的有序树,在使用二叉树的时候,数据并不是随便插入到节点中的,一个节点的左子节点的关键值必须小于此节点,右子节点的关键值必须大于或者是等于此节点,所以又称二叉查找树、二叉排序树、二叉搜索树。

完全二叉树:若设二叉树的高度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第h层有叶子结点,并且叶子结点都是从左到右依次排布,这就是完全二叉树。

满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。

深度——二叉树的层数,就是深度。

二叉树的特点总结:

(1)树执行查找、删除、插入的时间复杂度都是O(logN)

(2)遍历二叉树的方法包括前序、中序、后序

(3)非平衡树指的是根的左右两边的子节点的数量不一致

(4) 在非空二叉树中,第i层的结点总数不超过 , i>=1;

(5)深度为h的二叉树最多有个结点(h>=1),最少有h个结点;

(6)对于任意一棵二叉树,如果其叶结点数为N0,而度数为2的结点总数为N2,则N0=N2+1;

二叉树的Java代码实现

首先是树的节点的定义,下面的代码中使用的是最简单的int基本数据类型作为节点的数据,如果要使用节点带有更加复杂的数据类型,换成对应的对象即可。

/**
 *
 * @ClassName: com.tree.TreeNode
 * @Description: 节点
 * @author zhaokaiqiang
 * @date 2014-12-5 下午4:43:24
 *
 */
public class TreeNode {

 // 左节点
 private TreeNode lefTreeNode;
 // 右节点
 private TreeNode rightNode;
 // 数据
 private int value;

 private boolean isDelete;

 public TreeNode getLefTreeNode() {
  return lefTreeNode;
 }

 public void setLefTreeNode(TreeNode lefTreeNode) {
  this.lefTreeNode = lefTreeNode;
 }

 public TreeNode getRightNode() {
  return rightNode;
 }

 public void setRightNode(TreeNode rightNode) {
  this.rightNode = rightNode;
 }

 public int getValue() {
  return value;
 }

 public void setValue(int value) {
  this.value = value;
 }

 public boolean isDelete() {
  return isDelete;
 }

 public void setDelete(boolean isDelete) {
  this.isDelete = isDelete;
 }

 public TreeNode() {
  super();
 }

 public TreeNode(int value) {
  this(null, null, value, false);
 }

 public TreeNode(TreeNode lefTreeNode, TreeNode rightNode, int value,
   boolean isDelete) {
  super();
  this.lefTreeNode = lefTreeNode;
  this.rightNode = rightNode;
  this.value = value;
  this.isDelete = isDelete;
 }

 @Override
 public String toString() {
  return "TreeNode [lefTreeNode=" + lefTreeNode + ", rightNode="
    + rightNode + ", value=" + value + ", isDelete=" + isDelete
    + "]";
 }

}

下面给出二叉树的代码实现。由于在二叉树中进行节点的删除非常繁琐,因此,下面的代码使用的是利用节点的isDelete字段对节点的状态进行标识

/**
 *
 * @ClassName: com.tree.Tree
 * @Description: 二叉树的定义
 * @author zhaokaiqiang
 * @date 2014-12-8 上午7:51:49
 *
 */

public class BinaryTree {

 // 根节点
 private TreeNode root;

 public TreeNode getRoot() {
  return root;
 }

 /**
  * 插入操作
  *
  * @param value
  */
 public void insert(int value) {

  TreeNode newNode = new TreeNode(value);

  if (root == null) {
   root = newNode;
   root.setLefTreeNode(null);
   root.setRightNode(null);
  } else {

   TreeNode currentNode = root;
   TreeNode parentNode;

   while (true) {

    parentNode = currentNode;
    // 往右放
    if (newNode.getValue() > currentNode.getValue()) {
     currentNode = currentNode.getRightNode();
     if (currentNode == null) {
      parentNode.setRightNode(newNode);
      return;
     }
    } else {
     // 往左放
     currentNode = currentNode.getLefTreeNode();
     if (currentNode == null) {
      parentNode.setLefTreeNode(newNode);
      return;
     }

    }
   }
  }
 }

 /**
  * 查找
  *
  * @param key
  * @return
  */
 public TreeNode find(int key) {

  TreeNode currentNode = root;

  if (currentNode != null) {

   while (currentNode.getValue() != key) {

    if (currentNode.getValue() > key) {
     currentNode = currentNode.getLefTreeNode();
    } else {
     currentNode = currentNode.getRightNode();
    }

    if (currentNode == null) {
     return null;
    }

   }

   if (currentNode.isDelete()) {
    return null;
   } else {
    return currentNode;
   }

  } else {
   return null;
  }

 }

 /**
  * 中序遍历
  *
  * @param treeNode
  */
 public void inOrder(TreeNode treeNode) {
  if (treeNode != null && treeNode.isDelete() == false) {
   inOrder(treeNode.getLefTreeNode());
   System.out.println("--" + treeNode.getValue());
   inOrder(treeNode.getRightNode());
  }
 }

}

在上面对二叉树的遍历操作中,使用的是中序遍历,这样遍历出来的数据是增序的。

下面是测试代码:

public class Main {

 public static void main(String[] args) {

  BinaryTree tree = new BinaryTree();
  // 添加数据测试
  tree.insert(10);
  tree.insert(40);
  tree.insert(20);
  tree.insert(3);
  tree.insert(49);
  tree.insert(13);
  tree.insert(123);

  System.out.println("root=" + tree.getRoot().getValue());
  // 排序测试
  tree.inOrder(tree.getRoot());
  // 查找测试
  if (tree.find(10) != null) {
   System.out.println("找到了");
  } else {
   System.out.println("没找到");
  }
  // 删除测试
  tree.find(40).setDelete(true);

  if (tree.find(40) != null) {
   System.out.println("找到了");
  } else {
   System.out.println("没找到");
  }

 }

}

二叉树的常见问题及其解决程序 http://www.linuxidc.com/Linux/2013-04/83661.htm

【递归】二叉树的先序建立及遍历 http://www.linuxidc.com/Linux/2012-12/75608.htm

在JAVA中实现的二叉树结构 http://www.linuxidc.com/Linux/2008-12/17690.htm

【非递归】二叉树的建立及遍历 http://www.linuxidc.com/Linux/2012-12/75607.htm

二叉树递归实现与二重指针 http://www.linuxidc.com/Linux/2013-07/87373.htm

二叉树先序中序非递归算法 http://www.linuxidc.com/Linux/2014-06/102935.htm

继续阅读
  • 版权声明: 发表于 2020年1月12日16:13:31
  • 转载注明:https://www.qieseo.com/180911.html
C++中的显式类型转换操作符 Linux编程

C++中的显式类型转换操作符

即使类型转换本身是危险的,在有些时候类型转换也是不可或缺的。程序员不使用显式转换,编译器也可能会使用隐式转换,那还不如把代码控制在程序员自己手中。 C++有4种显式类型转换操作符,最好不要使用C语言编...
Java编程:组合、继承和代理的区别 Linux编程

Java编程:组合、继承和代理的区别

组合、继承和代理三者的定义: 组合:在新类中new 另外一个类的对象,以添加该对象的特性。 继承:从基类继承得到子类,获得基类的特性。 代理:在代理类中创建某功能的类,调用类的一些方法以获得该类的部分...
Linux文件编程学习 Linux编程

Linux文件编程学习

在Linux平台下对文件编程可以使用两类函数:(1)Linux操作系统文件API;(2)C语言I/O库函数。 前者依赖于Linux系统调用,后者实际上与操作系统是独立的,因为在任何操作系统下,使用C语...
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: