有序二叉树的构建、遍历、查找

本文使用java写的有序二叉树，所谓有序二叉树，就是左子树上的数值小于树根上的值，树根的值小于右子树的值，创建过程很简单，只需要加上一个判断就可以，至于遍历，前序，中序，后序遍历需要使用栈来完成，于是使用递归的方法，层序遍历则需要使用队列，就是先将树根加到队列，然后每次取出队首元素，输出值，并将左右子树加入队列，循环至队列为空为止。下面是主要代码：

一、构建有序二叉树实现思路

• 如果左子树不为空，那么左子树上的所有值都均小于它的根节点的值
• 如果右子树不为空，那么右子树上的所有值都均大于或等于它的根节点的值
• 左，右子树也为二叉排序树
  
  新建TreeNode节点
  

public class TreeNode {
	
	private TreeNode leftTreeNode;  //左子树
	private TreeNode rightTreeNode; //右子树
	private Integer value;           //值
	
	public TreeNode(Integer value) {
		super();
		this.value = value;
	}
	
	public TreeNode getLeftTreeNode() {
		return leftTreeNode;
	}
	public void setLeftTreeNode(TreeNode leftTreeNode) {
		this.leftTreeNode = leftTreeNode;
	}
	public TreeNode getRightTreeNode() {
		return rightTreeNode;
	}
	public void setRightTreeNode(TreeNode rightTreeNode) {
		this.rightTreeNode = rightTreeNode;
	}
	public Integer getValue() {
		return value;
	}
	public void setValue(Integer value) {
		this.value = value;
	}
	
	@Override
	public String toString() {
		return "TreeNode [leftTreeNode=" + leftTreeNode + ", rightTreeNode=" + rightTreeNode + ", value=" + value + "]";
	}

}

public class BinaryTree {
	//新建二叉树
	TreeNode root;
 
	//获取二叉树的数据
	public TreeNode getRoot() {
	    return root;
	}
	
	/**
	 * 插入二叉树排序 有序插入 （大于根节点放右边 小于根节点放左边）
	 * 暂时没有处理相同节点  正常严谨二叉树不能出现相同节点
	 * @param value
	 */
	public void insert(Integer value) {

	    TreeNode newNode = new TreeNode(value);
	    if (root == null) {
	        root = newNode;
	        root.setLeftTreeNode(null);
	        root.setRightTreeNode(null);
	    } else {
	        TreeNode currentNode = root;
	        TreeNode parentNode;
	        // 有孩子继续循环，一直循环到最后一个节点 和插入的节点比较 大的放到右节点，小于放到左节点
	        while (true) {
	            parentNode = currentNode;
	            // 往右放
	            if (newNode.getValue() > currentNode.getValue()) {
	                currentNode = currentNode.getRightTreeNode();
	                if (currentNode == null) {
	                    parentNode.setRightTreeNode(newNode);
	                    return;
	                }
	            } else {
	                // 往左放
	                currentNode = currentNode.getLeftTreeNode();
	                if (currentNode == null) {
	                    parentNode.setLeftTreeNode(newNode);
	                    return;
	                }
	            }
	        }
	    }
	}


}

测试类

public class Test {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
	    BinaryTree tree = new BinaryTree();
	    tree.insert(5);
	    tree.insert(7);
	    tree.insert(4);
	    tree.insert(8);
	    tree.insert(6);
	    tree.insert(2);
	    tree.insert(3);
	    tree.insert(9);
	    System.out.println(tree.root);
	  
	}
}

二、二叉树的变量方式一共有四种

其中前中后序遍历采用了递归的方式进行

/**
	 * 中序遍历
	 * 
	 * @param treeNode
	 */
	public void inOrder(TreeNode treeNode) {
	    if (treeNode != null) {
	        inOrder(treeNode.getLeftTreeNode());
	        System.out.print(" " + treeNode.getValue() + " ");
	        inOrder(treeNode.getRightTreeNode());
	    }
	}

	/**
	 * 后序遍历
	 * 
	 * @param treeNode
	 */
	public void afterOrder(TreeNode treeNode) {
	    if (treeNode != null) {
	        afterOrder(treeNode.getLeftTreeNode());
	        afterOrder(treeNode.getRightTreeNode());
	        System.out.print(" " + treeNode.getValue() + " ");
	    }
	}

	/**
	 * 先序遍历
	 * 
	 * @param treeNode
	 */
	public void beforeOrder(TreeNode treeNode) {
	    if (treeNode != null) {
	        System.out.print(" " + treeNode.getValue() + " ");
	        beforeOrder(treeNode.getLeftTreeNode());
	        beforeOrder(treeNode.getRightTreeNode());
	    }
	}
 

最后再给大家介绍一下层序遍历

具体步骤如下：
1.首先申请一个新的队列，记为queue；
2.将头结点head压入queue中；
3.每次从queue中出队，记为node，然后打印node值，如果node左孩子不为空，则将左孩子入队；
4.如果node的右孩子不为空，则将右孩子入队；
5.重复步骤3，直到queue为空。

/**
	 * 层次遍历
	 */
	public  void levelOrder(){
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            root = queue.pop();
            System.out.print(root.getValue() + " ");
            if(root.getLeftreeNode() !=null) {
            	queue.add(root.getLeftreeNode());
            }
            if (root.getRigthTreeNode() !=null) {
            	 queue.add(root.getRigthTreeNode());
			}
        }
    }

三、二叉树的查找

1.定义一个指针指向根节点，如果指针指向的节点不等于我们的值，那么我们就一直循环去寻找。
2.指针指向的数据和我们要查找的值进行比较，如果我们查找的数据比当前值小，指针指向当前节点的左孩子如果我们查找的数据比当前值大，指针指向当前节点的右孩子
3.如果没有找打那么就返回 null

/**
	 *  数据查找
	 * @param value
	 * @return
	 */
	public TreeNode find(int value) {
		//定义一个指针指向根节点
		TreeNode currentNode = root;
		
		while (currentNode.getValue() != value) {
			if(value < currentNode.getValue()) {
				currentNode = currentNode.getLeftreeNode();
			}else {
				currentNode = currentNode.getRigthTreeNode();
			}
			 if( currentNode == null ) {
				 return null;
			 }
		}
		return currentNode;
		
	}