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

二叉树代码

 
阅读更多

 

package endual;

/**
 * 树的效率
 *     树查找的效率是取决于这个节点是在哪个层数。它的时间复杂度是logN,更准确的说是底数为2的的logN
*/
public class Tree {

	private TreeNode root ; //根节点
	private int nEitems ; //记录tree的个数

	
	/**
	 * 判断是否为空
	 * @return
	 */
	public boolean isEmplty() {
		
		if (root==null) {
			return true ;
		}
		
		return false ;
		
	}
	
	
	/**
               查找节点
               根据关键值的查找节点是树的主要操作,是最简单的。
               搜索二叉树的概念:每个节点都有一个关键值,代表节点,那么这个关键值的大小的比较是:左节点 < 父节点 <= 右节点
               节点关键词的选取:我们可以用员工的ID号码,用学生的序号,用公民的身份证号,设置可以是电话号码。
                     我们也可以用零件的数量,颜色等等。当然了数字是比较常用。
               节点的创建得到这两个特征,并在生命周期内保存它。
	 */
	//查找
	public Object find(int key) { //返回的是数据
		
		TreeNode current = root ; //从根节点开始查找
		
		while (current.getTreeNodeId() != key) { //当前树节点的关键值是否等于key值
			
			if (key < current.getTreeNodeId()) { //如果关键字的值是小于当前节点的关键词的值,那么可以判定,这个关键词的值是可能在该节点的左边的孩子上
				
				current = current.getLeftNode() ; //将当前节点设置为该节点的左边的孩子
			}else {
				//同理
				current = current.getRightNode() ;
			}
			
			if (current == null) { //如果当前node找到没有可以找位置都没有找到,那么就返回了,否则一直找下去
				return null ;
			}
			
			
		} //end while
		
		return current.getObj() ;

	} //end find
	
	
	/**
	 * 要插入一个节点,首先必须找到要插入的地方。这很像要找一个不存在的节点的过程,好像找不到节点的那种情况,然后我们
	 * 将要插入的Node插入进行。从根节点开始查找一个相应节点,它将是新节点的父节点。当父节点找到了,新的节点
	 * 就可以连接到它的左子节点或者右子子节点。这取决于新节点的关键子的值比父节点大还是小的问题了。
	 * 	            目标是要找到空的地方还有是最重要的是一个顺序关系,
			  必须要将我们的输入的关键词key的值啊要和符合搜索树的条件
			
	 */
	

	//插入
	//传入进来的是自己设置的key值
	public void insert(Object obj,int key) { 

		TreeNode newNode = new TreeNode(obj,null,null) ; //将新节点的左右子节点都设置成为null
		newNode.setTreeNodeId(key ) ; //设置该插入节点的key值
		
		if (null == root) { //根节点为空
			
			root = newNode ;
			return ;
		}
		
		TreeNode current = root ;
		TreeNode parent = null ;
		
		while (true) {
			/**
			 * 目标是要找到空的地方还有是最重要的是一个顺序关系,
			 * 必须要将我们的输入的关键词key的值啊要和符合搜索树的条件
			 */
			parent = current ;
			if(parent.getLeftNode().getTreeNodeId() > key) {
			//当前父节点的KEY值要大于key	,那么转向该父亲节点的左子节点
				current = parent.getLeftNode() ;
				if (current == null) { //如果左边的子节点是空的,那么就插入到了
					
				    parent.setLeftNode(newNode) ; //插入进去了
					return ;
				}
			}//end go to left
			else { //向右子节点去了
				current = parent.getRightNode() ;
				if (current == null) { //如果左边的子节点是空的,那么就插入到了
					
					parent.setRightNode(newNode) ; //插入进去了
					return ;
				}
			} //end go to right
			
		} //end while
	} //end insert
	
