二叉排序树（也叫二叉搜索树、查找树）。
具有如下特点：
或者是一颗空树，或者是一颗具有如下性质的树：
1）若左子树不为空，那么左子树上面的所有节点的关键字值都比根节点的关键字值小
2）若右子树不为空，那么右子树上面的所有节点的关键字值都比根节点的关键字值大
3）左右子树都为二叉树
4）没有重复值
代码实践
1、树的表示形式：孩子表示法
/**
* 树中的节点
*/
public static class TreeNode {
int data; //本例中以 int 型数据为例
TreeNode leftChild;
TreeNode rightChild;
TreeNode parent;
public TreeNode(int data) {
this.data = data;
}
}
2、添加结点
/**
* 添加节点
*/
public TreeNode put(int data) {
if (root == null) { //空树
TreeNode node = new TreeNode(data);
root = node;
return node;
}
TreeNode node = root;
TreeNode parent = null;
while (node != null) {
parent = node;
if (data < node.data) {
node = node.leftChild;
} else if (data > node.data) {
node = node.rightChild;
} else { // 插入节点重复，直接返回
return node;
}
}
TreeNode newNode = new TreeNode(data);
if (data < parent.data) {
parent.leftChild = newNode;
} else {
parent.rightChild = newNode;
}
//切记别忘了（有点类似于双向链表的那种）
newNode.parent = parent;
return newNode;
}
3、树的遍历（中序LCR）
1、递归形式
/**
* 中序遍历
*/
public void midOrderTraverse(TreeNode root) {
if (root == null) {
return;
}
//LDR
midOrderTraverse(root.leftChild);
System.out.printf(root.data + " ");
midOrderTraverse(root.rightChild);
}
2、非递归形式
/**
* 中序遍历 非递归形式
*/
public void midOrderTraverse(TreeNode root){
if (root == null) return;
/**
* Stack 出站的顺序即 中序遍历 的顺序
*/
Stack stack = new Stack();
TreeNode target = root;
while (target != null){
stack.push(target);
target = target.leftChild;
}
while (!stack.isEmpty()){
TreeNode node = (TreeNode) stack.pop();
System.out.print(node.data + " ");
TreeNode tmp = node.rightChild;
while (tmp != null){
stack.push(tmp);
tmp = tmp.leftChild;
}
}
}
4、查找结点
/**
* 查找一个节点
*/
public TreeNode searchNode(int data) {
if (root == null) {
return null;
}
TreeNode node = root;
while (node != null) {
if (node.data == data) {
return node;
} else if (data > node.data) {
node = node.rightChild;
} else if (data < node.data) {
node = node.leftChild;
}
}
return null;
}
5、删除节点（难点）
删除节点时，所有可能出现的情况：
image.png
1、一种比较精简的实现方式：
/**
* 删除一个结点：参考TreeMap的方式，值赋值，效率高。
* <p>
* 这样的代码写起来精简，稍微不易读。每种条件判断排列组合以后，覆盖了所有情况。
*
* @param p 要删除的节点。
* 使用 ：
* TreeNode node = searchNode(3);
* tree.delNode(node);
*/
public void delNode(TreeNode p) {
if(p == null) throw new NoSuchElementException();
//左右孩子都存在的情况
if (p.leftChild != null && p.rightChild != null) {
TreeNode s = successor(p);
p.data = s.data;
p = s;
}
TreeNode replacement = p.leftChild != null ? p.leftChild : p.rightChild;
if (replacement != null) {
replacement.parent = p.parent;
if(p.parent == null){
root = replacement;
} else if (p.parent.leftChild == p) {
p.parent.leftChild = replacement;
} else if (p.parent.rightChild == p) {
p.parent.rightChild = replacement;
}
//注意这样写法
p.leftChild = p.rightChild = p.parent = null;
} else if (p.parent == null) {
root = null;
} else {
if (p.parent.leftChild == p) {
p.parent.leftChild = null;
} else {
p.parent.rightChild = null;
}
}
}
//寻找一个节点的后继节点
private TreeNode successor(TreeNode t) {
if (t == null) {
return null;
} else if (t.rightChild != null) {
TreeNode p = t.rightChild;
while (p.leftChild != null) {
p = p.leftChild;
}
return p;
} else {
TreeNode p = t.parent;
TreeNode ch = t;
while (p != null && ch == p.rightChild) {
ch = p;
p = p.parent;
}
return p;
}
}
2、引用赋值（代码复杂，思路简单）
/**
* 删除一个结点：注意各个指针之间的关系，没用的指针及时废掉。
*
* @param node 要删除的节点。
* 使用 ：
* TreeNode node = searchNode(3);
* tree.delNode(node);
*/
public void delNode(TreeNode node) {
if (node == null) {
throw new NoSuchElementException();
} else {
//先得到父节点，方便后边的操作
TreeNode parent = node.parent;
if (node.leftChild == null && node.rightChild == null) { //1、如果node是叶子节点
if (parent == null) { //根节点
root = null;
} else if (parent.leftChild == node) { //是某一个节点的左节点
parent.leftChild = null;
} else if (parent.rightChild == node) {// 是某一个节点的右节点
parent.rightChild = null;
}
node.parent = null;
} else if (node.leftChild != null && node.rightChild == null) { //2、node只有左子树
if (parent == null) { //根节点
root = node.leftChild;
node.leftChild = null; //断开连接
root.parent = null; //注意，因为root的parent为空，如果不设置会出问题
} else {
if (parent.leftChild == node) { //要删除的节点是父亲的左节点
parent.leftChild = node.leftChild;
node.leftChild.parent = parent;
} else { //要删除的节点是父亲的右节点
parent.rightChild = node.leftChild;
node.leftChild.parent = parent;
}
node.leftChild = null;
node.parent = null;
}
} else if (node.leftChild == null && node.rightChild != null) { //3、node只有右子树
if (parent == null) {
root = node.rightChild;
node.rightChild = null;
root.parent = null; //注意，因为root的parent为空，如果不设置会出问题
} else {
if (parent.leftChild == node) { //要删除的节点是父亲的左节点
parent.leftChild = node.rightChild;
node.rightChild.parent = parent;
} else if (parent.rightChild == node) { //要删除的节点是父亲的右节点
parent.rightChild = node.rightChild;
node.rightChild.parent = parent;
}
node.rightChild = null;
node.parent = null;
}
} else if (node.leftChild != null && node.rightChild != null) {//4、有左右两个孩子
if (node.rightChild.leftChild == null) { //如果被删除节点的右孩子节点的左子树为空，则直接补上右孩子节点
if (parent == null) { //要删除的是根节点
root = node.rightChild;
node.rightChild.leftChild = node.leftChild;
node.leftChild.parent = node.rightChild;
node.leftChild = null;
node.rightChild = null;
root.parent = null; //尽管只移动了root指针，此时要记得置空
} else {
if (parent.leftChild == node) { //要删除的节点是父节点的左节点
parent.leftChild = node.rightChild;
node.rightChild.parent = parent;
node.rightChild.leftChild = node.leftChild;
node.leftChild.parent = node.rightChild;
} else {//要删除的节点是父节点的右节点
parent.rightChild = node.rightChild;
node.rightChild.parent = parent;
node.rightChild.leftChild = node.leftChild;
node.leftChild.parent = node.rightChild;
}
node.leftChild = null;
node.rightChild = null;
node.parent = null;
}
} else { //如果被删除节点的右孩子节点的左子树不为空，则补上左子树中最小的一个
TreeNode minLeftNode = getMinLeftTreeNode(node.rightChild);
//处理好最左侧节点的事情
minLeftNode.parent.leftChild = minLeftNode.rightChild;
if (minLeftNode.rightChild != null) {
minLeftNode.rightChild.parent = minLeftNode.parent;
}
//设置移动节点 的左孩子
minLeftNode.leftChild = node.leftChild;
node.leftChild.parent = minLeftNode;
//设置移动节点 的右孩子
minLeftNode.rightChild = node.rightChild;
node.rightChild.parent = minLeftNode;
if (parent == null) {//要删除的节点是根节点
//设置为根节点
root = minLeftNode;
root.parent = null;
} else {
if (parent.leftChild == node) { //要删除的节点是自己父亲节点的左节点
parent.leftChild = minLeftNode;
minLeftNode.parent = parent;
} else { //要删除的节点是自己父亲节点的右节点
parent.rightChild = minLeftNode;
minLeftNode.parent = parent;
}
}
node.leftChild = null;
node.rightChild = null;
node.parent = null;
}
}
}
}
/**
* 获取一个二叉排序树中最小的节点
*/
private TreeNode getMinLeftTreeNode(TreeNode node) {
if (node == null) {
return null;
} else {
TreeNode curNode = node;
while (curNode.leftChild != null) {
curNode = curNode.leftChild;
}
return curNode;
}
}
完整代码：
/**
* <p>Description : 二叉排序树</p>
* 或者是一颗空树，或者是一颗具有如下性质的树：
* 1）若左子树不为空，那么左子树上面的所有节点的关键字值都比根节点的关键字值小
* 2）若右子树不为空，那么右子树上面的所有节点的关键字值都比根节点的关键字值大
* 3）左右子树都为二叉树
* 4）没有重复值
*/
public class SearchBinaryTree {
//根节点
public TreeNode root;
/**
* 树中的节点
*/
public static class TreeNode {
int data; //本例中以 int 型数据为例
TreeNode leftChild;
TreeNode rightChild;
TreeNode parent;
public TreeNode(int data) {
this.data = data;
}
}
/**
* 添加节点
*/
public TreeNode put(int data) {
if (root == null) { //空树
TreeNode node = new TreeNode(data);
root = node;
return node;
}
TreeNode node = root;
TreeNode parent = null;
while (node != null) {
parent = node;
if (data < node.data) {
node = node.leftChild;
} else if (data > node.data) {
node = node.rightChild;
} else { // 插入节点重复，直接返回
return node;
}
}
TreeNode newNode = new TreeNode(data);
if (data < parent.data) {
parent.leftChild = newNode;
} else {
parent.rightChild = newNode;
}
//切记别忘了（有点类似于双向链表的那种）
newNode.parent = parent;
return newNode;
}
/**
* 中序遍历 非递归形式
*/
public void midOrderTraverse(TreeNode root){
if (root == null) return;
/**
* Stack 出站的顺序即 中序遍历 的顺序
*/
Stack stack = new Stack();
TreeNode target = root;
while (target != null){
stack.push(target);
target = target.leftChild;
}
while (!stack.isEmpty()){
TreeNode node = (TreeNode) stack.pop();
System.out.print(node.data + " ");
TreeNode tmp = node.rightChild;
while (tmp != null){
stack.push(tmp);
tmp = tmp.leftChild;
}
}
}
/**
* 查找一个节点
*/
public TreeNode searchNode(int data) {
if (root == null) {
return null;
}
TreeNode node = root;
while (node != null) {
if (node.data == data) {
return node;
} else if (data > node.data) {
node = node.rightChild;
} else if (data < node.data) {
node = node.leftChild;
}
}
return null;
}
/**
* 删除一个结点：参考TreeMap的方法，值复制，效率高。
* <p>
* 这样的代码写起来精简，稍微不易读。每种条件判断排列组合以后，覆盖了所有情况。
*
* @param p 要删除的节点。
* 使用 ：
* TreeNode node = searchNode(3);
* tree.delNodeNew(node);
*/
public void delNode(TreeNode p) {
if(p == null) throw new NoSuchElementException();
//左右孩子都存在的情况
if (p.leftChild != null && p.rightChild != null) {
TreeNode s = successor(p);
p.data = s.data;
p = s;
}
TreeNode replacement = p.leftChild != null ? p.leftChild : p.rightChild;
if (replacement != null) {
replacement.parent = p.parent;
if(p.parent == null){
root = replacement;
} else if (p.parent.leftChild == p) {
p.parent.leftChild = replacement;
} else if (p.parent.rightChild == p) {
p.parent.rightChild = replacement;
}
//注意这样写法
p.leftChild = p.rightChild = p.parent = null;
} else if (p.parent == null) {
root = null;
} else {
if (p.parent.leftChild == p) {
p.parent.leftChild = null;
} else {
p.parent.rightChild = null;
}
}
}
//寻找一个节点的后继节点
private TreeNode successor(TreeNode t) {
if (t == null) {
return null;
} else if (t.rightChild != null) {
TreeNode p = t.rightChild;
while (p.leftChild != null) {
p = p.leftChild;
}
return p;
} else {
TreeNode p = t.parent;
TreeNode ch = t;
while (p != null && ch == p.rightChild) {
ch = p;
p = p.parent;
}
return p;
}
}
}
网友评论