今天刷题时候碰到了一个二叉排序树的问题 忽然发现我连二叉排序树是啥都不知道 : ) 看了下资料 自己敲了代码 现在记录一哈
二叉排序树 是一颗有规则的二叉树 它的左子树永远比他的根节点小，而根节点永远比右子树小 。 所以用中序遍历可以得到一个递增的集合。
关于二叉排序树的结构 ： 值 value，左子树节点，右子树节点，还有双亲节点
class TreeNode1{ int val; TreeNode1 left; TreeNode1 right; TreeNode1 p; public TreeNode1(int v){ this.val = v; } }它有一些简单的方法 这里不一一叙述 看函数名就知道
public static TreeNode1 getMinNode(TreeNode1 T){ if(T == null){ return T; } while(T.left != null){ T = T.left; } return T; } public static TreeNode1 getMaxNode(TreeNode1 T){ if(T == null){ return T; } while(T.right != null){ T = T.right; } return T; } public static TreeNode1 foundNode(int v){ TreeNode1 t = head; while(t != null){ if(t.val == v){ return t; } if(t.val > v){ t = t.left; }else{ t = t.right; } } return null; }它有一些操作 例如插入、删除 。 下面是它的插入操作。 每插入一个节点 我们需要从根节点开始 判断这个插入节点的值大于还是小于当前节点的值 如果大于 那么它就应该放在当前节点的右子树中 如果小于 就放在当前节点的左子树中 这样迭代 直到我们遍历到的节点是null
public static void insert(TreeNode1 T,TreeNode1 t){ TreeNode1 f = T; TreeNode1 pre = null; while(true){ pre = f; if(f.val > t.val){ f = f.left; if(f == null){ pre.left = t; break; } }else{ f = f.right; if(f == null){ pre.right = t; break; } } } t.left = null; t.right = null; t.p = pre; }下面是删除操作 这个操作比较复杂 大体可以分为三种情况： 1、 要删除的节点是一个叶子节点 这个时候很简单 直接删除这个节点就行。 2、 要删除的节点的左子树或者右子树为空 这个也简单 就用这个节点的另外一颗子树代替这个节点就可以 3、 要删除的节点既有左子树也有右子树 。 这个时候就比较复杂了，但是不要慌 也只需要两个步骤就可以搞定。 首先 我们先找到这个删除节点的后继节点 所谓后继节点 就是遍历时它的后面一个节点 （比他大的最小的节点）（必定在它的右子树中 因为它的左子树都比它小 它的右子树都比他大 而且这个节点必定没有左子树 因为他是删除节点的右子树中的最小值） 找到这个节点后 我们再判断这个后继节点是否就是删除节点的右孩子 如果是右孩子就直接用删除节点的右孩子替换删除节点。 如果不是 那么就先用这个后继节点的右孩子代替后继节点，然后再用这个后继节点代替删除节点就搞定了。
替换节点函数如下 ：
//用t节点替代T节点 public static void translate(TreeNode1 T,TreeNode1 t){ if(T.p == null){ head = t; }else if(T.p.left == T){ T.p.left = t; }else{ T.p.right = t; } t.p = T.p; }删除函数 ：
public static void deleteNode(int v){ TreeNode1 T = foundNode(v); if(T.left == null){ translate(T,T.right); }else if (T.right == null){ translate(T,T.left); }else{ //找到删除节点的后继节点（它的后一个元素 值比它大 是它右子树的最小值） TreeNode1 t = getMinNode(T.right); //如果这个后继节点就是删除节点的右子树 那么就直接用后继节点来代替删除节点 //如果不是，这个后继节点没有左子树（因为他是最小的元素），所以它的位置由它的右子树替代，然后用这个后继节点替代删除节点的位置 if(t.p != T){ translate(t,t.right); t.right = T.right; t.right.p = t; } translate(T,t); t.left = T.left; t.left.p = t; } }