	//---------------------------------------------------------------删除
	/**
	 * 删除节点是二次树搜索树常用的一半操作中最复杂的。但是,删除节点在很多树的应用中又非常重要,所以要
	 * 详细的研究并且总结特点。
	 * 
	 * 删除节点要从查找删除的节点开始入手,方法与前面介绍的find和insert相同的,找到节点以后,这个要删除的节点有三种情况要考虑
	 * 1.改节点是叶子节点,
	 * 2.改节点有一个子节点
	 * 3.改节点有两个子节点
	 * 
	 * 情况1:删除没有子节点的节点
	 *    要删除叶节点,只需要改变改节点的父节点的对应子字段的值,由指向该节点改为null就可以了。
	 *    要删除的节点仍然在,但是不是tree的了。java jvm会收回的。不需要删掉的。
	 * 
	 */
	public boolean delect(int key) { //删除掉以后那么返回的是ture,否则返回的是false
		
		if(root == null) {
			System.out.println("空树");
			return false;
		}

		TreeNode current = root ;
		TreeNode parent  = root ;
		boolean  isLeftNode = true ;
		boolean  isRoot = true ;
		while (current.getTreeNodeId() != key) {
			isRoot = false ;
			parent = current ;
			
		   if (current.getTreeNodeId() < key) {
				
				current = parent.getLeftNode() ;
				
			} 
		   else {
				
				isLeftNode = false ;
				current = parent.getRightNode() ;

			}
			if (current == null) {
				System.out.println("找不到这样的节点");
				return false;//没有找到这样的
			}
		   
		}//end while (true
		
		//1.找到了符合key的node 叫current
		//2.找到了current的parent节点,叫parent
		//3.标记current是parent的哪个节点

		if(isRoot) { //如果是root
			
			//1.当前节点是叶子节点
			//1.root没有孩子,那么将root为null
			if(current.getLeftNode()==null && current.getRightNode()==null) {
				root = null ;
				return true ;
			}
			//如果当前节点有两个节点
			//root有左右两个孩子
			if(current.getLeftNode()!=null || current.getRightNode()!=null) {
				
				
				
			}
			//当前节点只有一个节点
			//那么root有一个孩子
			else {
				
				if(root.getLeftNode()!=null) { //如果只有左孩子,那么孩子就当root
					
					root = root.getLeftNode() ; //将root用左孩子代替
					return true ;
				}
				
				else { //那么root只有右孩子
					
					root = root.getRightNode() ; //将root右孩子代替
					return true ;
				}
			}
			
		}
		
		//这说明删除的节点不是root了
		
		if (isLeftNode) { //如果是current是parent的左边的节点  
           
			//1.当前节点是叶子节点
			if(current.getLeftNode()==null && current.getRightNode()==null) {
				parent.setLeftNode(null) ; //直接将孩子设置为null
				return true ;
			}
			//如果当前节点有两一个节点
			if(current.getLeftNode()!=null || current.getRightNode()!=null) {
				
				//我不会啊
				
			}
			//当前节点只有一个节点
			else {
				//要删掉的Node是父亲的左孩子,并且这个Node只有一个右孩子,那么Node的父亲的左边孩子指向到Node节点的右孩子
				if(current.getRightNode()!=null) { 
					
					parent.setLeftNode(current.getRightNode()) ;
					return  true ;
				}
				//要删掉的Node是父亲的左孩子,并且这个Node只有一个左孩子,那么Node的父亲的左边孩子指向到Node节点的左孩子
				parent.setLeftNode(current.getLeftNode()) ;
				return true ;
			}

		}
		
		
		//如果是current是parent的右边边的节点
		else {        
			
			//1.当前节点是叶子节点
			if(current.getLeftNode()==null && current.getRightNode()==null) {
				parent.setRightNode(null) ; //直接将右边的孩子设置null
			}
			//如果当前节点有两一个节点
			if(current.getLeftNode()!=null || current.getRightNode()!=null) {
				
				
				//我不会啊
				
			}
			//当前节点只有一个节点
			else {
				
				if(current.getRightNode()!=null) { //要删掉节点是父亲的右孩子,它有唯一的右孩子,那么将父亲的右边孩子指向该节点的右边孩子
					
					parent.setRightNode(current.getRightNode()) ;
					return  true ;
				}
				
				parent.setRightNode(current.getLeftNode()) ;//要删掉节点是父亲的右孩子,它有唯一的左孩子,那么将父亲的右边孩子指向该节点的左边孩子
				return true ;
			}
			
		}
		

		
		
		return true ;
		
	}
	
	//----------------------------------------选择最大值最小值----------------------------------------------
	
	/**
	 * 查找最大值和最小值
	 * 顺便说下,在二叉树中得到最大值和最小值也是恨容易的事情。事实上,这个过程非常容易,下面我们来理解下。
	 * 要找最小值的时候,先走到根的左子节点,然后接着走,如此类推,知道找到的节点没有左子节点,这个就是最小得值了
	 * 
	 */
	
	/**
	 * 查找最大值
	 * 要找最大值的时候,先走到根的右子节点,然后接着走,如此类推,知道找到的节点没有由子节点,这个就是最小得值了
	 * 
	 */
	public void findMax() {
		
		if(root == null) {
			System.out.println("空树") ;
			return ;
		}
		
		this.getTreeMax(root) ;
		
		
	}
	
	
	/**
	 * 查找最小值
	 * 要找最小值的时候,先走到根的左子节点,然后接着走,如此类推,知道找到的节点没有左子节点,这个就是最小得值了
	 */
	public void findMin() {
		
		if(root == null) {
			System.out.println("空树") ;
			return ;
		}
		
		this.getTreeMin(root) ;
		
	}
	
