Java数据结构系列之——树（二）：二叉树的实现及其常用操作

Java数据结构系列之——树（2）：二叉树的实现及其常用操作

package tree.binarytree;

public class BiTreeNode {
	int data;
	BiTreeNode leftNode;
	BiTreeNode rightNode;
	
	public BiTreeNode(){
		leftNode=null;
		rightNode=null;
	}
	
	public BiTreeNode(int data,BiTreeNode leftNode,BiTreeNode rightNode){
		this.data=data;
		this.leftNode=leftNode;
		this.rightNode=rightNode;
	}
}

*******************************************************************************

package tree.binarytree;

public class BiTree {
	public BiTreeNode root;//根节点
	
	public BiTree(){//空树
		this.root=null;
	}
	
	//传入数据域，左子树，右子树构建二叉树
	public BiTree(int data,BiTree leftchild,BiTree rightchild){
		BiTreeNode left,right;
		
		if(leftchild==null){
			left=null;
		}else{
			left=leftchild.root;
		}
		
		if(rightchild==null){
			right=null;
		}else{
			right=rightchild.root;
		}
		
		this.root=new BiTreeNode(data, left, right);
	}
	
	//插入结点
	public void insert(int data){
		BiTreeNode newNode=new BiTreeNode(data,null,null);
		BiTreeNode current=root;//当前结点
		BiTreeNode parent;//父节点
		
		if(root==null){
			root=newNode;
			return;
		} else {
			while (true) {
				parent = current;

				if (current.data > data) {
					current = current.leftNode;
					if (current == null) {
						parent.leftNode = newNode;
						return;
					}
				} else {
					current = current.rightNode;
					if (current == null) {
						parent.rightNode = newNode;
						return;
					}
				}

			}
		}
	}
	
	//查找
	public BiTreeNode find(int data){
		if(root==null){
			throw new RuntimeException("二叉樹為空");
		}
		
		BiTreeNode current=root;
		
		while(current.data!=data){
			if(current.data>data){
				current=current.leftNode;
			}else{
				current=current.rightNode;
			}
			
			if(current==null){
				return null;
			}
		}
		return current;
	}
}