`
zhaohaolin
  • 浏览: 1012556 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

Java数据结构和算法--树

阅读更多

(1)二叉树 

Java代码  收藏代码
  1. package ChapterEight;  
  2.   
  3. class Tree {  
  4.     class Node {  
  5.         public long value;  
  6.   
  7.         public Node leftChild;  
  8.   
  9.         public Node rightChild;  
  10.   
  11.         public Node(long value) {  
  12.             this.value = value;  
  13.             leftChild = null;  
  14.             rightChild = null;  
  15.         }  
  16.     }  
  17.   
  18.     public Node root;  
  19.   
  20.     public Tree() {  
  21.         root = null;  
  22.     }  
  23.   
  24.     // 向树中插入一个节点  
  25.     public void insert(long value) {  
  26.         Node newNode = new Node(value);  
  27.         // 树是空的  
  28.         if (root == null)  
  29.             root = newNode;  
  30.         else {  
  31.             Node current = root;  
  32.             Node parentNode;  
  33.             while (true) {  
  34.                 parentNode = current;  
  35.                 if (value < current.value) {  
  36.                     current = current.leftChild;  
  37.                     // 要插入的节点为左孩子节点  
  38.                     if (current == null) {  
  39.                         parentNode.leftChild = newNode;  
  40.                         return;  
  41.                     }  
  42.                 } else {  
  43.                     // 要插入的节点为右孩子节点  
  44.                     current = current.rightChild;  
  45.                     if (current == null) {  
  46.                         parentNode.rightChild = newNode;  
  47.                         return;  
  48.                     }  
  49.                 }  
  50.             }  
  51.         }  
  52.     }  
  53.   
  54.     // 先续遍历树中的所有节点  
  55.     public void preOrder(Node currentRoot) {  
  56.         if (currentRoot != null) {  
  57.             System.out.print(currentRoot.value + " ");  
  58.             preOrder(currentRoot.leftChild);  
  59.             preOrder(currentRoot.rightChild);  
  60.         }  
  61.     }  
  62.   
  63.     // 中续遍历树中的所有节点  
  64.     public void inOrder(Node currentNode) {  
  65.         if (currentNode != null) {  
  66.             inOrder(currentNode.leftChild);  
  67.             System.out.print(currentNode.value + " ");  
  68.             inOrder(currentNode.rightChild);  
  69.         }  
  70.     }  
  71.   
  72.     // 后续遍历树中的所有节点  
  73.     public void postOrder(Node currentNode) {  
  74.         if (currentNode != null) {  
  75.             postOrder(currentNode.leftChild);  
  76.             postOrder(currentNode.rightChild);  
  77.             System.out.print(currentNode.value + " ");  
  78.         }  
  79.     }  
  80.   
  81.     public void traverse(int traverseType) {  
  82.         switch (traverseType) {  
  83.         case 1:  
  84.             preOrder(root);  
  85.             break;  
  86.         case 2:  
  87.             inOrder(root);  
  88.             break;  
  89.         case 3:  
  90.             postOrder(root);  
  91.             break;  
  92.         default:  
  93.             break;  
  94.         }  
  95.     }  
  96.   
  97.     // 依据树节点的值删除树中的一个节点  
  98.     public boolean delete(int value) {  
  99.         // 遍历树过程中的当前节点  
  100.         Node current = root;  
  101.         // 要删除节点的父节点  
  102.         Node parent = root;  
  103.         // 记录树的节点为左孩子节点或右孩子节点  
  104.         boolean isLeftChild = true;  
  105.         while (current.value != value) {  
  106.             parent = current;  
  107.             // 要删除的节点在当前节点的左子树里  
  108.             if (value < current.value) {  
  109.                 isLeftChild = true;  
  110.                 current = current.leftChild;  
  111.             }  
  112.             // 要删除的节点在当前节点的右子树里  
  113.             else {  
  114.                 isLeftChild = false;  
  115.                 current = current.rightChild;  
  116.             }  
  117.             // 在树中没有找到要删除的节点  
  118.             if (current == null)  
  119.                 return false;  
  120.         }  
  121.         // 要删除的节点为叶子节点  
  122.         if (current.leftChild == null && current.rightChild == null) {  
  123.             // 要删除的节点为根节点  
  124.             if (current == root)  
  125.                 root = null;  
  126.             // 要删除的节点为左孩子节点  
  127.             else if (isLeftChild)  
  128.                 parent.leftChild = null;  
  129.             // 要删除的节点为右孩子节点  
  130.             else  
  131.                 parent.rightChild = null;  
  132.         }  
  133.         // 要删除的节点有左孩子节点,没有右孩子节点  
  134.         else if (current.rightChild == null) {  
  135.             // 要删除的节点为根节点  
  136. font-size: 1em; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 38px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 10px; bord
    分享到:
    评论

相关推荐

    java数据结构和算法--第二版

    java数据结构和算法--第二版

    Java数据结构和算法-带书签目录扫描版

    《Java数据结构和算法-带书签目录扫描版》是一本深入探讨Java编程语言中数据结构和算法的书籍。此扫描版特别包含了完整的书签目录,使得读者在电子版阅读时能够快速定位到所需章节,提高了学习和查阅的效率。 在...

    Java数据结构和算法-第二版-高清扫描版-带目录书签

    《Java数据结构和算法》第二版是一本深入探讨Java编程中数据结构与算法的权威书籍。这本书涵盖了在软件开发中至关重要的基础知识,旨在帮助程序员提升解决问题的能力和代码效率。高清扫描版提供了清晰的文本和图表,...

    JAVA数据结构与算法-第二版

    总之,《JAVA数据结构与算法-第二版》是一本全面、深入的教程,适合Java程序员、计算机科学学生和对算法有兴趣的读者。通过阅读和实践书中的内容,读者不仅可以提高编程技能,还能培养解决复杂问题的能力,为未来在...

    java数据结构与算法.pdf

    Java作为广泛应用的编程语言,其在实现数据结构和算法时有着丰富的库支持和优秀的可读性。下面将对标题和描述中提到的一些关键知识点进行详细解释。 1. **数据结构**: - **稀疏数组**:当大量数据中大部分为零或...

    Java数据结构和算法

    Java数据结构和算法 Java数据结构和算法 Java数据结构和算法 Java数据结构和算法 Java数据结构和算法 Java数据结构和算法 Java数据结构和算法 Java数据结构和算法

    数据结构与算法--Java语言描述

    学习“数据结构与算法--Java语言描述”,不仅能够理解各种数据结构的内部工作原理,还能学会如何用Java来实现它们,这对于软件开发、系统分析和算法竞赛等领域都有极大的帮助。通过深入学习和实践,我们不仅可以提升...

    数据结构与算法-java

    以下是基于标题“数据结构与算法-java”及描述中提到的“数据结构与算法分析_Java语言描述高清版(第2版)1.pdf”所涵盖的一些关键知识点: 1. **数据结构**: - **数组**:最基础的数据结构,存储固定大小的同类型...

    Java数据结构和算法.pdf

    资源摘要信息是关于Java数据结构和算法的知识点总结,涵盖了数组、栈与队列、链表、递归、哈希表、高级排序、二叉树、红黑树、堆、带权图等数据结构和算法概念。 一、数组 * 数组是相同类型变量的集合,可以使用...

    Java数据结构和算法中文第二版

    根据提供的信息,“Java数据结构和算法中文第二版”这本书主要关注的是数据结构与算法的相关内容。下面将基于这些信息,详细介绍数据结构与算法的核心概念、重要性和应用领域,以及在Java编程环境中如何实现这些概念...

    Java数据结构和算法-学习笔记

    本文基于《Java数据结构与算法》的学习笔记,旨在帮助读者更好地理解和掌握这些核心概念。 #### 二、数据结构概述 数据结构是指一组数据的集合以及它们之间的关系,以及在这组数据上定义的操作。常见的数据结构包括...

    Java数据结构和算法(第二版)+源代码+Applets

    Java数据结构和算法是计算机科学中的核心概念,对于任何Java开发者来说,理解和掌握它们都是至关重要的。本资源包“Java数据结构和算法(第二版)+源代码+Applets”为学习者提供了一个全面且深入的学习平台,涵盖了...

    数据结构与算法-Java语言版

    主要内容包括:面向对象编程的基本原理,判定算法效率的方法,堆栈、队列及其应用,对于多种递归的详细讨论,二叉树、B树、2-4树等的查找和遍历等,分析排序、散列等数据结构的应用,图、NP完整性,数据压缩算法、...

    java版数据结构和算法视频

    Java数据结构和算法第七讲.avi Java数据结构和算法第三十一讲.avi Java数据结构和算法第三十七讲.avi Java数据结构和算法第三十三讲.avi Java数据结构和算法第三十九讲.avi Java数据结构和算法第三十二讲.avi Java...

    Java数据结构和算法(第二版).zip

    《Java数据结构和算法》(第2版)介绍了计算机编程中使用的数据结构和算法,对于在计算机应用中如何操作和管理数据以取得最优性能提供了深入浅出的讲解。全书共分为15章,分别讲述了基本概念、数组、简单排序、堆和...

    C、C++、JAVA数据结构与算法电子书

    C、C++和Java都是广泛使用的编程语言,它们在处理数据结构和算法时各有特点。以下是对这三种语言在数据结构与算法方面的一些关键知识点的详细阐述: 1. **数据结构**: - **数组**:基本的数据结构,用于存储同...

    java数据结构和算法学习笔记

    ### Java数据结构与算法学习笔记知识点总结 #### 一、数据结构概述 数据结构是对数据的一种组织形式,它决定了数据的存储方式以及处理数据的方法。常见的数据结构包括但不限于数组、链表、栈、队列、二叉树、图等...

    数据结构与算法----C#版

    虽然有许许多多关于数据结构与算法的书籍,但是这些书籍通常都是大学教材,而且是用在大学里经典讲授的Java语言或C++语言编写的。C#语言正在成为一种广受欢迎的编程语言。这本书为C#语言程序员提供了学习基础数据...

    Java数据结构和算法(第二版)+随书源代码+applet小程序

    《Java数据结构和算法(第二版)》是一本专为希望深入理解Java编程中的数据结构与算法的读者设计的书籍。这本书的特点是从基础知识逐步引导读者进入复杂领域,通过结合实际的Applet小程序,使得理论知识变得生动直观。...

Global site tag (gtag.js) - Google Analytics