`
suhuanzheng7784877
  • 浏览: 706567 次
  • 性别: Icon_minigender_1
  • 来自: 北京
博客专栏
Ff8d036b-05a9-33b5-828a-2633bb68b7e6
读金庸故事,品程序人生
浏览量:47819
社区版块
存档分类
最新评论

Java基础复习笔记10数据结构-排序二叉树

阅读更多

1.       排序二叉树

排序二叉树是在二叉树的限制基础上又加了一些限制,所有的的树节点数据都具有可比较性质、树的根节点数据肯定都大于它的左子树中所有节点、树的根节点数据也都小于或者等于它的右子树的所有节点。同理这个棵树上的父节点都大于左节点,并且小于等于右节点。如下图所示。

 

就是一颗排序二叉树,对此树进行深度优先中根遍历法,那么会得到从小到大的排列顺序:12457101213141518

2.       使用场景

顾名思义,排序二叉树就是为了快速排序,查找元素时用的最多的。

3.       维护排序二叉树

构建一棵排序二叉树可能对于咱们来说不是什么难事,但是关键是维护好这颗排序二叉树。比如新增或者删除一个元素节点后,还能严格的保持这棵树是一颗排序二叉树。尤其是涉及到删除节点元素的时候,需要考虑的因素就比较多了比如删除一个节点后,得考虑这个节点是否有子节点,有几个子节点等等。

一般分为如下几个情况处理。

1):被删除的节点是叶子节点,没关系,不会影响大局,直接删除即可

2):被删节点只有左子树或者只有右子树,被删除的节点只有单子树的。直接将被删节点的子树赋给被删节点的父节点即可,也就是说被删节点的左子树代替被删节点成为被删结点父亲的左子树,而被删节点的右子树代替被删节点成为被删结点父亲的右子树。

3):被删节点既有左子树又有右字数,这种是比较麻烦的,也就是当不当、正不正只删除中间的节点。这个时候就要用被删节点最大左子树的节点或者用最小右子树的的节点代替被删节点。

添加节点:添加节点的过程实际上就是构建排序二叉树的过程。原理如下

1):首先有一个根节点

2):以根节点作为当前节点开始检索

3):新增节点和当前节点进行值比较

4):如果新节点比当前节点大,那么当前节点的右子节点作为新的当前节点,如果当前节点比当前节点小,那么当前节点的左子节点作为新的当前节点。

5):重复34步骤直到当前节点没有了子节点,那么新节点作为当前节点的子节点,具体作为左子节点还是有子节点得看新节点的值和当前节点值得比较。

4.       算法代码

实现创建排序二叉树以及维护排序二叉树的代码如下:

package dateStructer.tree.orderTree;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

/**
 * 排序二叉树
 * 
 * @author liuyan
 */
public class OrderTree {

	static class Node {
		Integer data;
		Node parent;
		Node left;
		Node right;

		public Node(Integer data, Node parent, Node left, Node right) {

			this.data = data;
			this.parent = parent;
			this.left = left;
			this.right = right;

		}

		@Override
		public String toString() {
			return "[data:" + this.data + "]";
		}

	}

	private Node root;

	public OrderTree(Integer data) {
		root = new Node(data, null, null, null);
	}

	/**
	 * 添加新节点
	 * 
	 * @param data
	 */
	public void addNode(Integer data) {

		if (root == null) {
			root = new Node(data, null, null, null);
			return;
		}

		// 从根节点开始
		Node nowNode = root;
		Node newParent = null;
		do {
			newParent = nowNode;
			if (nowNode.data > data) {
				nowNode = nowNode.left;
			} else {
				nowNode = nowNode.right;
			}

		} while (nowNode != null);

		if (newParent.data > data) {
			newParent.left = new Node(data, newParent, null, null);
		} else {
			newParent.right = new Node(data, newParent, null, null);
		}

	}

	/**
	 * 查找节点对象
	 * 
	 * @param data
	 * @return
	 */
	public Node findNode(Integer data) {

		Node nowNode = root;

		while (nowNode != null) {

			if (nowNode.data == data) {
				return nowNode;
			}

			if (nowNode.data > data) {
				nowNode = nowNode.left;
			} else {
				nowNode = nowNode.right;
			}

		}
		return null;

	}

	/**
	 * 删除节点
	 * 
	 * @param data
	 */
	public void deleteNode(Integer data) {
		Node tagNode = findNode(data);

		if (tagNode == null) {
			return;
		}
		if (tagNode == root) {
			root = null;
		}
		if (tagNode.left == null && tagNode.right == null) {
			if (tagNode.parent.left == tagNode) {
				tagNode.parent.left = null;
			} else if (tagNode.parent.right == tagNode) {
				tagNode.parent.right = null;
			}
			return;
		}
		if (tagNode.left == null && tagNode.right != null) {
			if (tagNode.parent.left == tagNode) {
				tagNode.parent.left = tagNode.right;
			} else if (tagNode.parent.right == tagNode) {
				tagNode.parent.right = tagNode.right;
			}
			return;
		}

		if (tagNode.left != null && tagNode.right == null) {
			if (tagNode.parent.left == tagNode) {
				tagNode.parent.left = tagNode.left;
			} else if (tagNode.parent.right == tagNode) {
				tagNode.parent.right = tagNode.left;
			}
			return;
		}

		Node leftMaxNode = tagNode.left;

		while (leftMaxNode.right != null) {
			leftMaxNode = leftMaxNode.right;
		}

		leftMaxNode.parent.right = null;
		leftMaxNode.parent = tagNode.parent;

		if (tagNode == tagNode.parent.left) {
			leftMaxNode.parent.left = leftMaxNode;
		} else {
			leftMaxNode.parent.right = leftMaxNode;
		}

		leftMaxNode.left = tagNode.left;
		leftMaxNode.right = tagNode.right;
		tagNode.left = null;
		tagNode.right = null;
		tagNode.parent = null;
	}

	public static List<Node> deepFirst(Node root) {

		List<Node> list = new ArrayList<Node>();
		Queue<Node> queue = new ArrayDeque<Node>();
		queue.add(root);

		while (!queue.isEmpty()) {

			list.add(queue.peek());

			Node twoLinkNode = queue.poll();

			if (twoLinkNode.left != null) {
				queue.add(twoLinkNode.left);
			}

			if (twoLinkNode.right != null) {
				queue.add(twoLinkNode.right);
			}
		}

		return list;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		OrderTree orderTree = new OrderTree(7);
		orderTree.addNode(4);
		orderTree.addNode(1);
		orderTree.addNode(2);
		orderTree.addNode(5);
		orderTree.addNode(5);
		orderTree.addNode(13);
		orderTree.addNode(10);
		orderTree.addNode(12);
		orderTree.addNode(15);
		orderTree.addNode(14);
		orderTree.addNode(18);
		System.out.println(deepFirst(orderTree.root));
		orderTree.deleteNode(4);
		System.out.println(deepFirst(orderTree.root));
	}
}

 运行后效果如下

[[data:7], [data:4], [data:13], [data:1], [data:5], [data:10], [data:15], [data:2], [data:5], [data:12], [data:14], [data:18]]
//删除后
[[data:7], [data:2], [data:13], [data:1], [data:5], [data:10], [data:15], [data:5], [data:12], [data:14], [data:18]]

 删除后的树形图应该如下



 

 

  • 大小: 35.9 KB
  • 大小: 31.2 KB
分享到:
评论

相关推荐

    Java基础复习笔记09数据结构-哈夫曼树

    ### Java基础复习笔记09数据结构-哈夫曼树 #### 1. 哈夫曼树概述 哈夫曼树是一种特殊的二叉树,它在计算机科学领域有着广泛的应用,尤其是在数据压缩方面。哈夫曼树也被称为最优二叉树,其构建原则是使得带权路径...

    Java基础复习笔记07数据结构-树的概述

    在Java编程中,数据结构是解决问题的关键工具之一,其中树是一种非常重要的非线性数据结构。本篇复习笔记主要关注树的概述,包括树的概念、基本操作、使用场景以及一种特殊的树实现——记父节点实现。 1. **树的...

    数据结构高分笔记part1

    7. **实际应用**:最后,笔记可能会将这些理论知识与实际编程语言(如C++、Java或Python)结合,通过示例代码解释如何实现这些数据结构和算法。 由于笔记名为“数据结构高分笔记”,它很可能会重点强调考试中的常见...

    JavaSE基础复习笔记

    ### JavaSE基础复习知识点 #### 1. 数组在内存中的存储状态 ...综上所述,Java的基础复习不仅仅是对语言特性的简单回顾,更重要的是深入理解其背后的实现原理和技术细节,从而更好地掌握Java编程的核心技能。

    408考试数据结构高分笔记2019版(天勤论坛)

    此外,笔记还会强调实际编程实现,包括C++或Java等语言的数据结构实现,如链表的插入、删除、遍历,树的构建与遍历,图的邻接矩阵和邻接表表示,以及各种排序和查找算法的代码实现。这部分内容有助于考生提升编程...

    数据结构算法Java实现。关于Java《数据结构算法》核心技术学习积累的例子,是初学者及核心技术巩固的最佳实践。.zip

    数据结构是计算机科学中...这个压缩包“my_resource”可能包含了上述所有知识点的相关文件,如笔记、代码示例、练习题解答等,是学习和复习数据结构算法的理想资源。记得深入学习和动手实践,以真正掌握这些重要概念。

    newreview_die4ix_Java数据结构_

    "newreview_die4ix_Java数据结构_"这个标题暗示了这是一个关于Java编程和数据结构复习的资源,可能包含了作者die4ix在学习或教学过程中整理的笔记、示例代码或测试题目。 描述中提到的“java基本编程的复习”涵盖了...

    java二叉树算法源码-Data_Structure_Note:《恋上数据结构》第1季度+第2季完整学习笔记,从0实现的Java数据结构大全

    至于怎么判断笔记是否翻新过,主要看前缀有没有《恋上数据结构第x季》 抛开学习数据结构的角度不说,恋上数据结构的每一份数据结构的代码都是健壮而又完善的,完全可以在业务中需要的时候直接拿来用。 我的《恋上...

    Java《剑指Offer》刷题笔记.zip

    1. **基础数据结构与算法**:Java中常见的数据结构如数组、链表、栈、队列、树(二叉树、平衡树如AVL和红黑树)以及图等是面试的基础。算法方面,排序(快速排序、归并排序、堆排序等)、查找(二分查找、哈希查找)...

    数据结构和算法课件笔记代码.zip

    这个压缩包“数据结构和算法课件笔记代码.zip”包含两部分主要内容:课件和代码。这些资源可以帮助学习者深入理解数据结构的原理和算法的实现。 首先,让我们详细讨论数据结构。数据结构是组织和存储数据的方式,以...

    清华大学内部数据结构讲解

    在“清华大学内部数据结构讲解”中,你可能会学到这些数据结构的实现细节,包括如何在C++或Java中创建和操作这些结构。此外,还会深入讨论各种操作的时间复杂度和空间复杂度,这是理解算法效率的关键。 接下来,会...

    天勤2019数据结构无水印可打印

    复习资料中可能还包括了编程语言与数据结构的结合,如C++或Java中的指针和对象,以及如何使用这些语言实现各种数据结构。理解数据结构的抽象数据类型(ADT)和其实现,比如用数组实现栈和队列,用链表实现集合和映射...

    2011数据结构其中.zip

    这个名为"2011数据结构其中.zip"的压缩包文件可能包含了一位学生或教师在2011年关于数据结构课程的学习资料,其中的文档"2011数据结构其中.doc"很可能是课程笔记、作业、讲义或者复习材料。 数据结构的基本概念包括...

    LeetCode刷题笔记.rar

    总的来说,《LeetCode刷题笔记》不仅记录了个人在LeetCode上的学习过程,也是对数据结构和算法的系统复习。通过刷题,我们可以不断提升自己的编程思维,提高解决问题的能力,为职场竞争增添砝码。无论是初学者还是...

    数据结构与算法.docx

    在给定的文件中,包含了对数据结构与算法的学习笔记,主要内容涵盖了稀疏数组、队列、链表、栈、树、图以及十大经典算法等方面的知识点。 首先,稀疏数组是一种特殊的数据结构,它是对二维数组中大量零元素的优化...

    (CPT101)的笔记汇总.zip

    数据结构是存储和组织数据的方式,包括数组、链表、栈、队列、树(如二叉树、堆)和图等。学习数据结构能帮助优化算法,提高程序效率。在CPT101中,学会长期和临时存储数据的方法至关重要。 四、函数与模块化编程 ...

    技术面试必备知识点.zip

    在准备技术面试时,数据结构是必不可少的知识领域,无论你是C、C++、Java还是Python开发者。本压缩包“技术面试必备知识点.zip”提供了一套全面的学习资源,旨在帮助大学生和初学者深入理解和掌握数据结构的基本概念...

    考试类精品--王道考研机试指南的代码合集,附有一些笔记和感悟.zip

    3. **数据结构**:如链表、栈、队列、树(二叉树、平衡树等)、图、哈希表等。这些是解决复杂问题的基础,压缩包中可能包含它们的实现和应用场景。 4. **编程技巧**:如优化代码效率、调试技巧、程序设计模式等,...

Global site tag (gtag.js) - Google Analytics