二叉搜索树
建立二叉搜索树
基本骨架
//因为视频考虑到实用性 加了泛型、 //E元素遵循Comparable接口 //extends Comparable 转化为组合 更加灵活 class BinarySearchTree<E> { private Integer size = 0; public Node root; public Comparator comparator; public BinarySearchTree(Comparator comparator) { this.comparator = comparator; } public BinarySearchTree() { } public Integer size() { return size; } public boolean isEmpty() { //if(root==null)return true; //return false; return size == 0; } public boolean contains(E element) { return true; } }节点类
class Node<E> { E element; Node<E> left; Node<E> right; Node<E> parent; public Node(E e, Node<E> parent) { this.element = e; this.parent = parent; } }节点处理器 我们就可以除了写输出外 还可以进行一些操作
//节点处理器需要提取出来 interface Visitor<E> { //---> abstract 增加一个stop 用于控制程序 // 不太适合用一个全局变量然后作为参数 因为基本类型 所有的方法不是共用一个 //boolean flag = true; //如果在处理器中进行拦截的话 递归还是在运行 //改为 ---> visitor实现类 参考截图 void visit(E element); }节点输出
@Override public String toString() { StringBuffer sb = new StringBuffer(); toString(root, sb, ""); return sb.toString(); } private void toString(Node node, StringBuffer sb, String prefix) { if (node == null) return; toString(node.left, sb, prefix + "L---"); sb.append(prefix).append(node.element).append("\n"); toString(node.right, sb, prefix + "R---"); } }
需要指定比较方式 且 不允许为null
比较器代码
// e1==e2为等于0, e1>e2为大于0, e1<e2为小于0 public int compare(E e1, E e2) { //return e1.compareTo(e2); if (comparator != null) return comparator.compare(e1, e2); else { //更加完美的比较器 如果没法比较 说明元素有问题 return ((Comparable) e1).compareTo(e2); } } //节点不能为空 private void elementNotNullCheck(E element) { if (element == null) throw new RuntimeException(); }比较器的实现类
//这样就可以自定义比较器 //可以写为匿名类 class MyComparator implements Comparator<Integer> { @Override public int compare(Integer t1, Integer t2) { return t2 - t1; } }
接口设计
图解
- 添加节点
public void add(E element) { elementNotNullCheck(element); //添加的是第一个节点 if (root == null) { root = new Node(element, null); size++; return; } //添加不是第一个节点 Node<E> temp = root; Node<E> parent = null; int cmp = 0; while (temp != null) { parent = temp; cmp = compare(temp.element, element); if (cmp == 0) { //覆盖掉原先的node 大部分是有必要的 直接赋值 Node的结构没有发生变化 temp.element = element; return; } else if (cmp > 0) { temp = temp.left; } else if (cmp < 0) { temp = temp.right; } } //必须要一个父节点来操作 否则会报错 无法代替add效果 //涉及到指针问题 直接赋值 temp 直接指针到新节点，而parent的对应子节点还是null //temp = new Node(val,parent); if (cmp > 0) { parent.left = new Node(element, parent); } else { parent.right = new Node(element, parent); } size++; }
前序遍历：树状结构展示（注意左右子树）
代码
//前序遍历 public void preOrder(Node<E> node) { if (node == null) return; System.out.println(node.element); preOrder(node.left); preOrder(node.right); } public void preOrderRe(Node<E> node) { Stack<Node> stack = new Stack<Node>(); stack.push(node); while (!stack.isEmpty()) { Node temp = stack.pop(); if (temp != null) { System.out.println(temp.element); if (temp.right != null) { stack.add(temp.right); } if (temp.left != null) { stack.add(temp.left); } } } }
中序遍历：二叉搜索树的中序遍历按升序或者降序处理节点
代码
//中序遍历 public void midOrder(Node<E> node) { if (node == null) return; midOrder(node.left); System.out.println(node.element); midOrder(node.right); } public void midOrderRe(Node<E> node) { Stack<Node> stack = new Stack<Node>(); Node temp = node; while (temp != null || !stack.isEmpty()) { while (temp != null) { stack.push(temp); temp = temp.left; } temp = stack.pop(); System.out.println(temp.element); temp = temp.right; } }
后序遍历：适用于一些先子后父的操作
代码
//后序遍历 public void postOrder(Node<E> node) { if (node == null) return; postOrder(node.left); postOrder(node.right); System.out.println(node.element); } public void postOrderRe(Node<E> node) { Stack<Node> stack = new Stack<Node>(); Node temp = node; Node last = null; while (temp != null || !stack.isEmpty()) { while (temp != null) { stack.push(temp); temp = temp.left; } temp = stack.peek(); if (temp.right == null || temp.right == last) { System.out.println(temp.element); stack.pop(); last = temp; temp = null; } else { temp = temp.right; } } }
层次遍历
- 代码
//层次遍历 public void levelOrder(Node<E> node, Visitor<E> visitor) { if (node == null) return; Queue<Node> queue = new LinkedList<Node>(); Node temp = node; queue.offer(node); //不要用add while (!queue.isEmpty()) { node = queue.poll(); //处理器提取出来 visitor.visit(node.element); if (node.left != null) queue.add(node.left); if (node.right != null) queue.add(node.right); } }
计算高度 可以参考leetcode
- 代码
if(node==null) return 0; return 1+ Math.max(height(node.left),height(node.right)); 非递归就可用层次遍历 1 -- 2 -- 4 -- 8 ---...
判断是不是完全二叉树
遍历一个一个节点 if(node.left==null&&node.right!=null) return false;
还有一种情况是if(node.left!=null){ queue.offer(node.left) }
翻转二叉树
- 代码
左右交换 子节点递归
重构二叉树 前序+中序 参考leetcode
- 代码
class Solution { int index = 0; public TreeNode buildTree(int[] preorder, int[] inorder) { return createBuild(preorder,inorder,0,preorder.length-1); } public TreeNode createBuild(int []preorder,int[]inorder,int start ,int end){ if(start>end)return null; int val = preorder[index++]; TreeNode root = new TreeNode(val); for (int i = 0; i < inorder.length; i++) { if(inorder[i]==val){ root.left = createBuild(preorder,inorder,start ,i-1); root.right = createBuild(preorder,inorder,i+1 , end); break; } } return root; } }
前驱结点
- 讲解
- 实现代码
public Node<E> predecessor(Node<E> node) { if (node == null) return null; Node temp = null; if (node.left != null) { temp = node.left; while (temp.right != null) { temp = temp.right; } return temp; } temp = node; while (temp.parent.left == temp && node.parent != null) { temp = temp.parent; } return temp.parent; }
后继节点
删除节点--叶子节点
- 直接删除 度为0
删除节点 ---度为1的节点 需要考虑parent的问题
删除节点 度为2的节点
- 前驱点或者后继点来取代自己
public class Solution {
public static void main(String[] args) {
BinarySearchTree bst = new BinarySearchTree();
bst.add(7);
bst.add(4);
bst.add(9);
bst.add(2);
bst.add(5);
bst.add(8);
bst.add(11);
bst.add(3);
bst.add(12);
bst.add(1);
bst.remove(5);
System.out.println(bst.toString());
System.out.println("-----");
bst.remove(11);
System.out.println(bst.toString());
System.out.println("-----");
bst.remove(2);
System.out.println(bst.toString());
System.out.println("-----");
}
}
class BinarySearchTree<E> {
private Integer size = 0;
public Node root;
public Comparator comparator;
public BinarySearchTree() {
}
public BinarySearchTree(Comparator comparator) {
this.comparator = comparator;
}
public Integer size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public boolean contains(E element) {
if (findNode(element) != null) return true;
return false;
}
public void remove(E element) {
Node node = findNode(element);
if (node == null) return;
if (node.right != null && node.left != null) {
Node temp = temp = predecessor(element);
node.element = temp.element;
node = temp;
}
//node这里度为1或者0 度为2已经转化成度为1或者0
Node<E> replace = node.left != null ? node.left : node.right;
if (replace != null) { // 说明是度为1的节点
replace.parent = node.parent; //需要更改原先的parent的指向
if (node.parent == null) {
root = replace;
//root.parent = null;
} else if (node == node.parent.left) {
node.parent.left = replace;
//replace.parent = node.parent; //需要更改原先的parent的指向
} else if (node == node.parent.right) {
node.parent.right = replace;
//replace.parent = node.parent;
}
} else if (node.parent == null) {
root = null;
} else {
if (node == node.parent.left) node.parent.left = null;
else node.parent.right = null;
}
size--;
}
public void clear() {
root = null;
}
public Node<E> predecessor(E element) {
Node node = findNode(element);
if (node == null) return null;
Node temp = null;
if (node.left != null) {
temp = node.left;
while (temp.right != null) {
temp = temp.right;
}
return temp;
}
temp = node;
while (temp.parent.left == temp && node.parent != null) {
temp = temp.parent;
}
return temp.parent;
}
private Node<E> findNode(E e) {
if (root == null || e == null) return null;
Node<E> temp = root;
while (temp != null) {
if (compare(temp.element, e) > 0) {
temp = temp.left;
} else if (compare(temp.element, e) < 0) {
temp = temp.right;
} else {
break;
}
}
return temp;
}
public int compare(E e1, E e2) {
//return e1.compareTo(e2);
if (comparator != null) return comparator.compare(e1, e2);
else {
return ((Comparable) e1).compareTo(e2);
}
}
private void elementNotNullCheck(E element) {
if (element == null) throw new RuntimeException();
}
public void add(E element) {
elementNotNullCheck(element);
if (root == null) {
root = new Node(element, null);
size++;
return;
}
Node<E> temp = root;
Node<E> parent = null;
int cmp = 0;
while (temp != null) {
parent = temp;
cmp = compare(temp.element, element);
if (cmp == 0) {
temp.element = element;
return;
} else if (cmp > 0) {
temp = temp.left;
} else if (cmp < 0) {
temp = temp.right;
}
}
if (cmp > 0) {
parent.left = new Node(element, parent);
} else {
parent.right = new Node(element, parent);
}
size++;
}
@Override
public String toString() {
StringBuffer sb = new StringBuffer();
toString(root, sb, "");
return sb.toString();
}
private void toString(Node node, StringBuffer sb, String prefix) {
if (node == null) return;
toString(node.left, sb, prefix + "L---");
sb.append(prefix).append(node.element).append("\n");
toString(node.right, sb, prefix + "R---");
}
}
class Node<E> {
E element;
Node<E> left;
Node<E> right;
Node<E> parent;
public Node(E e, Node<E> parent) {
this.element = e;
this.parent = parent;
}
} 
大疆公司福利 177人发布