二叉查找树

二叉树概念

二叉树是一种层次结构，要么是空集，要么是由一个称为根（root）和两棵不同的二叉树（左子树（left subtree）和右子树（right subtree））。允许子树一棵或者两棵为空，没有孩子的结点称为叶节点（leaf）。

一条路径的长度（length）是指这条路径上的边的个数，一个结点的深度（depth）是指从根结点到该结点的路径长度，根节点的深度为0。给定深度的结点的集合称为该树的一层（level）。兄弟结点是共享同一父结点的结点。 空树的高度为0，非空树的高度是从根到最远非空路径长度+1。

二叉查找树概念（BST）

一种称为二叉查找树（binary search tree）的特殊二叉树非常有用。二叉查找树的定义：首先是没有重复元素，然后对于树中的每一个结点，左子树结点值都小于该结点，右子树大于该结点。

查找元素

可以从根节点开始向下扫描，直到找到一个匹配元素，或者达到一个空子树为止。

public boolean search(E e) { TreeNode<E> current = root;// Start from the root while (current!= null) { if(e.compareTo(current.element) < 0) { current = current.left; } else if (e.compareTo(current.element) > 0) { current = current.right; } else // element matches current.element return true; //Element is found } return false; }

插入元素

关键思路是确定新结点的父节点的位置，如果这棵树是空的，就用新元素创建一个根结点，否则寻找元素结点的父结点。和查找方法差不多：

public boolean insert(E e) { if (root== null) root = createNewNode(e); // Create a new root else { //Locate the parent node TreeNode<E> parent = null; TreeNode<E> current =root; while (current!= null) if(e.compareTo(current.element) < 0) { parent = current; current = current.left; } else if (e.compareTo(current.element) > 0) { parent = current; current = current.right; } else return false; //Duplicate node not inserted //Create the new node and attach it to the parent node if(e.compareTo(parent.element) < 0) parent.left = createNewNode(e); else parent.right = createNewNode(e); } size++; return true; //Element inserted } protected TreeNode<E>createNewNode(E e) { return new TreeNode<E>(e); }

树的遍历

遍历有很多种：中序（inorder）、前序（preorder）、后序（postorder）、深度优先（depth-first）和广度优先（breadth-first）。

中序遍历法，首先递归地访问当前结点的左子树，然后访问当前结点，最后递归地访问该结点的右子树。

后序遍历，左右中。

前序遍历，中左右。

深度优先遍历法与前序遍历法相同。

广度优先遍历法逐层访问树中结点。

先序遍历；中序遍历；后续遍历；层次遍历。事实上，知道任意两种方式，并不能唯一地确定树的结构，但是，只要知道中序遍历和另外任意一种遍历方式，就一定可以唯一地确定一棵树。

上述几种遍历方法只能显示树中的元素，如果要处理二叉树中的元素，就得使用iterator。该迭代器继承了Iterator类，从而可以中序、前序和后序遍历二叉树。如果要保证数据结构遍历灵活可以将迭代器定义为ListIterator 的子类，可以前向遍历和后向遍历。

删除元素

为了删除一个元素，需要定位包含该元素的结点以及他的父结点。本质：找到左子树种元素最大值然后替换该结点。

情况1：

当前结点没有没有左孩子，只需讲该结点的父结点和当前结点的右孩子相连。

 

情况2：

要删除的current结点有一个左孩子。假设rightMost指向包含current结点的左子树中最大元素的结点，parentOfRightMost指向rightMost结点的父结点。使用right结点的元素值替换current结点元素值。将parentOfRightMost和rightMost结点的左孩子相连，special case需要注意。

public boolean delete(E e) { //Locate the node to be deleted and also locate its parent node TreeNode<E> parent = null; TreeNode<E> current = root; while (current!= null) { if(e.compareTo(current.element) < 0) { parent = current; current = current.left; } else if (e.compareTo(current.element) > 0) { parent = current; current = current.right; } else break; // Element is in the tree pointed bycurrent } if (current== null) return false; //Element is not in the tree //Case 1: current has no left children if(current.left == null) { //Connect the parent with the right child of the current node if (parent== null) { root = current.right; } else { if(e.compareTo(parent.element) < 0) parent.left = current.right; else parent.right = current.right; } } else { //Case 2: The current node has a left child //Locate the rightmost node in the left subtree of //the current node and also its parent TreeNode<E>parentOfRightMost = current; TreeNode<E> rightMost= current.left; while(rightMost.right != null) { parentOfRightMost = rightMost; rightMost = rightMost.right; // Keep going to the right } //Replace the element in current by the element in rightMost current.element = rightMost.element; //Eliminate rightmost node if(parentOfRightMost.right == rightMost) parentOfRightMost.right =rightMost.left; else // Special case: parentOfRightMost == current parentOfRightMost.left =rightMost.left; } size--; return true; //Element inserted }