`

二叉树的java实现

阅读更多
package other;

import java.util.Stack;

class TreeNode {
	private String key;
	private TreeNode lchild; //左孩子
	private TreeNode rchild; //右孩子
	private TreeNode parent; //双亲节点

	public TreeNode(String key) {
		this.key = key;
	}

	public String getKey() {
		return key;
	}

	public void setKey(String key) {
		this.key = key;
	}

	public TreeNode getLchild() {
		return lchild;
	}

	public void setLchild(TreeNode lchild) {
		this.lchild = lchild;
	}

	public TreeNode getRchild() {
		return rchild;
	}

	public void setRchild(TreeNode rchild) {
		this.rchild = rchild;
	}

	public TreeNode getParent() {
		return parent;
	}

	public void setParent(TreeNode parent) {
		this.parent = parent;
	}

	public String toString() { // 打印出树种某个节点的信息
		StringBuffer sb = new StringBuffer();
		sb.append("key:" + this.key + "   ");
		if (this.getLchild() != null) {
			sb.append("   left child:" + this.getLchild().getKey());
		}
		if (this.getRchild() != null) {
			sb.append("   right child:" + this.getRchild().getKey());
		}
		return sb.toString();
	}
}

public class TreeTest {

	private static Stack<TreeNode> s;
	private static TreeNode root;

	public static TreeNode createTree(){
		    root = new TreeNode("6");
			TreeNode l = new TreeNode("3");
			TreeNode r = new TreeNode("8");
			l.setParent(root);
			r.setParent(root);

			TreeNode ll = new TreeNode("2");
			TreeNode rl = new TreeNode("7");
			l.setLchild(ll);
			r.setLchild(rl);
			ll.setParent(l);
			rl.setParent(r);

			root.setLchild(l);
			root.setRchild(r);
			root.setParent(null);
			return root;
	}
	
	public static void main(String[] args) {

		// 简单的构造一个树,当然是先构造树上的每一个节点
	
		root = createTree();
		System.out.println(treeDepth(root));
//		preOrderTraverse(root); // 递归先序遍历树
//		
//		
//		//
//		TreeNode finded = treeSearchTranverse(root, "6"); // 查找树中的某个key是否存在
//		System.out.println(finded);
//
//		TreeNode finded2 = treeSearchTranverse(root, "6"); // 查找树中的某个key是否存在
//		System.out.println(finded2);
		
//		inOrderNonTraverse(root);
	}

	// 递归先序遍历二叉树,后序和中序相似,只是调换输出子树根节点的次序
	public static void preOrderTraverse(TreeNode t) {
		System.out.println("递归先序遍历");

		if (t != null) {
			System.out.println(t.getKey());
			preOrderTraverse(t.getLchild());
			preOrderTraverse(t.getRchild());
		}

	}

	public static void inOrderNonTraverse(TreeNode t) { // 中序遍历二叉树的非递归
														
		s = new Stack<TreeNode>();
		s.clear();

		s.push(t);// 根节点入栈
		while (!s.isEmpty()) {
			while (!s.isEmpty()&&s.peek()!= null)
				s.push(s.peek().getLchild());// 向左走到尽头
			s.pop();//空指针退栈,别忘了
			if (!s.isEmpty()) {
				TreeNode current = s.pop();
				System.out.println(current.getKey());
				s.push(current.getRchild());
			}
		}
	}

	// 二叉查找树,必须满足左子树的关键字小于等于根,右子树的节点大于等于根,这样中序遍历该树,可得到一个有序序列

	/*
	 * 在二叉查找树上找关键字为key的节点,递归方法
	 */
	public static TreeNode treeSearchTranverse(TreeNode root, String key) {
		if (root == null || root.getKey().equals(key))
			return root;
		if (root.getKey().compareTo(key) > 0) { // 小于根节点的关键字,肯定在左子树上
			return treeSearchTranverse(root.getLchild(), key);
		} else {
			return treeSearchTranverse(root.getRchild(), key);
		}
	}

	/*
	 * 在二叉查找树上找关键字为key的节点,非递归方法
	 */
	public static TreeNode treeSearchNonTranverse(TreeNode root, String key) {
		while (root != null && !root.getKey().equals(key)) {
			if (key.compareTo(root.getKey()) < 0) {
				root = root.getLchild(); // 指向左孩子
			} else {
				root = root.getRchild();
			}

		}
		return root;
	}

	/*
	 * 返回查找树中的最小关键字,只需一直沿着节点的left指针即可
	 */
	public static TreeNode TreeMin(TreeNode x) {
		while (x.getLchild() != null) {
			x = x.getLchild();
		}
		return x;
	}

	/*
	 * 返回查找树中的最大关键字,只需一直沿着节点的right指针即可
	 */
	public static TreeNode TreeMax(TreeNode x) {
		while (x.getRchild() != null) {
			x = x.getRchild();
		}
		return x;
	}

	/*
	 * 返回中序遍历查找树时节点x的后继,无需对关键字进行比较,因为二叉查找树的结构,x的后继就是具有大于x.getKey()的关键字中最小者的那个节点
	 */
	public static TreeNode TreeSuccessor(TreeNode x) {
		if (x.getRchild() != null) //根据中序遍历
			return TreeMin(x.getRchild());

		TreeNode y = x.getParent();
		while(y!=null&&x==y.getRchild()){ //x是y的右孩子或x是根节点???
			x=y;
			y=y.getParent();
		}
		return y;  //x是y的左孩子
	}
	
	/*
	 * 在二叉查找树中插入一个节点z,使之仍然保持查找树的特性???????????不懂,指针x跟踪路径,从根节点开始,下降,而y始终指向x的父节点。
	 */
	public static void insertNode(TreeNode z){
		TreeNode y =null;
		TreeNode x = getRoot(); //根的父节点为空
		
		while(x!=null){
			y=x;
			if(z.getKey().compareTo(x.getKey())<0) x=x.getLchild();
			else x=x.getRchild();
			
			
		}
		z.setParent(y); //插入的z节点的双亲节点
		if(y==null){
			setRoot(z);//当前树为空树,设置根节点
		}
		else if(z.getKey().compareTo(y.getKey())<0){
			y.setLchild(z);
		}
		else y.setRchild(z);
	}

	
	public static TreeNode getRoot() {
		return root;
	}

	public static void setRoot(TreeNode root) {
		TreeTest.root = root;
	}

	/*
	 * 在二叉查找树中删除一个节点z,使之仍然保持查找树的特性
	 */
	public static TreeNode deleteNode(TreeNode z){
		
		TreeNode x,y;
		if(z.getLchild()==null||z.getRchild()==null){
			y=z;
		}
		else y = TreeSuccessor(z);
		
		if(y.getLchild()!=null){
			x=y.getLchild();
		}
		else x = y.getRchild();
		
		if(x!=null){
			x.setParent(y.getParent());
		}
		
		if(y.getParent()==null){
			setRoot(x);
		}
		else if(y==y.getParent().getLchild()){
			y.getParent().setLchild(x);
		}
		else{
			y.getParent().setRchild(x);
		}
		
		if(y!=z){
			z.setKey(y.getKey());
		}
		return y;
	}
	
	public static int treeDepth(TreeNode t){ //计算树的深度
		TreeNode lchild,rchild;
		int lchildDepth,rchildDepth;
		
		if(t==null) return 0;
		else {
			System.out.println("树节点不为空时:");
			lchild = t.getLchild();
			rchild = t.getRchild();
			lchildDepth = treeDepth(lchild);
			rchildDepth = treeDepth(rchild);
			
			
			return lchildDepth>rchildDepth?(lchildDepth+1):(rchildDepth+1);
		}
	}

}
分享到:
评论

相关推荐

    数据结构-二叉树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