排序二叉树
博客专区 > JiaChang 的博客 > 博客详情
排序二叉树
JiaChang 发表于1年前
排序二叉树
  • 发表于 1年前
  • 阅读 9
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 技术升级10大核心产品年终让利>>>   

摘要: 排序二叉树的java实现

排序二叉树

排序二叉树要么是一棵空二叉树,要么是具有以下性质的二叉树

(1)若它的左子树不空,则左子树上所有节点的值均小于它的根节点的值。

(2)若它的右子树不空,则右子树上所有节点的值均大于它的根节点的值。

(3)它的左,右子树也分别为排序二叉树。

创建排序二叉树

(1)以根节点为当前节点开始搜索

(2)拿新节点的值和当前节点的值比较

(3)如果新节点的值更大,则以当前节点的右子节点作为新的当前节点;如果新节点的值更小,则以当前节点的左子节点作为新的当前节点

(4)重复2和3两个步骤,直到搜索到合适的叶子节点

(5)将新节点添加为第4步找到的叶子节点的子节点,如果新节点更大,则添加为右子节点;否则,添加为左子节点

删除节点

当从排序二叉树中删除一个节点之后,为了让它依然保持为排序二叉树,必须对该排序二叉树进行维护。维护可以分成如下几种情况

(1)被删除节点是叶子节点,只需将它从父节点中删除

(2)被删除节点p只有左子树或则只有右子树,用p的子节点来代替要删除的节点

 

 

(3)若被删除节点p的左,右子树均非空,则有两种做法,一是用被删除节点最大的左孩子来代替删除节点,二是用被删除节点最小的右孩子来代替删除节点。

 

排序二叉树的节点定义

//排序二叉树节点结构
	class Node{
		Object data;
		Node left;
		Node right;
		Node parent;
		
		public String toString(){
			return "[data="+this.data+"]";
		}
		
		public boolean equals(Object obj){
			if(this==obj){
				return true;
			}
			if(obj.getClass() == Node.class){
				Node target = (Node)obj;
				return this.data.equals(target.data)
						&& this.left == target.left
						&& this.right == target.right
						&& this.parent == target.parent;
			}
			return false;
		}
	}

排序二叉树添加节点

/***
	 * 添加节点
	 * @param data 新添加节点的数据
	 */
	public void add(E data){
		if(root==null){
			new SortedBinTree(data);	//如果树根为null,则先构造树根节点
		}
		else{
			int cmp = 0;
			Node parent = null;
			Node current = root;
			do{
				parent = current;
				cmp = data.compareTo(current.data);		
				//如果新节点的值大于当前节点的值
				if(cmp>0){
					current = current.right;	//以右子节点作为当前节点
				}
				else {		//否则新节点小于当前节点的值
					current = current.left;		//以左子节点当作当前节点
				}
			}while(current!=null);		//当前节点不为null继续遍历
			//创建新节点
			Node newNode = new Node();
			newNode.data = data;
			newNode.parent = parent;
			if(cmp>0){
				parent.right = newNode;
			}
			else {
				parent.left = newNode;
			}
		}
		
	}

排序二叉树删除节点

/***
	 * 删除指定节点
	 * @param element 删除节点
	 * @return 被删除节点存在则删除并将该节点返回,不存在则返回null
	 */
	public Node remove(E element){

		Node target = getNode(element);
		if(target == null){
			return null;
		}
		//第一种情况:被删除节点为叶子节点,(处理方法:直接删除即可)
		if(target.left == null && target.right == null){
			Node deleteNode = target;
			//如果要删除的节点是根节点
			if(target == root){
				root = null;
			}
			else {
				//要删除节点是父节点的左孩子节点,直接删除即可
				if(target == target.parent.left){
					target.parent.left = null;					
				}
				//要删除节点是父节点的右孩子节点
				else {
					target.parent.right = null;	
				}
			}
			//删除目标节点
			target = null;
			return deleteNode;
		}
		//第二种情况:被删除节点只有左孩子节点(处理方法:用要删除节点的左孩子节点代替要删除节点)
		else if(target.left != null && target.right == null){
			Node deleteNode = target;
			if(target == root){
				root = target.left;
			}
			else {
				//如果要删除节点是父节点的左孩子节点
				if(target == target.parent.left){
					//用要删除节点的左孩子节点代替要删除节点
					target.parent.left = target.left;
				}
				else {
					target.parent.right = target.left;
				}
				//让target的左子树的parent指向target的parent
				target.left.parent = target.parent;
			}
			//删除目标节点
			target = null;
			return deleteNode;
		}
		//第三种情况:被删除节点只有右孩子节点(处理方法:用要删除节点的右孩子节点代替要删除节点)
		else if(target.left == null && target.right != null){
			Node deleteNode = target;
			//被删除节点是根节点
			if(target == root){
				root = target.right;	
			}
			else {
				//如果被删除节点是父节点的左孩子节点
				if(target == target.parent.left){
					target.parent.left = target.right;
				}
				//否则被删除节点是父节点的右孩子节点
				else {
					target.parent.right = target.right;
				}
				//让target的右子树的parent指向target的parent
				target.right.parent = target.parent;
			}
			//删除目标节点
			target = null;
			return deleteNode;
		}
		//第四种情况:被删除节点非叶子节点,并且左右孩子都不为null(处理方法有两种:一种是用被删除节点的最大左孩子节点代替删除节点,另一种是用被删除节点最小的右孩子节点代替删除节点)
		else {
			Node deleteNode = target;
			Node maxLeftNode = target.left;
			//找到删除节点的最大左孩子节点
			while(maxLeftNode.right!=null){
				maxLeftNode = maxLeftNode.right;
			}
			//从原有的子树中删除最大的左孩子节点
			maxLeftNode.parent.right = null;
			//如果删除节点为父节点的左孩子节点
			if(target == target.parent.left){
				target.parent.left = maxLeftNode;
			}
			//否则删除节点为父节点的右孩子节点
			else {
				target.parent.right = maxLeftNode;
			}
			//用被删除节点的最大左孩子节点代替删除节点
			maxLeftNode.parent = target.parent;
			maxLeftNode.left = target.left;
			maxLeftNode.right = target.right;
			target = null;
			return deleteNode;
		}
		
		
	}

获取指定节点

/***
	 * 根据节点的数据获取指定节点
	 * @param element
	 * @return
	 */
	public Node getNode(E element){
		if(root == null){
			
		}
		Node p = root;
		while(p != null){
			int cmp = element.compareTo(p.data);
			if(cmp>0){
				p = p.right;
			}
			else if(cmp<0){
				p = p.left;
			}
			else return p;
		}
		return null;
	}

广度优先遍历

/***
	 * 广度优先遍历
	 * 利用队列实现
	 * @return list
	 */
	public List<Node> breadthFirst(){
		Queue<Node> queue = new ArrayDeque<>();
		List<Node> list = new ArrayList<>();
		if(root != null){
			queue.add(root);
		}
		while(!queue.isEmpty()){
			Node node = queue.poll();
			list.add(node);
			if(node.left != null){
				queue.add(node.left);
			}
			if(node.right != null){
				queue.add(node.right);
			}
		}
		return list;
	}

深度优先遍历

public void inOrderIterator(Node root){
		if(root !=null){
			inOrderIterator(root.left);
			System.out.println(root);
			inOrderIterator(root.right);
		}
	}

 

标签: 排序二叉树
共有 人打赏支持
粉丝 3
博文 32
码字总数 18002
×
JiaChang
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: