二叉排序树 插入 数据结构与算法（二）:线性表、栈、树(二叉树，AVL树)、图(2)

class TreeNode<E> {

E element;

TreeNode<E> left;

TreeNode<E> right;

public TreeNode(E e) {

element = e;

}

}

二叉查找树的三种遍历都可以直接用递归的方法来实现：

代码12 先序遍历

protected void preorder(TreeNode<E> root) {

if (root == null)

return;

System.out.println(root.element " ");

preorder(root.left);

preorder(root.right);

}

代码13 中序遍历

protected void inorder(TreeNode<E> root) {

if (root == null)

return;

inorder(root.left);

System.out.println(root.element " ");

inorder(root.right);

}

代码14 后序遍历

protected void postorder(TreeNode<E> root) {

if (root == null)

return;

postorder(root.left);

postorder(root.right);

System.out.println(root.element " ");

}

代码15 二叉查找树的简单实现

/**

* @author JackalTsc

*/

public class MyBinSearchTree<E extends Comparable<E>> {

// 根

private TreeNode<E> root;

// 默认构造函数

public MyBinSearchTree() {

}

// 二叉查找树的搜索

public boolean search(E e) {

TreeNode<E> current = root;

while (current != null) {

if (e.compareTo(current.element) < 0) {

current = current.left;

} else if (e.compareTo(current.element) > 0) {

current = current.right;

} else {

return true;

}

}

return false;

}

// 二叉查找树的插入

public boolean insert(E e) {

// 如果之前是空二叉树 插入的元素就作为根节点

if (root == null) {

root = createNewNode(e);

} else {

// 否则就从根节点开始遍历 直到找到合适的父节点

TreeNode<E> parent = null;

TreeNode<E> current = root;

while (current != null) {

if (e.compareTo(current.element) < 0) {

parent = current;

current = current.left;

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-60790-2.html