二叉查找树

2019-11-08 01:37:33

字体：大中小

来源：转载

供稿：网友

取自java书籍，数据结构与算法分析。其中remove方法添加了理解信息。

1、整体源码结构

public Class BinarySearchTree<AnyType extends Comparable<? super AnyType>>{ //二叉树结构 PRivate static class BinaryNode<AnyType> { /*-----*/} private BinaryNode<AnyType> root; public BinarySearchTree() { root= null; } public void makeEmpty() {root= null;} public boolean isEmpty() {return root== null; } public boolean contains(AnyType x) {return contains(x, root);} public AnyType findMin() { if(isEmpty()) throw new UnderflowException(); return findMin(root).element; } public AnyType findMax() { if(isEmpty()) throw new UnderflowException(); return findMax(root).element; } public void insert(AnyType x) {root= insert(x, root);} public void remove(AnyType x) {root=remove(x, root);} public void printTree() private boolean contains(AnyType x, BinaryNode<AnyType> t) {/**************/} private BinaryNode<AnyType> findMin (BinaryNode<AnyType t) {/************/} private BinaryNode<AnyType> findMax (BinaryNode<AnyType t) {/************/} private BinaryNode<AnyType> insert(AnyType x, BinaryNode<AnyType> t) {/************/} private BinaryNode<AnyType> remove(AnyType x, BinaryNode<AnyType> t) {/************/} private void printTree(BinaryNode<AnyType> t) {/******************/}}

1、结构节点元素值，左右子节点信息（类似链指向）

private static class BinaryNode(AnyType){ //Constructors BinaryNode(AnyType theElement) { this(theElement, null, null);} BinaryNode(AnyType theElement, BinaryNode<AnyType>lt, BinaryNode<AnyType> rt) { element=} AnyType element;//The data in the node BinaryNode<AnyType> left;//Left Child; BinaryNode<AnyType> right;//Right Child;}

3、contains 方法, 比较简单，注意null的处理

private boolean contains(AnyType x, BinaryNode<AnyType> t){ if(t==null) return false; int compareResult= x.compareTo(t.element); if(compareResult < 0) return contains(x, t.left); else if(compareResult > 0) return contains(x, t.right); else return true; //Math}

4、findMin, findMax findMin 从根开始一直遍历左儿子，终点就是最小值。同理，findMax向右遍历

/********findMin*********/private BinaryNode<AnyType> findMin (BinaryNode<AnyType> t){ if(t == null) return null; else if(t.left == null) return t; return findMin(t.left);}/******findMax*******/private BinaryNode<AnyType> findMax(BinaryNode<AnyType> t){ if(t == null) return null; else if(t.right == null) return t; return findMax(t.right);}

5、insert 方法

private BinaryNode<AnyType> insert(AnyType x, BinaryNode<AnyType> t){ if( t== null) return new BinaryNode<> (x, null, null); int compareResult= x.compareTo(t.element); if(compareResult < 0) t.left= insert(x, x.left);//t.left 就是为了保持新建立父到子的链 else if(compareResult > 0) t.right= insert(x, t.right);//t.right 保持新建链 else ;//Duplicate; do nothing return t;}

6、remove方法分三种情况 1、节点为叶子，直接删除，不会破坏树结构 2、节点有且仅有一个儿子，该节点可在其父节点调整链绕过该节点。删除该节点 3、节点有2个儿子，根据二叉树的定义，策略为，在右子树找到最小值替换该节点的元素值data，不改变该节点树结构。再递归删除该节点（最小值节点），（删除时，链结构也要调整）记住。右子树中的最小的节点不可能有左儿子，所以remove节点要容易。

private BinaryNode<AnyType> remove (AnyType x, BinaryNode<AnyType> t){ if(t== null) return t;//Item not found; do nothing int compareResult= x.compareTo(t.element); if(compareResult< 0) t.left= remove(x, t.left);//t.left= 为了保持链 else if(compareResult> 0) t.right= remove(x, right);//t.right= 为了保持链 else if(t.left != null && t.right != null)// two children { t.element=findMin(t.right).element;//替换元素值 t.right= remove(t.element, t.right);//递归删除右子树的最小值并且t.right 保持新建里的链关系 } else //one child 时直接子覆盖父 //no child 返回null t=(t.left != null) ? t.left: t.right; return t;}

总结：理解上特别注意insert 和remove 通过递归返回t.left= or t.right 很好了保持了原有不需要改变的树结构，同时可以建立新的树结构。几乎就是遍历了一遍，有需要的就去修改树结构链

上一篇：Feb_0219_Leetcode_32_Longest Valid Parentheses

下一篇：bzoj2435: [Noi2011]道路修建树上dp