`

二叉树的Java实现

 
阅读更多
package com.pskfire.binTreeExample;

// tree.java
// demonstrates binary tree
// to run this program: C>java TreeApp
import java.io.*;
import java.util.*; // for Stack class
////////////////////////////////////////////////////////////////

class Node {
	public int iData; // data item (key)
	public double dData; // data item
	public Node leftChild; // this node's left child
	public Node rightChild; // this node's right child

	public void displayNode() // display ourself
	{
		System.out.print('{');
		System.out.print(iData);
		System.out.print(", ");
		System.out.print(dData);
		System.out.print("} ");
	}
} // end class Node
// //////////////////////////////////////////////////////////////

class Tree {
	private Node root; // first node of tree

	// -------------------------------------------------------------
	public Tree() // constructor
	{
		root = null;
	} // no nodes in tree yet
		// -------------------------------------------------------------

	public Node find(int key) // find node with given key
	{ // (assumes non-empty tree)
		Node current = root; // start at root
		while (current.iData != key) // while no match,
		{
			if (key < current.iData) // go left?
				current = current.leftChild;
			else
				// or go right?
				current = current.rightChild;
			if (current == null) // if no child,
				return null; // didn't find it
		}
		return current; // found it
	} // end find()
	
	public Node find2(int key) {
		Node current = root;
		
		while(current.iData != key) {
			if(key < current.iData) {
				current = current.leftChild;
			} else {
				current = current.rightChild;
			}
			
			if(current == null) {
				return null;
			}
		}
		
		return current;
	}
		// -------------------------------------------------------------

	public void insert(int id, double dd) {
		Node newNode = new Node(); // make new node
		newNode.iData = id; // insert data
		newNode.dData = dd;
		if (root == null) // no node in root
			root = newNode;
		else // root occupied
		{
			Node current = root; // start at root
			Node parent;
			while (true) // (exits internally)
			{
				parent = current;
				if (id < current.iData) // go left?
				{
					current = current.leftChild;
					if (current == null) // if end of the line,
					{ // insert on left
						parent.leftChild = newNode;
						return;
					}
				} // end if go left
				else // or go right?
				{
					current = current.rightChild;
					if (current == null) // if end of the line
					{ // insert on right
						parent.rightChild = newNode;
						return;
					}
				} // end else go right
			} // end while
		} // end else not root
	} // end insert()
	
	public void insert2(int id, double dd) {
		Node newNode = new Node();
		newNode.iData = id;
		newNode.dData = dd;
		if(root == null) {
			root = newNode;
		} else {
			Node current = root;
			Node parent;
			
			while (true) {
				parent = current;
				if(id < current.iData) {
					current = current.leftChild;
					if(current == null) {
						parent.leftChild = newNode;
						return;
					}
				} else {
					current = current.rightChild;
					if(current == null) {
						parent.rightChild = newNode;
						return;
					}
				}
			}
		}
	}
		// -------------------------------------------------------------

	public boolean delete(int key) // delete node with given key
	{ // (assumes non-empty list)
		Node current = root;
		Node parent = root;
		boolean isLeftChild = true;

		while (current.iData != key) // search for node
		{
			parent = current;
			if (key < current.iData) // go left?
			{
				isLeftChild = true;
				current = current.leftChild;
			} else // or go right?
			{
				isLeftChild = false;
				current = current.rightChild;
			}
			if (current == null) // end of the line,
				return false; // didn't find it
		} // end while
			// found node to delete

		// if no children, simply delete it
		if (current.leftChild == null && current.rightChild == null) {
			if (current == root) // if root,
				root = null; // tree is empty
			else if (isLeftChild)
				parent.leftChild = null; // disconnect
			else
				// from parent
				parent.rightChild = null;
		}

		// if no right child, replace with left subtree
		else if (current.rightChild == null)
			if (current == root)
				root = current.leftChild;
			else if (isLeftChild)
				parent.leftChild = current.leftChild;
			else
				parent.rightChild = current.leftChild;

		// if no left child, replace with right subtree
		else if (current.leftChild == null)
			if (current == root)
				root = current.rightChild;
			else if (isLeftChild)
				parent.leftChild = current.rightChild;
			else
				parent.rightChild = current.rightChild;

		else // two children, so replace with inorder successor
		{
			// get successor of node to delete (current)
			Node successor = getSuccessor(current);

			// connect parent of current to successor instead
			if (current == root)
				root = successor;
			else if (isLeftChild)
				parent.leftChild = successor;
			else
				parent.rightChild = successor;

			// connect successor to current's left child
			successor.leftChild = current.leftChild;
		} // end else two children
			// (successor cannot have a left child)
		return true; // success
	} // end delete()
		// -------------------------------------------------------------
		// returns node with next-highest value after delNode
		// goes to right child, then right child's left descendents

	private Node getSuccessor(Node delNode) {
		Node successorParent = delNode;
		Node successor = delNode;
		Node current = delNode.rightChild; // go to right child
		while (current != null) // until no more
		{ // left children,
			successorParent = successor;
			successor = current;
			current = current.leftChild; // go to left child
		}
		// if successor not
		if (successor != delNode.rightChild) // right child,
		{ // make connections
			successorParent.leftChild = successor.rightChild;
			successor.rightChild = delNode.rightChild;
		}
		return successor;
	}

	// -------------------------------------------------------------
	public void traverse(int traverseType) {
		switch (traverseType) {
		case 1:
			System.out.print("\nPreorder traversal: ");
			preOrder(root);
			break;
		case 2:
			System.out.print("\nInorder traversal:  ");
			inOrder(root);
			break;
		case 3:
			System.out.print("\nPostorder traversal: ");
			postOrder(root);
			break;
		}
		System.out.println();
	}

	// -------------------------------------------------------------
	private void preOrder(Node localRoot) {
		if (localRoot != null) {
			System.out.print(localRoot.iData + " ");
			preOrder(localRoot.leftChild);
			preOrder(localRoot.rightChild);
		}
	}

	// -------------------------------------------------------------
	private void inOrder(Node localRoot) {
		if (localRoot != null) {
			inOrder(localRoot.leftChild);
			System.out.print(localRoot.iData + " ");
			inOrder(localRoot.rightChild);
		}
	}

	// -------------------------------------------------------------
	private void postOrder(Node localRoot) {
		if (localRoot != null) {
			postOrder(localRoot.leftChild);
			postOrder(localRoot.rightChild);
			System.out.print(localRoot.iData + " ");
		}
	}

	// -------------------------------------------------------------
	public void displayTree() {
		Stack globalStack = new Stack();
		globalStack.push(root);
		int nBlanks = 32;
		boolean isRowEmpty = false;
		System.out
				.println("......................................................");
		while (isRowEmpty == false) {
			Stack localStack = new Stack();
			isRowEmpty = true;

			for (int j = 0; j < nBlanks; j++)
				System.out.print(' ');

			while (globalStack.isEmpty() == false) {
				Node temp = (Node) globalStack.pop();
				if (temp != null) {
					System.out.print(temp.iData);
					localStack.push(temp.leftChild);
					localStack.push(temp.rightChild);

					if (temp.leftChild != null || temp.rightChild != null)
						isRowEmpty = false;
				} else {
					System.out.print("--");
					localStack.push(null);
					localStack.push(null);
				}
				for (int j = 0; j < nBlanks * 2 - 2; j++)
					System.out.print(' ');
			} // end while globalStack not empty
			System.out.println();
			nBlanks /= 2;
			while (localStack.isEmpty() == false)
				globalStack.push(localStack.pop());
		} // end while isRowEmpty is false
		System.out
				.println("......................................................");
	} // end displayTree()
		// -------------------------------------------------------------
} // end class Tree
// //////////////////////////////////////////////////////////////

class TreeApp {
	public static void main(String[] args) throws IOException {
		int value;
		Tree theTree = new Tree();

		theTree.insert(50, 1.5);
		theTree.insert(25, 1.2);
		theTree.insert(75, 1.7);
		theTree.insert(12, 1.5);
		theTree.insert(37, 1.2);
		theTree.insert(43, 1.7);
		theTree.insert(30, 1.5);
		theTree.insert(33, 1.2);
		theTree.insert(87, 1.7);
		theTree.insert(93, 1.5);
		theTree.insert(97, 1.5);

		while (true) {
			System.out.print("Enter first letter of show, ");
			System.out.print("insert, find, delete, or traverse: ");
			int choice = getChar();
			switch (choice) {
			case 's':
				theTree.displayTree();
				break;
			case 'i':
				System.out.print("Enter value to insert: ");
				value = getInt();
				theTree.insert(value, value + 0.9);
				break;
			case 'f':
				System.out.print("Enter value to find: ");
				value = getInt();
				Node found = theTree.find(value);
				if (found != null) {
					System.out.print("Found: ");
					found.displayNode();
					System.out.print("\n");
				} else
					System.out.print("Could not find ");
				System.out.print(value + '\n');
				break;
			case 'd':
				System.out.print("Enter value to delete: ");
				value = getInt();
				boolean didDelete = theTree.delete(value);
				if (didDelete)
					System.out.print("Deleted " + value + '\n');
				else
					System.out.print("Could not delete ");
				System.out.print(value + '\n');
				break;
			case 't':
				System.out.print("Enter type 1, 2 or 3: ");
				value = getInt();
				theTree.traverse(value);
				break;
			default:
				System.out.print("Invalid entry\n");
			} // end switch
		} // end while
	} // end main()
		// -------------------------------------------------------------

	public static String getString() throws IOException {
		InputStreamReader isr = new InputStreamReader(System.in);
		BufferedReader br = new BufferedReader(isr);
		String s = br.readLine();
		return s;
	}

	// -------------------------------------------------------------
	public static char getChar() throws IOException {
		String s = getString();
		return s.charAt(0);
	}

	// -------------------------------------------------------------
	public static int getInt() throws IOException {
		String s = getString();
		return Integer.parseInt(s);
	}
	// -------------------------------------------------------------
} // end class TreeApp
// //////////////////////////////////////////////////////////////
分享到:
评论

相关推荐

    数据结构-二叉树Java实现及其遍历算法

    数据结构-二叉树Java实现及其遍历算法,代码示例中实现了中序遍历,简单易学。

    二叉树java实现

    在Java中实现二叉树,我们可以自定义一个类来表示树节点,并通过节点之间的连接来构建整个树形结构。这篇博客主要讨论了如何在Java中实现二叉树的基本操作,包括递归和非递归方式的三种遍历顺序:前序遍历、中序遍历...

    平衡二叉树

    平衡二叉树Java实现,平衡二叉树Java实现,平衡二叉树Java实现,平衡二叉树Java实现,

    二叉树的java实现

    二叉树的java实现

    数据结构-二叉树 JAVA语言实现

    总结来说,理解和掌握二叉树以及如何用JAVA实现它们是成为优秀程序员的关键一步。通过实践,你可以更深入地了解数据结构的精髓,提升算法设计能力,并为解决复杂问题打下坚实基础。对于初学者,可以从简单的二叉树...

    数据结构 二叉树 java图形界面实现

    本文将深入探讨“数据结构 二叉树 java图形界面实现”这一主题,主要围绕二叉树的基本概念、常见操作以及如何在Java环境中结合图形界面进行实现。 首先,二叉树是一种非线性的数据结构,每个节点最多有两个子节点,...

    Java创建二叉树java

    代码实现: 二叉树的查找、插入、删除和输出根节点到当前节点的路径 二叉树的前序遍历,中序遍历和后续遍历 TreeNode.java --定义树节点 Mytree.java----创建树结构和上述功能函数 TestTree.java --测试上述的功能

    java 二叉树实现

    java二叉树实现 (简单实现,入门用) /**创建二叉树*/ public BinaryTree createTree(String treeStr); /**寻找结点*/ public BinaryTree findNode(BinaryTree tree ,char sign); /**找所给结点的左子树*/ ...

    遍历二叉树(java实现)

    后序遍历的Java实现通常使用栈来辅助操作: ```java public void postOrderTraversal(TreeNode node) { if (node == null) return; Stack&lt;TreeNode&gt; stack = new Stack(); TreeNode prev = null; while (node...

    Java实现二叉树的遍历

    java实现二叉树非递归前序中序后序遍历

    基于JAVA开发的二叉树课程设计与实现

    在本项目中,“基于JAVA开发的二叉树课程设计与实现”主要涵盖了计算机科学中的数据结构和算法领域,特别是关于二叉树的理论知识、Java编程语言的应用以及软件工程的基本实践。二叉树是一种重要的非线性数据结构,...

    java使用jtree动态实现二叉树

    在Java中动态实现二叉树,即在运行时根据需要创建、更新和操作树结构,这涉及到对数据结构和Swing组件的深入理解。 首先,二叉树是一种特殊的树形数据结构,每个节点最多有两个子节点,分别称为左孩子和右孩子。...

    数据结构二叉树专题java代码实现

    下面是一些常见的二叉树操作的Java实现示例: 1. **创建二叉树**: 创建二叉树通常从空节点开始,通过插入节点来构造。例如,插入新节点的函数可能如下: ```java public void insert(int val) { root = insert...

    数据结构-二叉树(Java实现)

    编程实现如下功能: 1、假设二叉树的结点值是字符,根据输入的一颗二叉树的标明了空子树的完整先根遍历序列,建立一棵以二叉链表表示的二叉树。 2、对二叉树进行先根、中根和后根遍历操作,并输出遍历序列,同时观察...

    java实现二叉树最佳方法

    总之,Java实现二叉树的最佳方法依赖于对二叉树性质的深入理解以及对Java语言特性的熟练应用。递归构建和遍历是实现二叉树的两个核心方面,它们共同构建了复杂二叉树算法的基石。在实际应用中,还需要考虑树结构的...

    二叉树的简单Java实现

    数据结构二叉树(Binary Tree)的Java实现; 包括最基本的清空方法/判断为空方法/求树的深度的方法/获得父结点的方法/获得左/右兄弟结点的方法/递归先序/中序/后序遍历二叉树的方法;

    java 实现平衡二叉树

    文档中是我自己实现的用java语言实现(1)判断给定的二叉树是否平衡;(2)二叉树插入新数据后,如果失衡自我旋转调整的方法。

    二叉树相关操作java实现

    1:构造一个二叉树 2:二叉树前序遍历(递归) 3:二叉树中序遍历(递归) 4:二叉树后续遍历(递归) 5:二叉树前序遍历(非递归) 6:二叉树中序遍历(非递归) 7:二叉树后序遍历(非递归)

    二叉树java源码完整

    在"二叉树java源码完整"这个项目中,我们可以期待找到用Java实现的二叉树类及其相关方法。源码通常会包括以下部分: 1. **基础定义**:首先,会有一个类(例如`BinaryTree`或者`Node`)来表示二叉树的节点,每个...

    二叉树可视化Java语言实现(完整版,打开即可运行)

    在这个Java实现中,我们可以看到一个完整的二叉树可视化系统,包括四个关键的Java源文件:BinaryNode、Show1_12、Display_Tree和TreeControl。 1. **BinaryNode.java**: 这个文件代表二叉树的基本节点。在Java中,...

Global site tag (gtag.js) - Google Analytics