二叉查找树的构造与遍历[Java实现]

构造二叉查找树之插入算法：比较新节点关键字与格子树根节点的大小关系。如果新节点关键字小，则递归进入相应根节点的左子树，直到找到左子树为空的位置；否则，递归进入相应根节点的右子树，直到找到右子树为空的位置。

树节点:

package org.pbdevj.ds.search.binarysearchtree;import java.io.Serializable;/**树节点*/public class TreeNode implements Serializable {public Object nodeValue;//数据域public TreeNode lChild;//左子树public TreeNode rChild;//右子树public TreeNode() {// TODO Auto-generated constructor stub}public TreeNode(Object nodeValue, TreeNode lChild, TreeNode rChild) {super();this.nodeValue = nodeValue;this.lChild = lChild;this.rChild = rChild;}}

查找回调接口:

package org.pbdevj.ds.search.binarysearchtree;/**查找回调接口*/public interface ISearchCallBack {void visit(TreeNode e);}

查找接口：

package org.pbdevj.ds.search.binarysearchtree;/**查找接口*/public interface ISearch {TreeNode search(Object e);TreeNode search(Object e,ISearchCallBack searchCallBack);void output(ISearchCallBack searchCallBack);}

二叉查找树：

package org.pbdevj.ds.search.binarysearchtree;/**二叉查找树*/public class BinarySearchTree implements ISearch {private Object[] elements;TreeNode rootNode;//树根节点public BinarySearchTree(Object[] elements) {// TODO Auto-generated constructor stubthis.elements = elements;buildBinarySearchTree();}public BinarySearchTree(TreeNode rootNode) {// TODO Auto-generated constructor stubthis.rootNode = rootNode;}/**构造二叉查找树*/private void buildBinarySearchTree(){if(elements==null || elements.length==0)return;rootNode =new TreeNode(elements[0],null,null);if (elements.length==1)return;for (int index = 1; index < elements.length; index++) {//每次循环从数组中取一个元素TreeNode tempNode = rootNode;while(true){//将这个元素与左子树或右子树循环比较,小于则继续进入左子树的左子树，否则继续进入右子树的右子树if (elements[index].toString().compareTo(tempNode.nodeValue.toString())<0){//小于中间节点if (tempNode.lChild==null){tempNode.lChild = new TreeNode(elements[index],null,null);break;}tempNode = tempNode.lChild;//继续比较左子树} else {if (tempNode.rChild==null){tempNode.rChild = new TreeNode(elements[index],null,null);break;}tempNode = tempNode.rChild;//继续比较右子树}}}}/**中序输出这个二叉查找树*/@Overridepublic void output(ISearchCallBack searchCallBack) {// TODO Auto-generated method stubif (rootNode==null)return;_output(rootNode,searchCallBack);}/**中序输出这个二叉查找树[递归函数]*/private void _output(TreeNode node,ISearchCallBack searchCallBack){if (node.lChild!=null)//遍历左子树_output(node.lChild,searchCallBack);if (searchCallBack!=null)//访问根节点searchCallBack.visit(node);if (node.rChild!=null)//遍历右子树_output(node.rChild,searchCallBack);}@Overridepublic TreeNode search(Object e) {// TODO Auto-generated method stubreturn null;}@Overridepublic TreeNode search(Object e, ISearchCallBack searchCallBack) {// TODO Auto-generated method stubreturn null;}}

单元测试:

package org.pbdevj.ds.search.binarysearchtree.utest;import org.junit.Before;import org.junit.Test;import org.pbdevj.ds.search.binarysearchtree.BinarySearchTree;import org.pbdevj.ds.search.binarysearchtree.ISearch;import org.pbdevj.ds.search.binarysearchtree.ISearchCallBack;import org.pbdevj.ds.search.binarysearchtree.TreeNode;public class BinarySearchTreeTest {@Testpublic void testOutput(){ISearch search = new BinarySearchTree(new Object[]{50,30,10,20,60,90,70,45,43,32,38,44,21,20,55,65,67,76,77,88,77});search.output(new ISearchCallBack() {@Overridepublic void visit(TreeNode e) {// TODO Auto-generated method stubSystem.out.println(e.nodeValue);}});}}

车到山前必有路，没路可以先开路，开路就得有乐观，