Java-如何创建二叉查找树

原文来自：https://goo.gl/EieLZK

简介

这篇文章主要讲如何创建二叉查找树。如果有哪些不对的地方请指正，欢迎批评和建议。

要点

本文将依照一下的几点介绍

什么是二叉查找数二叉查找树的遍历代码例子

二叉查找树的定义

一个二叉树如果想成为二叉查找树需要满足以下条件： （1）若任意节点的左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值； （2）若任意节点的右子树不为空，则右子树上所有节点的值均大于或等于根节点的值； （3）任意节点的左、右子树也分别为二叉查找树。

下图所示为一棵二叉查找树

二叉查找树的遍历

二叉查找树的遍历和普通的二叉树遍历没有本质上的区别。

（1）先序遍历：按照 根-左子树-右子树 的顺序遍历； （2）中序遍历：按照 左子树-根-右子树 的顺序遍历； （3）后序遍历：按照 左子树-右子树-根 的顺序遍历

代码例子

给出数组：{20, 15, 200, 25, -5, 0, 100, 20, 12, 126, 1000, -150} 作为节点上的值，如何创建以及遍历二叉查找数呢？我们此处假设根节点的值为20（可以选择任意一个值作为根节点值）。

public class TreeNode { int val; public TreeNode left; public TreeNode right; public TreeNode(int x) { val = x; } public void addNode(int num) { if (num < this.val) { if (this.left != null) { this.left.addNode(num); } else { this.left = new TreeNode(num); } return; } if (this.right != null) { this.right.addNode(num); } else { this.right = new TreeNode(num); } return; } // Visit the node first, then left and right sub-trees public void traversePreOrder() { System.out.println(this.val); if (this.left != null) { this.left.traversePreOrder(); } if (this.right != null) { this.right.traversePreOrder(); } } // Visit left sub-tree, then node and then, right sub-tree public void traverseInOrder() { if (this.left != null) { this.left.traverseInOrder(); } System.out.println(this.val); if (this.right != null) { this.right.traverseInOrder(); } } // Visit left sub-tree, then right sub-tree and then the node public void traversePostOrder() { if (this.left != null) { this.left.traversePostOrder(); } if (this.right != null) { this.right.traversePostOrder(); } System.out.println(this.val); } }