一、概述
二叉查找树 又称为 二叉搜索树，它是一棵空树，或者是具有下列性质的 二叉树
- 若左子树不空，则左子树上所有结点的值均小于或等于它的结点
- 若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值
- 左、右子树也分别为二叉查找树
下面我们就来一起梳理一下和二叉查找树相关的知识点：
- 建立二叉查找树
- 删除二叉查找树中指定元素
- 非递归遍历二叉查找树（先序遍历、中序遍历、后序遍历）
二、代码实现
2.1 建立二叉查找树
解决思路
二叉查找树可以用Tree来表示，它包含一个root变量，用于存放这棵树的根结点，size表示树中元素的个数，每个结点Node包含以下的变量：
parent：指向其父结点left、right：分别指向它的左孩子和右孩子value：该结点存储的值
代码实现
下面我们输入一个数组p，通过它建立一个二叉查找树，并通过 递归中序遍历 的方式打印出树中的元素，按照二叉查找树的定义，最后输出的结果必然是递增排序的。
class Untitled { static class Tree { int size; Node root; } static class Node { Node parent; Node left; Node right; int value; } static void insertNode(Tree tree, int value) { if (tree == null) { return; } Node tNode = tree.root; //待插入结点的父结点，如果遍历完为空，说明此时是一个空树。 Node pNode = null; //新的结点。 Node nNode = new Node(); nNode.value = value; while (tNode != null) { pNode = tNode; if (tNode.value > value) { tNode = tNode.left; } else { tNode = tNode.right; } } nNode.parent = pNode; if (pNode == null) { tree.root = nNode; } else if (pNode.value > value) { pNode.left = nNode; } else { pNode.right = nNode; } tree.size++; } static Tree createBinTree(int p[], int len) { Tree tree = new Tree(); for (int i=0; i 运行结果
>> 1>> 2>> 3>> 4>> 5>> 6复制代码
2.2 删除二叉查找树中指定元素
解决思路
在二叉查找树中删除某个元素，其核心思想就是 找到待删除结点的父结点，并将该父结点的left或right指向 待删除结点的孩子结点
- 如果待删除结点只有一个孩子结点，那么用 该孩子结点替换待删除结点 即可。
- 如果待删除结点有两个孩子结点，那么就需要进行如下几步操作：
- 第一步：找到 待删除结点的右子树的最小结点 作为替换结点，如果该结点不是右子树的根节点，那么还需要 先用最小结点的右结点来替换最小结点
- 第二步：用第一步找到的结点替换待删除结点
- 第三步：将待删除结点的左子树的根节点嫁接到替换结点 上。
实现代码
class Untitled { static class Tree { int size; Node root; } static class Node { Node parent; Node left; Node right; int value; } static void insertNode(Tree tree, int value) { if (tree == null) { return; } Node tNode = tree.root; //待插入结点的父结点，如果遍历完为空，说明此时是一个空树。 Node pNode = null; //新的结点。 Node nNode = new Node(); nNode.value = value; while (tNode != null) { pNode = tNode; if (tNode.value > value) { tNode = tNode.left; } else { tNode = tNode.right; } } nNode.parent = pNode; if (pNode == null) { tree.root = nNode; } else if (pNode.value > value) { pNode.left = nNode; } else { pNode.right = nNode; } tree.size++; } static Tree createBinTree(int p[], int len) { Tree tree = new Tree(); for (int i=0; i value) { node = node.left; } else if (node.value < value) { node = node.right; } else { find = node; break; } } return find; } static Node minNode(Node node) { while (node != null && node.left != null) { node = node.left; } return node; } static void transPlant(Tree tree, Node deleteNode, Node replaceNode) { if (deleteNode.parent == null) { tree.root = replaceNode; } else if (deleteNode.parent.left == deleteNode) { deleteNode.parent.left = replaceNode; } else if (deleteNode.parent.right == deleteNode) { deleteNode.parent.right = replaceNode; } if (replaceNode != null) { replaceNode.parent = deleteNode.parent; } } static void deleteNode(Tree tree, int value) { if (tree == null) { return; } Node deleteNode = searchNode(tree, value); if (deleteNode != null) { if (deleteNode.left == null) { transPlant(tree, deleteNode, deleteNode.right); } else if (deleteNode.right == null) { transPlant(tree, deleteNode, deleteNode.left); } else { Node replaceNode = minNode(deleteNode.right); if (replaceNode != deleteNode.right) { transPlant(tree, replaceNode, replaceNode.right); deleteNode.right.parent = replaceNode; replaceNode.right = deleteNode.right; } transPlant(tree, deleteNode, replaceNode); deleteNode.left.parent = replaceNode; replaceNode.left = deleteNode.left; } } } //递归的方式中序打印二叉查找树，最后输出的顺序必然是递增的。 static void printInOrder(Node node) { if (node == null) { return; } printInOrder(node.left); System.out.println(node.value); printInOrder(node.right); } public static void main(String[] args) { int p[] = { 3,5,6,1,2,4}; Tree tree = createBinTree(p, p.length); deleteNode(tree, 3); printInOrder(tree.root); }}复制代码 运行结果
>> 1>> 2>> 4>> 5>> 6复制代码
2.3 非递归遍历方式
解决思路
对于二叉树的递归遍历，相信大家已经很熟悉了，这里演示的是如何通过“栈”来实现二叉树的非递归遍历：
class Untitled { static class Tree { int size; Node root; } static class Node { Node parent; Node left; Node right; int value; } static void insertNode(Tree tree, int value) { if (tree == null) { return; } Node tNode = tree.root; //待插入结点的父结点，如果遍历完为空，说明此时是一个空树。 Node pNode = null; //新的结点。 Node nNode = new Node(); nNode.value = value; while (tNode != null) { pNode = tNode; if (tNode.value > value) { tNode = tNode.left; } else { tNode = tNode.right; } } nNode.parent = pNode; if (pNode == null) { tree.root = nNode; } else if (pNode.value > value) { pNode.left = nNode; } else { pNode.right = nNode; } tree.size++; } static Tree createBinTree(int p[], int len) { Tree tree = new Tree(); for (int i=0; i = 0) { while (node != null) { int value = node.value; System.out.println(node.value); index++; p[index] = node; node = node.left; } if (index >= 0) { node = p[index]; p[index] = null; index--; } node = node.right; } } //中序遍历。 static void printInOrder(Tree tree) { Node p[] = new Node[tree.size]; int index = -1; Node node = tree.root; while (node != null || index >= 0) { while (node != null) { int value = node.value; index++; p[index] = node; node = node.left; } if (index >= 0) { node = p[index]; System.out.println(node.value); p[index] = null; index--; } node = node.right; } } //后序遍历。 static void printPostOrder(Tree tree) { Node p[] = new Node[tree.size]; int index = 0; Node curNode = tree.root; Node preNode = null; p[index] = curNode; while (index >= 0) { curNode = p[index]; //如果没有孩子结点。 boolean hasNoChild = (curNode.left == null && curNode.right == null); //如果它的左孩子或者右孩子已经被访问过。 boolean hasVisit = preNode == curNode.left || preNode == curNode.right; if (hasNoChild || hasVisit) { System.out.println(curNode.value); p[index] = null; index--; preNode = curNode; } else { //左孩子先入栈，保证右孩子先被访问。 if (curNode.left != null) { index++; p[index] = curNode.left; } if (curNode.right != null) { index++; p[index] = curNode.right; } } } } //递归的方式中序打印二叉查找树，最后输出的顺序必然是递增的。 static void printInOrder(Node node) { if (node == null) { return; } printInOrder(node.left); System.out.println(node.value); printInOrder(node.right); } public static void main(String[] args) { int p[] = { 3,5,6,1,2,4}; Tree tree = createBinTree(p, p.length); System.out.println("- 先序遍历 - "); printPreOrder(tree); System.out.println("- 中序遍历 - "); printInOrder(tree); System.out.println("- 后序遍历 - "); printPostOrder(tree); }}复制代码 运行结果
- 先序遍历 - 312546- 中序遍历 - 123456- 后序遍历 - 645213复制代码