`
啸笑天
  • 浏览: 3465687 次
  • 性别: Icon_minigender_1
  • 来自: China
社区版块
存档分类
最新评论

【code】java实现排序二叉树

阅读更多

 

import java.util.*;

public class SortedBinTree<T extends Comparable>
{
	static class Node
	{
		Object data;
		Node parent; 
		Node left;
		Node right;
		public Node(Object data , Node parent 
			, Node left , Node right)
		{
			this.data = data;
			this.parent = parent;
			this.left = left;
			this.right = right;
		}
		public String toString()
		{
			return "[data=" + data + "]"; 
		}
		public boolean equals(Object obj)
		{
			if (this == obj)
			{
				return true;
			}
			if (obj.getClass() == Node.class)
			{
				Node target = (Node)obj;
				return data.equals(target.data)
					&& left == target.left
					&& right == target.right
					&& parent == target.parent;
			}
			return false;
		}
	}
	private Node root;
	//两个构造器用于创建排序二叉树
	public SortedBinTree()
	{
		root = null;
	}
	public SortedBinTree(T o)
	{
		root = new Node(o , null , null , null);
	}
	//添加节点
	public void add(T ele)
	{
		//如果根节点为null
		if (root == null)
		{
			root = new Node(ele , null , null , null);
		}
		else
		{
			Node current = root;
			Node parent = null;
			int cmp = 0;
			//搜索合适的叶子节点,以该叶子节点为父节点添加新节点
			do
			{
				parent = current;
				cmp = ele.compareTo(current.data);
				//如果新节点的值大于当前节点的值
				if (cmp > 0)
				{
					//以右子节点作为当前节点
					current = current.right;
				}
				//如果新节点的值小于当前节点的值
				else
				{
					//以左子节点作为当前节点
					current = current.left;
				}
			}
			while (current != null);
			//创建新节点
			Node newNode = new Node(ele , parent , null , null);
			//如果新节点的值大于父节点的值
			if (cmp > 0)
			{
				//新节点作为父节点的右子节点
				parent.right = newNode;
			}
			//如果新节点的值小于父节点的值
			else
			{
				//新节点作为父节点的左子节点
				parent.left = newNode;
			}
		}
	}
	//删除节点,采用的是11. 25图的左边情形
	public void remove(T ele)
	{
		//获取要删除的节点
		Node target = getNode(ele);
		if (target == null)
		{
			return;
		}
		//左、右子树为空
		if (target.left == null
			&& target.right == null)
		{
			//被删除节点是根节点
			if (target == root)
			{
				root = null;
			}
			else
			{
				//被删除节点是父节点的左子节点
				if (target == target.parent.left)
				{
					//将target的父节点的left设为null
					target.parent.left = null;
				}
				else
				{
					//将target的父节点的right设为null
					target.parent.right = null;
				}
				target.parent = null;
			}
		}
		//左子树为空,右子树不为空
		else if (target.left == null
			&& target.right != null)
		{
			//被删除节点是根节点
			if (target == root)
			{
				root = target.right;
			}
			else
			{
				//被删除节点是父节点的左子节点
				if (target == target.parent.left)
				{
					//让target的父节点的left指向target的右子树
					target.parent.left = target.right;
				}
				else
				{
					//让target的父节点的right指向target的右子树
					target.parent.right = target.right;
				}
				//让target的右子树的parent指向target的parent
				target.right.parent = target.parent;
			}
		}
		//左子树不为空,右子树为空
		else if(target.left != null
			&& target.right == null)
		{
			//被删除节点是根节点
			if (target == root)
			{
				root = target.left;
			}
			else
			{
				//被删除节点是父节点的左子节点
				if (target == target.parent.left)
				{
					//让target的父节点的left指向target的左子树
					target.parent.left = target.left;
				}
				else
				{
					//让target的父节点的right指向target的左子树
					target.parent.right = target.left;
				}
				//让target的左子树的parent指向target的parent
				target.left.parent = target.parent;
			}
		}
		//左、右子树都不为空
		else
		{
			//leftMaxNode用于保存target节点的左子树中值最大的节点
			Node leftMaxNode = target.left;
			//搜索target节点的左子树中值最大的节点
			while (leftMaxNode.right != null)
			{
				leftMaxNode = leftMaxNode.right;
			}
			//从原来的子树中删除leftMaxNode节点
			leftMaxNode.parent.right = null;
			//让leftMaxNode的parent指向target的parent
			leftMaxNode.parent = target.parent;
			//被删除节点是父节点的左子节点
			if (target == target.parent.left)
			{
				//让target的父节点的left指向leftMaxNode
				target.parent.left = leftMaxNode;
			}
			else
			{
				//让target的父节点的right指向leftMaxNode
				target.parent.right = leftMaxNode;
			}
			leftMaxNode.left = target.left;
			leftMaxNode.right = target.right;
			target.parent = target.left = target.right = null;//删除原来的节点
		}
	}
	//根据给定的值搜索节点
	public Node getNode(T ele)
	{
		//从根节点开始搜索
		Node p = root;
		while (p != null) 
		{
			int cmp = ele.compareTo(p.data);
			//如果搜索的值小于当前p节点的值
			if (cmp < 0)
			{
				//向左子树搜索
				p = p.left;
			}
			//如果搜索的值大于当前p节点的值
			else if (cmp > 0)
			{
				//向右子树搜索
				p = p.right;
			}
			else
			{
				return p;
			}
		}
		return null;
	}
	//广度优先遍历
	public List<Node> breadthFirst()
	{
		Queue<Node> queue = new ArrayDeque<Node>();
		List<Node> list = new ArrayList<Node>();
		if( root != null)
		{
			//将根元素加入“队列”
			queue.offer(root);
		}
		while(!queue.isEmpty())
		{
			//将该队列的“队尾”的元素添加到List中
			list.add(queue.peek());
			Node p = queue.poll();
			//如果左子节点不为null,将它加入“队列”
			if(p.left != null)
			{
				queue.offer(p.left);
			}
			//如果右子节点不为null,将它加入“队列”
			if(p.right != null)
			{
				queue.offer(p.right);
			}
		}
		return list;
	}
	
	//实现中序遍历  
    public List<Node> inIterator()  
    {  
        return inIterator(root);  
    }  
    private List<Node> inIterator(Node node)  
    {  
        List<Node> list = new ArrayList<Node>();  
        //递归处理左子树  
        if (node.left != null)  
        {  
            list.addAll(inIterator(node.left));  
        }  
        //处理根节点  
        list.add(node);  
        //递归处理右子树  
        if (node.right != null)  
        {  
            list.addAll(inIterator(node.right));  
        }  
        return list;  
    }  
	
	public static void main(String[] args) 
	{
		SortedBinTree<Integer> tree 
			= new SortedBinTree<Integer>();
		//添加节点
		tree.add(5);
		tree.add(20);
		tree.add(10);
		tree.add(3);
		tree.add(8);
		tree.add(15);
		tree.add(30);
		System.out.println(tree.breadthFirst());
		//删除节点
		tree.remove(20);
		System.out.println(tree.breadthFirst());
		
	}
}
 

 

 




 

 

  • 大小: 154.9 KB
  • 大小: 136.2 KB
  • 大小: 117.2 KB
分享到:
评论
1 楼 pseudocodes 2011-09-18  
删除算法左右子树不为空的情况感觉有问题

相关推荐

    Java各种排序算法代码.zip

    这个名为"Java各种排序算法代码.zip"的压缩包包含了一系列实现不同排序算法的Java源代码。排序算法是计算机科学中的基本概念,用于对一组数据进行排列。下面将详细讨论这些算法及其在Java中的实现。 1. 冒泡排序...

    java 数据结构code

    3. pBinTreeStringWR.class 和 pBinTreeIntegerWR.class:这些可能表示基于字符串和整数的二叉树实现,可能用于搜索、插入和删除操作。"WR"可能是“Writeable”或类似含义,表示这些类支持对树数据结构的写入操作。 ...

    java排序算法总结

    堆排序是一种基于比较的排序算法,它利用了完全二叉树的特性,通过构建最大(或最小)堆来实现排序。在Java中,堆排序通常使用`PriorityQueue`类实现,具有O(n log n)的时间复杂度,但不稳定性较差。 接下来是归并...

    基于Huffman编码压缩软件(java实现)

    `HuffmanCode.java`则负责生成Huffman编码,这通常通过遍历Huffman树并跟踪从根节点到每个叶子节点的路径来完成。每条路径可以被映射到一个唯一的二进制码,形成字符与编码的对应关系。 `CompressFrame.java`和`...

    堆排序详解升序和降序Java版本

    在Java中,实现堆排序通常涉及构建堆和进行排序两个主要步骤。 一、堆排序的基本原理 1. 建堆:首先将无序序列构建成一个大顶堆(升序时)或小顶堆(降序时)。对于大顶堆,根节点的值是整个堆中最大的,而小顶堆...

    data structures with java source code

    Java的java.util.PriorityQueue类实现了这个概念,可以用来实现堆排序等算法。 6. **堆(Heap)**:堆是一种特殊的树形数据结构,满足最大堆或最小堆的性质,即父节点的值总是大于或小于其子节点的值。Java的java....

    算法实践(JavaScript & Java),排序,查找、树、两指针、动态规划等

    本资源包"算法实践(JavaScript & Java),排序,查找、树、两指针、动态规划等"涵盖了编程中的多个重要概念,旨在帮助开发者提升算法设计与实现能力。接下来,我们将详细探讨这些知识点。 1. **动态规划**: 动态...

    Java_Programming_classic_tree_parameter_code.rar_java programmin

    本资源“Java_Programming_classic_tree_parameter_code.rar”包含了一个名为“Java编程开发树参数经典代码.java”的文件,它很可能包含了实现树结构及其操作的示例代码。下面我们将深入探讨树数据结构的基本概念、...

    Java版 赫夫曼编码计算程序

    Java版的赫夫曼编码计算程序是一个用于数据压缩的实用工具,它基于赫夫曼树(也称为最优二叉树)...通过阅读和分析`HuffmanCode.java`的源代码,我们可以学习到如何在Java中实现这些概念,并进一步提升我们的编程能力。

    HuffmanCode_huffman编码java_huffman_

    在Java中实现哈夫曼编码,首先需要理解面向对象的思想。面向对象编程(Object-Oriented Programming, OOP)是Java的核心特性,它将数据和操作数据的方法封装在一起,形成对象。在哈夫曼编码的实现中,我们可以创建三...

    Cracking-the-code-interview-solution-java.rar_The Interview_crac

    例如,链表操作可以用于实现LRU缓存,二叉树可以用于搜索和排序问题。 算法是解决问题的有效工具,面试中经常涉及排序(快速排序、归并排序、堆排序等)、查找(线性查找、二分查找)、动态规划、贪心算法、回溯法...

    Java软件结构 设计和使用数据结构

    二叉树是每个节点最多有两个子节点的数据结构,广泛应用于搜索和排序。红黑树是一种自平衡的二叉查找树,确保插入和删除操作的时间复杂度为O(log n)。 "ch09 Code"和"ch11 Code"可能包含散列表(HashMap)的实现和...

    Java程序

    - **堆排序(Heap Sort)**: 堆排序是一种基于比较的排序算法,其核心是利用完全二叉树(堆)的性质来进行排序。在示例代码中,使用了最小堆(min heap)对节点进行了排序,以便构建哈夫曼树。 - **构建最小堆**: ...

    Code-for-binary-tree.zip_tree

    "Code for binary tree"这个压缩包可能包含了用不同编程语言实现的二叉树操作代码,比如插入、删除、搜索和遍历等操作。常见的编程语言如C++、Java、Python等都有相应的二叉树数据结构实现。通过阅读和理解这些代码...

    数据结构与问题分析 java 源代码

    `Tree`相关文件(如`TestTreeIterators.java`)可能涉及二叉树、平衡树(如AVL树或红黑树)等,它们在搜索、排序和其他操作中非常高效。 2. **问题分析**:这是理解算法复杂性和性能的过程。`Sort.java`可能是对...

    java源码结构-Java-data-structure-source-code:Java数据结构

    这个压缩包文件“Java-data-structure-source-code”很可能包含了一些经典的Java实现的数据结构,如数组、链表、栈、队列、树、图等。下面将详细介绍这些常见的数据结构以及它们在Java中的实现。 1. **数组**:数组...

    Java_算法和数据结构的集合.zip

    "codelibrary_main.zip"这个名字暗示了一个代码库,可能包含了各种算法和数据结构的Java实现。这个子压缩包可能包含分门别类的目录,每个目录对应一种或多种算法或数据结构,如排序算法(快速排序、归并排序、冒泡...

    Algorithm-codelibrary.zip

    在"Algorithm-codelibrary.zip"中,你可以找到各种经典算法的实现,如搜索算法(二分查找、广度优先搜索、深度优先搜索)、排序算法(冒泡排序、快速排序、归并排序)以及图算法(Dijkstra算法、Floyd-Warshall算法...

    java算法大全源码包

    Java算法大全源码包是一个集合了多种经典算法实现的资源包,主要面向Java开发者,旨在帮助他们提升在算法设计和实现方面的技能。这个资源包很可能包含了各种数据结构、排序算法、搜索算法以及其他实用的编程技巧。...

Global site tag (gtag.js) - Google Analytics