	private void getTreeMin(TreeNode node) {
		
		if(node.getLeftNode() != null) {
			
			this.getTreeMin(node.getLeftNode());
			
		}
		else {
			
			System.out.println("该树的最大值是:" + node.getTreeNodeId()) ;
			
		}
		
		
	}
	private void getTreeMax(TreeNode node) {
		
		if(node.getRightNode() != null) {
			
			this.getTreeMax(node.getRightNode()) ;
			
		}
		else {
			
			System.out.println("该树的最大值是:" + node.getTreeNodeId()) ;
			
		}
		
	}
	
	
	
	//---------------------------------------------遍历-------------------------------------------------------------
	
	/**
	 * 遍历树的意思就是根据一种特定的顺序来方法每一个节点,这个过程不如查找,插入,删除节点常用。其中一个原因是因为遍历
	 * 的速度不是特别快。不过遍历树在某些情况下是有用的,而且在理论上很有意思。遍历比删除简单。
	 * 遍历有三种情况
	 * 前序遍历  ABC
	 * 中序遍历  BAC
	 * 后序遍历 ACB
	 * 三种遍历是根据根节点来定义的。
	 * 
	 */
	
	//遍历树 中序遍历
	/**
	 * 中序遍历
	 * 中序遍历二叉搜索树会使得所有的节点按照关键子的值升序被访问到。如果希望在二叉树
	 * 中创建有序的数据序列,这是一种方式
	 * 遍历树的最简单的方法是递归的方法。用递归的方法遍历整棵树要用一个节点作为参考。初始的时候这个节点就是根节点
	 * 三件事情:
	 * 
	 * 1.调用自身来遍历节点的左边树
	 * 2.访问自身节点
	 * 3.调用自身来遍历节点的右边树
	 * 
	 * 记住访问一个节点意味着对这个节点做了某些操作;显示节点,把节点写入问题,或者其他的操作
	 * 遍历可以应用于任何的二叉树,而不只是二叉树搜索。这个遍历的原来不关心节点的关键字值。它只是看到这个节点是不是有子节点
	 */
	
	public void displayTreeABC() {
		
		if(root == null) {
			System.out.println("空树哦") ;
			return ;		
		}
		
       this.ABC(root) ;
		
	}

	public void displayTreeBAC() {
		
		if(root == null) {
			System.out.println("空树哦") ;
			return ;		
		}
		
		//非空的时候;
		this.BAC(root) ;
		
	}
	
	//遍历树 后序遍历
	public void displayTreeACB() {
		
		if(root == null) {
			System.out.println("空树哦") ;
			return ;		
		}
		
		//非空的时候
		
		this.ACB(root) ;
		
	}
	
	//中序方法,用于递归
	private void ABC(TreeNode node) {
		

		if(node != null) {
			
			this.ABC(node.getLeftNode()) ;
			System.out.println(node.getTreeNodeId()); //取得以后进行了操作
			this.ABC(node.getRightNode()) ;
		}
		
		
		
	}
	
	//前序方法,用于递归
	private void BAC(TreeNode node) {
		
		if(node!= null) {
			
			System.out.println(node.getTreeNodeId()); //取得以后进行了操作
			this.ABC(node.getLeftNode()) ;
			this.ABC(node.getRightNode()) ;
		}
		
		
	}
	
	//后续方法,用于递归
	private void ACB(TreeNode node) {

		if(node != null) {
			
			this.ABC(node.getLeftNode()) ;
			this.ABC(node.getRightNode()) ;
			System.out.println(node.getTreeNodeId()); //取得以后进行了操作
		
		}
		
		
	}
	
	
	
	
}

 

 

 

package endual;

public class TreeNode {

	private Object obj ; //存放数据
	private TreeNode leftNode = null; //树节点的左孩子
	private TreeNode rightNode = null ; //树节点的右孩子
   	private int treeNodeId ;   //节点的关键词
   	
	public TreeNode(Object obj, TreeNode leftNode, TreeNode rightNode,
			int treeNodeId) {
		super();
		this.obj = obj;
		this.leftNode = leftNode;
		this.rightNode = rightNode;
		this.treeNodeId = treeNodeId;
	}

	
	
	
	public TreeNode(Object obj) {
		super();
		this.obj = obj;
	}

   


	public TreeNode(Object obj, TreeNode leftNode, TreeNode rightNode) {
		super();
		this.obj = obj;
		this.leftNode = leftNode;
		this.rightNode = rightNode;
	}




	public TreeNode(Object obj, int treeNodeId) {
		super();
		this.obj = obj;
		this.treeNodeId = treeNodeId;
	}

	public Object getObj() {
		return obj;
	}

	public void setObj(Object obj) {
		this.obj = obj;
	}

