欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构-二叉树(BTree)

程序员文章站 2024-01-19 13:02:04
...

BTree

特征:

1.一个节点最多只有两个子节点,其中左子节点的关键字小于这个节点,右子节点的关键字大于等于该节点。

2.执行查找,插入,删除的时间复杂度都是:O(logN)。

3.遍历有中序,前序,后序。前,中和后只是在递归的时候先输出左子,自己或右子的顺序。可以通过中排序,按左子,自己,右子的顺序就是升序,反之则是降序。

4.最大值是树的右边底层叶子;最小值是左边底层叶子。

 

JAVA代码实现:

 

 

package org.acooly.datastructure.btree;

import java.util.Random;

/**
 * 特征:一个节点的左子节点的关键字小于这个节点,右子节点的关键字大于等于该节点。
 * 
 * @author zhangpu
 * 
 */
public class BinaryTree {

	/** 根节点 */
	private Node root;

	/**
	 * 查找
	 * 
	 * @param key
	 * @return
	 */
	public Node find(int key) {
		if (root == null) {
			return null;
		}
		Node current = root;
		while (current.getKey() != key) {
			if (key < current.getKey()) {
				// 小于本节点在左边
				current = current.getLeftNode();
			} else {
				// 大于等于本节点在右边
				current = current.getRightNode();
			}
			if (current == null) {
				// 搜索到最后叶子为空,表示没有找到
				return null;
			}
		}
		return current;
	}

	public Node getParent(int key) {
		if (root == null) {
			return null;
		}
		Node current = root;
		Node parent = root;
		while (current.getKey() != key) {
			if (key < current.getKey()) {
				// 小于本节点在左边
				parent = current;
				current = current.getLeftNode();
			} else {
				// 大于等于本节点在右边
				parent = current;
				current = current.getRightNode();
			}
			if (current == null) {
				// 搜索到最后叶子为空,表示没有找到
				return null;
			}
		}
		return parent;
	}

	/**
	 * 插入
	 * 
	 * @param key
	 * @param value
	 */
	public void insert(int key, Object value) {
		Node node = new Node(key, value);
		if (root == null) {
			root = node;
			return;
		}
		Node current = root;
		while (true) {
			if (key < current.getKey()) {
				if (current.getLeftNode() == null) {
					current.setLeftNode(node);
					return;
				} else {
					current = current.getLeftNode();
				}
			} else {
				if (current.getRightNode() == null) {
					current.setRightNode(node);
					return;
				} else {
					current = current.getRightNode();
				}
			}
		}

	}

	/**
	 * 中遍历(升序)
	 * 
	 * @param startNode
	 */
	public void inOrderAsc(Node startNode) {

		if (startNode != null) {
			inOrderAsc(startNode.getLeftNode());
			System.out.println(startNode);
			inOrderAsc(startNode.getRightNode());
		}

	}

	/**
	 * 中遍历(降序)
	 * 
	 * @param startNode
	 */
	public void inOrderDesc(Node startNode) {
		if (startNode != null) {
			inOrderDesc(startNode.getRightNode());
			System.out.println(startNode);
			inOrderDesc(startNode.getLeftNode());
		}

	}

	/**
	 * 最大值 算法:树中最底层的右子叶
	 * 
	 * @return
	 */
	public Node getMax() {
		Node current = root;
		while (current.getRightNode() != null) {
			current = current.getRightNode();
		}
		return current;
	}

	/**
	 * 算法:树中最底层的左子叶
	 * 
	 * @return
	 */
	public Node getMin() {
		return getMin(root);
	}

	/**
	 * 指定节点的最小节点,如果指定节点为root,则是树的最小节点
	 * 
	 * @param localRoot
	 * @return
	 */
	private Node getMin(Node localRoot) {
		Node current = localRoot;
		while (current.getLeftNode() != null) {
			current = current.getLeftNode();
		}
		return current;
	}

	/**
	 * 删除节点存在3中情况 <li>目标节点是叶子:直接删除,置为null <li>
	 * 目标节点只有一个子节点:如果目标节点是在父节点的左边,直接使用子节点作为父节点的左子,反正则为右子。 <li>
	 * 目标节点有两个子节点:找到后继节点,作为目标节点父节点的对应子节点。(后继:目标节点子节点中大于目标节点最小的个。路径:目标节点右子的最小节点。)
	 * 
	 * @param key
	 */
	public void delete(int key) {

		Node target = find(key);
		if (target == null) {
			return;
		}

		boolean leftExsit = (target.getLeftNode() != null ? true : false);
		boolean rightExsit = (target.getRightNode() != null ? true : false);
		// 第一种情况,目标是叶子,直接设置为null
		if (!leftExsit && !rightExsit) {
			target = null;
			return;
		}

		// 获得目标的父节点
		Node parent = getParent(key);
		Node child = null;
		if (leftExsit != rightExsit) {
			// 第二种情况:只有一个子
			child = (leftExsit ? target.getLeftNode() : target.getRightNode());
		} else {
			// 第三种情况:有两个子
			Node rightChild = target.getRightNode();
			child = getMin(rightChild);
			getParent(child.getKey()).setLeftNode(null);
			child.setRightNode(rightChild);
		}

		if (parent == null) {
			root = child;
			target = null;
			return;
		}

		if (parent.getLeftNode() != null && target.getKey() < parent.getLeftNode().getKey()) {
			// 目标是父的左子
			parent.setLeftNode(child);
		} else {
			// 目标是父的右子
			parent.setRightNode(child);
		}
		target = null;
	}

	public Node getRoot() {
		return root;
	}

	public static void main(String[] args) {
		BinaryTree tree = new BinaryTree();
		Random random = new Random();
		// INSERT
		for (int i = 1; i <= 10; i++) {
			int key = random.nextInt(100);
			tree.insert(key, "value" + key);
		}
		int key = 0;
		tree.insert(key, "value" + key);
		System.out.println("TARGET key: " + key);
		// FIND
		System.out.println("FIND: " + tree.find(key));
		// GETPARENT
		System.out.println("PARENT: " + tree.getParent(key));
		// MIX
		System.out.println("MAX: " + tree.getMax());
		// MIN
		System.out.println("MIN: " + tree.getMin());
		tree.delete(key);
		System.out.println();
		System.out.println("中遍历(升序):");
		tree.inOrderAsc(tree.getRoot());
		System.out.println("中遍历(降序):");
		tree.inOrderDesc(tree.getRoot());
	}

}

   节点类:

 

package org.acooly.datastructure.btree;

/**
 * BTree 节点
 * 
 * @author zhangpu
 * 
 */
public class Node {

	/** 节点KEY */
	private int key;
	private Object value;
	/** 左子节点 */
	private Node leftNode;
	/** 右子节点 */
	private Node rightNode;

	public Node() {
		super();
	}

	public Node(int key, Object value) {
		super();
		this.key = key;
		this.value = value;
	}

	public int getKey() {
		return key;
	}

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

	public Node getLeftNode() {
		return leftNode;
	}

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

	public Node getRightNode() {
		return rightNode;
	}

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

	public Object getValue() {
		return value;
	}

	public void setValue(Object value) {
		this.value = value;
	}

	@Override
	public String toString() {
		return String.valueOf(key) + "=" + value;
	}
	
	@Override
	public boolean equals(Object obj) {
		if(obj instanceof Node){
			Node n = (Node)obj;
			if(n.getKey() != getKey()){
				return false;
			}
		}else{
			return false;
		}
		return true;
	}

}
 

 

相关标签: 数据结构 算法