二叉树

原文链接：http://www.orlion.ga/267/

为什么使用二叉树呢？因为它通常结合了另外两种数据结构的优点：一种是有序数组，另一种是链表。在树中查找数据项的速度和在有序数组中查找一样快，并且插入数据项和删除数据项的速度也和链表一样。

?

二叉搜索树：

非平衡树：树的大部分的节点是在根的一边或者是另一边，如下图所示

树变得不平衡是由数据项插入的顺序造成的。

用java代码来表示树

????像其他数据结构一样，有很多方法可以在计算机内存中表示树，最常用的方法是把节点存储在无关联的存储器中，而通过每个节点中指向自己子节点的引用来连接。

????还可以在内存中用数组来表示树，用存储在数组中相对的位置来表示节点在树中的位置。实例中的java代码采用的是引用连接节点的方法。

????Node类

????首先，需要一个节点对象的类，这些对象包含数据，数据代表要存储的内容，而且还有指向节点的两个子节点的引用。类代码如下：

package?ga.orlion.btree;

public?class?Node?{
	
	int?iData;		//?节点数
	double?fData;	//?其他数
	Node?leftChild;	//?左节点
	Node?rightChild;//?右节点
	
	public?void?displayNode(){
		//?显示节点数据
	}
}

还需要一个类来表示树本身：Tree类

package?ga.orlion.btree;

public?class?Tree?{
	
	private?Node?root;?//?根节点
	
	public?Node?find(int?key){
		//?查询
	}
	
	public?void?insert(int?id?,?double?dd){
		//?插入
	}
	
	public?void?delete(int?id){
		//?删除
	}
}

最后是一个操作树的类TreeApp:

package?ga.orlion.btree;

public?class?TreeApp?{

	public?static?void?main(String[]?args)?{
		
		Tree?theTree?=?new?Tree();
		
		theTree.insert(50,?1.5);
		theTree.insert(25,?1.7);
		theTree.insert(75,?1.9);
		
		Node?found?=?theTree.find(25);?//?查找key为25的节点
		
		if?(found?==?null)?
			System.out.println("未找到key25");
		else
			System.out.println("找到key25");
	}

}

查找节点

Tree中的查找方法find()：

public?Node?find(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;
	}

树的效率

????查找节点的时间取决于这个节点所在的层数。

插入一个节点

????insert()方法从创建新节点开始，用提供的数据作为参考。下一步insert()必须先确定新节点插入的位置，这段代码与查找代码大致相同，区别是查找节点时遇到null直接返回现在要插入节点就是在返回前插入节点。

????java代码：

public?void?insert(int?id?,?double?dd){
		
		Node?newNode?=?new?Node();
		newNode.iData?=?id;
		newNode.fData?=?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;
					}
				}
			}
		}
	}

????
中序遍历的java代码：

public?void?inOrder(Node?localRoot){
		
		if?(localRoot?!=?null)?{
			inOrder(localRoot.leftChild);
			
			System.out.print(localRoot.iData?+?"|");
			
			inOrder(localRoot.rightChild);
		}
	}

查找最大值和最小值：

找到最小值就是要找到二叉树的最左边的叶子，具体过程为从根节点出发往左子节点走，直到该节点没有了左子节点那么该节点就是最小值了，java代码：

public?Node?miniNum(){
		
		Node?last?,?current;
		last?=?current?=?root;
		while(current?!=?null)?{
			last?=?current;
			current?=?current.leftChild;
		}
		
		return?last;
	}

删除！

????????//?找到待删除节点的后继节点
	private?Node?getSuccessor(Node?delNode){
		
		Node?successorParent?=?delNode;
		Node?successor?=?delNode;
		Node?current?=?delNode.rightChild;
		while?(current?!=?null)?{
			successorParent?=?successor;
			successor?=?current;
			current?=?current.leftChild;
		}
		
		if?(successor?!=?delNode.rightChild)?{
			successorParent.leftChild?=?successor.rightChild;
			successor.rightChild?=?delNode.rightChild;
		}
		
		return?successor;
	}
	public?boolean?delete(Node?node){
		
		if?(node?!=?null)?{
			Node?current?=?root;
			Node?parent?=?root;
			boolean?isLeftChild?=?true;
			//?找到待删除节点
			while(current?!=?node){
				parent?=?current;
				if?(node.iData?<?current.iData)?{
					isLeftChild?=?true;
					current?=?current.leftChild;
				}?else?{
					isLeftChild?=?false;
					current?=?current.rightChild;
				}
				if?(current?==?null)
					return?false;
			}
			//?如果待删除节点无子节点
			if?(current.leftChild?==?null?&&?current.rightChild?==?null)?{
				if?(current?==?root)
					root?=?null;
				else?if?(isLeftChild)
					parent.leftChild?=?null;
				else?
					parent.rightChild?=?null;
			//?如果待删除节点有左子节点
			}?else?if?(current.rightChild?==?null)?{
				if?(current?==?root)
					root?=?root.leftChild;
				else?if?(isLeftChild)
					parent.leftChild?=?current.leftChild;
				else?
					parent.rightChild?=?current.leftChild;
			//?如果待删除节点有右子节点
			}?else?if?(current.leftChild?==?null)?{
				if?(current?==?root)
					root?=?root.rightChild;
				else?if?(isLeftChild)
					parent.leftChild?=?current.rightChild;
				else?{
					parent.rightChild?=?current.rightChild;
				}
			//?如果待删除节点有两个节点
			}?else?{
				Node?successor?=?getSuccessor(current);
				if?(current?==?root)
					root?=?successor;
				else?if?(isLeftChild)
					parent.leftChild?=?successor;
				else?
					parent.rightChild?=?successor;
				
				successor.leftChild?=?current.leftChild;
			}
			
		}
		
		return?true;
	}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!