	public TreeNode getLeftNode() {
		return leftNode;
	}

	public void setLeftNode(TreeNode leftNode) {
		this.leftNode = leftNode;
	}

	public TreeNode getRightNode() {
		return rightNode;
	}

	public void setRightNode(TreeNode rightNode) {
		this.rightNode = rightNode;
	}

	public int getTreeNodeId() {
		return treeNodeId;
	}

	public void setTreeNodeId(int treeNodeId) {
		this.treeNodeId = treeNodeId;
	}
   	
   	
	
	
}
分享到:
评论

相关推荐

    用Java编写的二叉树代码

    本资源包含的是用Java编程语言实现的二叉树代码,对于学习Java和数据结构的开发者来说极具价值。 二叉树主要分为几种类型,包括: 1. 完全二叉树:在完全二叉树中,除了最后一层外,每一层都被完全填满,并且所有...

    平衡二叉树代码

    平衡二叉树代码

    实用的php二叉树代码

    PHP二叉树代码概览 给定的代码片段展示了如何在PHP中构建并遍历一个二叉树。首先,通过数组`$node_cache`存储节点信息,包括节点ID、名称和父节点ID。这些信息构成了树的结构基础。随后,`get_page_children`函数...

    ConsoleApplication10.zip_C++二叉树代码

    本文将深入探讨“C++二叉树代码”这个主题,以及与之相关的概念和技术。 二叉树是一种特殊的树形数据结构,每个节点最多有两个子节点,通常分为左子节点和右子节点。在C++中,我们可以使用结构体或类来表示二叉树的...

    二叉树java代码

    java作业中的二叉树代码。在计算机科学中,二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。 一棵深度为...

    二叉树代码.rar

    这个名为"二叉树代码.rar"的压缩包文件包含了关于二叉树的各种操作的C语言实现,特别关注在Linux环境下的编程。下面将详细讨论其中涉及的知识点。 首先,我们来看"20数据结构-二叉树的创建、递归遍历、层次遍历"这...

    孩子兄弟二叉树代码

    在提供的"孩子兄弟二叉树代码"压缩包中,可能包含以下功能的实现: 1. **创建**:创建一个新的空的孩子兄弟二叉树,或者根据给定的节点数据创建一个完整的树。这个过程通常涉及到初始化节点,分配内存,并设置节点...

    数据结构二叉树代码

    总之,"数据结构二叉树代码"项目提供的"bst.cpp"文件,是一个用于学习和实践C++数据结构中二叉查找树的好资源。通过理解和掌握这个实现,开发者能够更好地理解二叉树的工作原理,并在实际项目中灵活运用。

    基于c语言实现的二叉树代码

    标题中提到的“基于C语言实现的二叉树代码”意味着本段代码涉及到的是C语言编程中的一个常用数据结构——二叉树。二叉树是一种非常重要的树形结构,它具有如下特点: 1. 每个节点最多有两个子节点,通常称为左孩子...

    二叉树代码 C++语言 类实现

    以下是对"二叉树代码 C++语言 类实现"这一主题的详细阐述。 首先,我们需要定义一个二叉树节点类,通常包含三个属性:值(存储节点的数据)、左子节点指针和右子节点指针。例如: ```cpp class TreeNode { public:...

    c语言关于二叉树代码

    c语言关于二叉树代码#include ; #include ; typedef struct TreeNode { int data; struct TreeNode *lchild, *rchild; }ABTreeNode; ABTreeNode * CreatBiTree() {ABTreeNode *T; int ch; scanf("%d",&ch); if...

    树与二叉树代码模板.zip

    本压缩包"树与二叉树代码模板.zip"提供了一些基本的代码实现,帮助我们更好地理解和操作这些数据结构。 树是一种非线性的数据结构,它由一组节点(也称为顶点)组成,每个节点可以有零个或多个子节点,且具有唯一的...

    java可视化二叉树代码

    java二叉树代码,该二叉树为可视化二叉树,可视化为swing中group的嵌套,通过点击add按钮添加子叶,通过点击delete删除子叶,同时会删除它下面的所有子树。图形化的操作非常适合二叉树的理解。

    欧式看涨期权二叉树代码

    欧式看涨期权二叉树代码

    线索二叉树代码和讲解

    线索二叉树代码和讲解,内容详细全面,通俗易懂,通过测试,代码可以直接使用,方便大家学习.

    判别平衡二叉树代码课程设计C++

    判别平衡二叉树代码C++版本

    数据算法 二叉树代码

    清华大学 计算机系 数据算法 二叉树 。。。二叉搜索树的费递归实现,包括树构建,树删除,复制(深拷贝),插入,中序遍历和层序遍历等等。希望能够提供帮助。

Global site tag (gtag.js) - Google Analytics