您好，欢迎来到九壹网。
科技 教育 生活 旅游 时尚 美容 美食 健康 体育 游戏 汽车 家电
搜索
您的当前位置：首页二叉树的Java实现及特点总结

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

来源：九壹网

转载请注明出处：

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

    

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

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

    完全二叉树：若设二叉树的高度为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基本数据类型作为节点的数据，如果要使用节点带有更加复杂的数据类型，换成对应的对象即可。

[java] 

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

[java] 
  1. /** 
  2.  *  
  3.  * @ClassName: com.tree.Tree 
  4.  * @Description: 二叉树的定义 
  5.  * @author zhaokaiqiang 
  6.  * @date 2014-12-8 上午7:51:49 
  7.  *  
  8.  */  
  9.   
  10. public class BinaryTree {  
  11.   
  12.     // 根节点  
  13.     private TreeNode root;  
  14.   
  15.     public TreeNode getRoot() {  
  16.         return root;  
  17.     }  
  18.   
  19.     /** 
  20.      * 插入操作 
  21.      *  
  22.      * @param value 
  23.      */  
  24.     public void insert(int value) {  
  25.   
  26.         TreeNode newNode = new TreeNode(value);  
  27.   
  28.         if (root == null) {  
  29.             root = newNode;  
  30.             root.setLefTreeNode(null);  
  31.             root.setRightNode(null);  
  32.         } else {  
  33.   
  34.             TreeNode currentNode = root;  
  35.             TreeNode parentNode;  
  36.   
  37.             while (true) {  
  38.   
  39.                 parentNode = currentNode;  
  40.                 // 往右放  
  41.                 if (newNode.getValue() > currentNode.getValue()) {  
  42.                     currentNode = currentNode.getRightNode();  
  43.                     if (currentNode == null) {  
  44.                         parentNode.setRightNode(newNode);  
  45.                         return;  
  46.                     }  
  47.                 } else {  
  48.                     // 往左放  
  49.                     currentNode = currentNode.getLefTreeNode();  
  50.                     if (currentNode == null) {  
  51.                         parentNode.setLefTreeNode(newNode);  
  52.                         return;  
  53.                     }  
  54.   
  55.                 }  
  56.             }  
  57.         }  
  58.     }  
  59.   
  60.     /** 
  61.      * 查找 
  62.      *  
  63.      * @param key 
  64.      * @return 
  65.      */  
  66.     public TreeNode find(int key) {  
  67.   
  68.         TreeNode currentNode = root;  
  69.   
  70.         if (currentNode != null) {  
  71.   
  72.             while (currentNode.getValue() != key) {  
  73.   
  74.                 if (currentNode.getValue() > key) {  
  75.                     currentNode = currentNode.getLefTreeNode();  
  76.                 } else {  
  77.                     currentNode = currentNode.getRightNode();  
  78.                 }  
  79.   
  80.                 if (currentNode == null) {  
  81.                     return null;  
  82.                 }  
  83.   
  84.             }  
  85.   
  86.             if (currentNode.isDelete()) {  
  87.                 return null;  
  88.             } else {  
  89.                 return currentNode;  
  90.             }  
  91.   
  92.         } else {  
  93.             return null;  
  94.         }  
  95.   
  96.     }  
  97.   
  98.     /** 
  99.      * 中序遍历 
  100.      *  
  101.      * @param treeNode 
  102.      */  
  103.     public void inOrder(TreeNode treeNode) {  
  104.         if (treeNode != null && treeNode.isDelete() == false) {  
  105.             inOrder(treeNode.getLefTreeNode());  
  106.             System.out.println("--" + treeNode.getValue());  
  107.             inOrder(treeNode.getRightNode());  
  108.         }  
  109.     }  
  110.   
  111. }  

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

    下面是测试代码:

[java] 
  1. public class Main {  
  2.   
  3.     public static void main(String[] args) {  
  4.   
  5.         BinaryTree tree = new BinaryTree();  
  6.         // 添加数据测试  
  7.         tree.insert(10);  
  8.         tree.insert(40);  
  9.         tree.insert(20);  
  10.         tree.insert(3);  
  11.         tree.insert(49);  
  12.         tree.insert(13);  
  13.         tree.insert(123);  
  14.   
  15.         System.out.println("root=" + tree.getRoot().getValue());  
  16.         // 排序测试  
  17.         tree.inOrder(tree.getRoot());  
  18.         // 查找测试  
  19.         if (tree.find(10) != null) {  
  20.             System.out.println("找到了");  
  21.         } else {  
  22.             System.out.println("没找到");  
  23.         }  
  24.         // 删除测试  
  25.         tree.find(40).setDelete(true);  
  26.   
  27.         if (tree.find(40) != null) {  
  28.             System.out.println("找到了");  
  29.         } else {  
  30.             System.out.println("没找到");  
  31.         }  
  32.   
  33.     }  
  34.   
  35. }  

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文

Copyright © 2019- 91gzw.com 版权所有 湘ICP备2023023988号-2

违法及侵权请联系：TEL:199 18 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务