`

数据结构 二叉树(B树)

 
阅读更多

BTree

特征:

1.一个节点最多只有两个子节点,其中左子节点的关键字小于这个节点,右子节点的关键字大于等于该节点。

2.执行查找,插入,删除的时间复杂度都是:O(logN)。

3.遍历有中序,前序,后序。前,中和后只是在递归的时候先输出左子,自己或右子的顺序。可以通过中排序,按左子,自己,右子的顺序就是升序,反之则是降序。

4.最大值是树的右边底层叶子;最小值是左边底层叶子。

 

JAVA代码实现:

 

 

Java代码  收藏代码
  1. package org.acooly.datastructure.btree;  
  2.   
  3. import java.util.Random;  
  4.   
  5. /** 
  6.  * 特征:一个节点的左子节点的关键字小于这个节点,右子节点的关键字大于等于该节点。 
  7.  *  
  8.  * @author zhangpu 
  9.  *  
  10.  */  
  11. public class BinaryTree {  
  12.   
  13.     /** 根节点 */  
  14.     private Node root;  
  15.   
  16.     /** 
  17.      * 查找 
  18.      *  
  19.      * @param key 
  20.      * @return 
  21.      */  
  22.     public Node find(int key) {  
  23.         if (root == null) {  
  24.             return null;  
  25.         }  
  26.         Node current = root;  
  27.         while (current.getKey() != key) {  
  28.             if (key < current.getKey()) {  
  29.                 // 小于本节点在左边  
  30.                 current = current.getLeftNode();  
  31.             } else {  
  32.                 // 大于等于本节点在右边  
  33.                 current = current.getRightNode();  
  34.             }  
  35.             if (current == null) {  
  36.                 // 搜索到最后叶子为空,表示没有找到  
  37.                 return null;  
  38.             }  
  39.         }  
  40.         return current;  
  41.     }  
  42.   
  43.     public Node getParent(int key) {  
  44.         if (root == null) {  
  45.             return null;  
  46.         }  
  47.         Node current = root;  
  48.         Node parent = root;  
  49.         while (current.getKey() != key) {  
  50.             if (key < current.getKey()) {  
  51.                 // 小于本节点在左边  
  52.                 parent = current;  
  53.                 current = current.getLeftNode();  
  54.             } else {  
  55.                 // 大于等于本节点在右边  
  56.                 parent = current;  
  57.                 current = current.getRightNode();  
  58.             }  
  59.             if (current == null) {  
  60.                 // 搜索到最后叶子为空,表示没有找到  
  61.                 return null;  
  62.             }  
  63.         }  
  64.         return parent;  
  65.     }  
  66.   
  67.     /** 
  68.      * 插入 
  69.      *  
  70.      * @param key 
  71.      * @param value 
  72.      */  
  73.     public void insert(int key, Object value) {  
  74.         Node node = new Node(key, value);  
  75.         if (root == null) {  
  76.             root = node;  
  77.             return;  
  78.         }  
  79.         Node current = root;  
  80.         while (true) {  
  81.             if (key < current.getKey()) {  
  82.                 if (current.getLeftNode() == null) {  
  83.                     current.setLeftNode(node);  
  84.                     return;  
  85.                 } else {  
  86.                     current = current.getLeftNode();  
  87.                 }  
  88.             } else {  
  89.                 if (current.getRightNode() == null) {  
  90.                     current.setRightNode(node);  
  91.                     return;  
  92.                 } else {  
  93.                     current = current.getRightNode();  
  94.                 }  
  95.             }  
  96.         }  
  97.   
  98.     }  
  99.   
  100.     /** 
  101.      * 中遍历(升序) 
  102.      *  
  103.      * @param startNode 
  104.      */  
  105.     public void inOrderAsc(Node startNode) {  
  106.   
  107.         if (startNode != null) {  
  108.             inOrderAsc(startNode.getLeftNode());  
  109.             System.out.println(startNode);  
  110.             inOrderAsc(startNode.getRightNode());  
  111.         }  
  112.   
  113.     }  
  114.   
  115.     /** 
  116.      * 中遍历(降序) 
  117.      *  
  118.      * @param startNode 
  119.      */  
  120.     public void inOrderDesc(Node startNode) {  
  121.         if (startNode != null) {  
  122.             inOrderDesc(startNode.getRightNode());  
  123.             System.out.println(startNode);  
  124.             inOrderDesc(startNode.getLeftNode());  
  125.         }  
  126.   
  127.     }  
  128.   
  129.     /** 
  130.      * 最大值 算法:树中最底层的右子叶 
  131.      *  
  132.      * @return 
  133.      */  
  134.     public Node getMax() {  
  135.         Node current = root;  
  136.         while (current.getRightNode() != null) {  
  137.             current = current.getRightNode();  
  138.         }  
  139.         return current;  
  140.     }  
  141.   
  142.     /** 
  143.      * 算法:树中最底层的左子叶 
  144.      *  
  145.      * @return 
  146.      */  
  147.     public Node getMin() {  
  148.         return getMin(root);  
  149.     }  
  150.   
  151.     /** 
  152.      * 指定节点的最小节点,如果指定节点为root,则是树的最小节点 
  153.      *  
  154.      * @param localRoot 
  155.      * @return 
  156.      */  
  157.     private Node getMin(Node localRoot) {  
  158.         Node current = localRoot;  
  159.         while (current.getLeftNode() != null) {  
  160.             current = current.getLeftNode();  
  161.         }  
  162.         return current;  
  163.     }  
  164.   
  165.     /** 
  166.      * 删除节点存在3中情况 <li>目标节点是叶子:直接删除,置为null <li> 
  167.      * 目标节点只有一个子节点:如果目标节点是在父节点的左边,直接使用子节点作为父节点的左子,反正则为右子。 <li> 
  168.      * 目标节点有两个子节点:找到后继节点,作为目标节点父节点的对应子节点。(后继:目标节点子节点中大于目标节点最小的个。路径:目标节点右子的最小节点。) 
  169.      *  
  170.      * @param key 
  171.      */  
  172.     public void delete(int key) {  
  173.   
  174.         Node target = find(key);  
  175.         if (target == null) {  
  176.             return;  
  177.         }  
  178.   
  179.         boolean leftExsit = (target.getLeftNode() != null ? true : false);  
  180.         boolean rightExsit = (target.getRightNode() != null ? true : false);  
  181.         // 第一种情况,目标是叶子,直接设置为null  
  182.         if (!leftExsit && !rightExsit) {  
  183.             target = null;  
  184.             return;  
  185.         }  
  186.   
  187.         // 获得目标的父节点  
  188.         Node parent = getParent(key);  
  189.         Node child = null;  
  190.         if (leftExsit != rightExsit) {  
  191.             // 第二种情况:只有一个子  
  192.             child = (leftExsit ? target.getLeftNode() : target.getRightNode());  
  193.         } else {  
  194.             // 第三种情况:有两个子  
  195.             Node rightChild = target.getRightNode();  
  196.             child = getMin(rightChild);  
  197.             getParent(child.getKey()).setLeftNode(null);  
  198.             child.setRightNode(rightChild);  
  199.         }  
  200.   
  201.         if (parent == null) {  
  202.             root = child;  
  203.             target = null;  
  204.             return;  
  205.         }  
  206.   
  207.         if (parent.getLeftNode() != null && target.getKey() < parent.getLeftNode().getKey()) {  
  208.             // 目标是父的左子  
  209.             parent.setLeftNode(child);  
  210.         } else {  
  211.             // 目标是父的右子  
  212.             parent.setRightNode(child);  
  213.         }  
  214.         target = null;  
  215.     }  
  216.   
  217.     public Node getRoot() {  
  218.         return root;  
  219.     }  
  220.   
  221.     public static void main(String[] args) {  
  222.         BinaryTree tree = new BinaryTree();  
  223.         Random random = new Random();  
  224.         // INSERT  
  225.         for (int i = 1; i <= 10; i++) {  
  226.             int key = random.nextInt(100);  
  227.             tree.insert(key, "value" + key);  
  228.         }  
  229.         int key = 0;  
  230.         tree.insert(key, "value" + key);  
  231.         System.out.println("TARGET key: " + key);  
  232.         // FIND  
  233.         System.out.println("FIND: " + tree.find(key));  
  234.         // GETPARENT  
  235.         System.out.println("PARENT: " + tree.getParent(key));  
  236.         // MIX  
  237.         System.out.println("MAX: " + tree.getMax());  
  238.         // MIN  
  239.         System.out.println("MIN: " + tree.getMin());  
  240.         tree.delete(key);  
  241.         System.out.println();  
  242.         System.out.println("中遍历(升序):");  
  243.         tree.inOrderAsc(tree.getRoot());  
  244.         System.out.println("中遍历(降序):");  
  245.         tree.inOrderDesc(tree.getRoot());  
  246.     }  
  247.   
  248. }  

   节点类:

 

Java代码  收藏代码
  1. package org.acooly.datastructure.btree;  
  2.   
  3. /** 
  4.  * BTree 节点 
  5.  *  
  6.  * @author zhangpu 
  7.  *  
  8.  */  
  9. public class Node {  
  10.   
  11.     /** 节点KEY */  
  12.     private int key;  
  13.     private Object value;  
  14.     /** 左子节点 */  
  15.     private Node leftNode;  
  16.     /** 右子节点 */  
  17.     private Node rightNode;  
  18.   
  19.     public Node() {  
  20.         super();  
  21.     }  
  22.   
  23.     public Node(int key, Object value) {  
  24.         super();  
  25.         this.key = key;  
  26.         this.value = value;  
  27.     }  
  28.   
  29.     public int getKey() {  
  30.         return key;  
  31.     }  
  32.   
  33.     public void setKey(int key) {  
  34.         this.key = key;  
  35.     }  
  36.   
  37.     public Node getLeftNode() {  
  38.         return leftNode;  
  39.     }  
  40.   
  41.     public void setLeftNode(Node leftNode) {  
  42.         this.leftNode = leftNode;  
  43.     }  
  44.   
  45.     public Node getRightNode() {  
  46.         return rightNode;  
  47.     }  
  48.   
  49.     public void setRightNode(Node rightNode) {  
  50.         this.rightNode = rightNode;  
  51.     }  
  52.   
  53.     public Object getValue() {  
  54.         return value;  
  55.     }  
  56.   
  57.     public void setValue(Object value) {  
  58.         this.value = value;  
  59.     }  
  60.   
  61.     @Override  
  62.     public String toString() {  
  63.         return String.valueOf(key) + "=" + value;  
  64.     }  
  65.       
  66.     @Override  
  67.     public boolean equals(Object obj) {  
  68.         if(obj instanceof Node){  
  69.             Node n = (Node)obj;  
  70.             if(n.getKey() != getKey()){  
  71.                 return false;  
  72.             }  
  73.         }else{  
  74.             return false;  
  75.         }  
  76.         return true;  
  77.     }  
  78.   
  79. }  

分享到:
评论

相关推荐

    高级数据结构代码 红黑树 二叉树 B树

    本资源包含关于三种高级数据结构的代码实现:红黑树、二叉树和B树。这些数据结构在实际编程中有着广泛的应用,尤其在算法设计、数据库系统、内存管理等领域。 首先,我们来看二叉树,它是数据结构中最基础也是最...

    数据结构 二叉树 树形输出

    ### 数据结构:二叉树的树形输出 #### 一、引言 在计算机科学领域,数据结构是存储和组织数据的方式,对于提高程序效率至关重要。其中,二叉树是一种非常重要的非线性数据结构,它由节点组成,每个节点最多有两个子...

    数据结构 树、二叉树的数据结构 哈夫曼树

    2. 实现哈夫曼树数据结构,使用哈夫曼树完成如下文档的编码与译码,假设该文档由5种符号字符(A、B、C、D、E)构成 ABACDEABBCEABAACCCDEACCBAABCCCA 3. 选做:实现二叉树的中序遍历线索化数据结构 4. 选做:使用...

    数据结构 二叉树 严蔚敏

    在实际应用中,二叉树被广泛应用于排序和搜索算法,如二叉堆(用于优先队列)、B树(用于数据库和文件系统)和B+树(更优化的B树,常用于数据库索引)。二叉树的理论和实践是理解和优化计算机程序性能的基础,对于...

    数据结构实验报告6-树-二叉树的遍历算法-实验内容及要求.docx

    根据给定文件的信息,我们可以详细地探讨一下关于二叉树的遍历算法这一主题,包括实验的目的、数据结构的设计、算法的设计以及输入/输出的设计等内容。 ### 实验目的 本次实验的主要目的是让学生深入理解并掌握...

    数据结构实验 二叉树 MFC

    在进行数据结构实验时,理解二叉树的性质和操作是基础,如平衡二叉树(如AVL树和红黑树)可以保证搜索效率,而B树和B+树则适用于大规模数据的存储。此外,递归是处理二叉树问题的强大工具,例如深度优先搜索(DFS,...

    数据结构广义表实现二叉树

    在计算机科学领域,数据结构是组织和存储数据的方式,它对于高效算法的设计至关重要。...在进行数据结构课程设计时,这种实现方式能帮助学生深入理解二叉树和广义表的内在联系,提高问题解决能力。

    数据结构树与二叉树汇总

    数据结构中的树是一种非...总结来说,数据结构中的树和二叉树是重要的概念,它们在算法设计中发挥着核心作用,特别是在处理表达式解析、搜索、排序等问题时。理解和掌握这些概念及其操作是计算机科学基础的重要部分。

    数据结构实验(树与二叉树)

    在本实验中,主题聚焦于数据结构中的树与二叉树,主要涉及两个核心知识点:一是根据二叉树的先根序列和中根序列构造二叉树,二是将中缀表达式转换为二叉树并计算其值。 1. **先根序列与中根序列构造二叉树**: - ...

    数据结构_ 二叉树

    同时,二叉树的概念还可以扩展到多叉树,如Trie树(字典树)和B树等,这些数据结构在实际应用中都有着重要的作用。 通过深入理解和熟练掌握二叉树及其操作,可以提升程序员在算法设计和问题解决上的能力,尤其是在...

    数据结构基础内容与B-树的详解

    通过阅读《数据结构高分笔记》精彩摘录之考研数据结构必备基础知识.pdf和《数据结构高分笔记》精彩摘录之B-树.pdf,读者可以深入理解这些概念,并获得实际应用的指导。学习数据结构不仅是为了解决编程问题,更是为了...

    这是数据结构课程设计,二叉树表示的算术表达式

    二叉树是一种特殊的树形数据结构,其中每个节点最多有两个子节点,分别被称为左子节点和右子节点。二叉树常用于搜索、排序和表达式解析等任务。 在计算领域,二叉树可以用来表示算术表达式。这种表示方式称为二叉...

    数据结构二叉树深度广度查询

    根据给定的文件信息,我们可以总结出以下关于“数据结构二叉树深度广度查询”的相关知识点: ### 一、二叉树基本概念 在计算机科学中,**二叉树**是一种常用的数据结构,其中每个节点最多有两个子节点,通常被称作...

    西南科技大学SWUST OJ 数据结构 树和二叉树答案 树和二叉树.zip

    在IT领域,数据结构是计算机科学的基础,而树和二叉树是其中极其重要的概念。西南科技大学(SWUST)的在线编程平台(OJ)提供了关于这些主题的编程题目,帮助学生深入理解和应用这些知识。以下是对这些题目涉及知识...

    数据结构课程设计+二叉树的动态演示C++

    通过这些文件,我们可以学习到如何在C++中实现和操作二叉树,特别是二叉搜索树和B树,以及如何将这些数据结构可视化,以帮助理解其工作原理。这对于提升编程技能和深入理解数据结构是非常有益的。此外,这个项目还...

    数据结构二叉树的使用

    2. 数据库索引:B树和B+树是二叉树的变种,常用于数据库的索引结构,以提高查询效率。 3. 编译器:词法分析和语法分析过程中,编译器会使用二叉树来表示源代码的语法结构,如抽象语法树(AST)。 4. 图像处理:在...

    数据结构中二叉树操作C++代码

    根据给定的信息,本文将对数据结构中的二叉树及其在C++中的实现进行详细的解析。主要内容包括二叉树的基本定义、二叉树节点结构、创建二叉树的方法、以及几种常用的二叉树操作(如遍历、计算高度、叶子节点数量等)...

    数据结构5.10二叉树线索链表存储结构

    ### 数据结构5.10二叉树线索链表存储结构 #### 一、知识点概述 在数据结构的学习中,二叉树是一种非常重要的非线性数据结构,它具有丰富的应用场景和变化形式。其中,二叉树的线索链表存储结构是通过对二叉树的...

    算法-树形结构- 树与二叉树- 树的数据生成器.rar

    3. **树的类型**:包括但不限于二叉搜索树、完全二叉树、满二叉树、平衡二叉树(如AVL树和红黑树)、B树和B+树等,每种类型的树有其特定的性质和应用场景。 4. **树的数据生成**:生成树的数据通常涉及随机生成算法...

Global site tag (gtag.js) - Google Analytics