面試算法代碼知識梳理系列
面試算法知識梳理(1) - 排序算法
面試算法知識梳理(2) - 字符串算法第一部分
面試算法知識梳理(3) - 字符串算法第二部分
面試算法知識梳理(4) - 數(shù)組第一部分
面試算法知識梳理(5) - 數(shù)組第二部分
面試算法知識梳理(6) - 數(shù)組第三部分
面試算法知識梳理(7) - 數(shù)組第四部分
面試算法知識梳理(8) - 二分查找算法及其變型
面試算法知識梳理(9) - 鏈表算法第一部分
面試算法知識梳理(10) - 二叉查找樹
面試算法知識梳理(11) - 二叉樹算法第一部分
面試算法知識梳理(12) - 二叉樹算法第二部分
面試算法知識梳理(13) - 二叉樹算法第三部分
一缩焦、概述
二叉查找樹 又稱為 二叉搜索樹驼修，它是一棵空樹，或者是具有下列性質(zhì)的 二叉樹
- 若左子樹不空背稼，則左子樹上所有結(jié)點的值均小于或等于它的結(jié)點
- 若右子樹不空兼砖，則右子樹上所有結(jié)點的值均大于或等于它的根結(jié)點的值
- 左测蘑、右子樹也分別為二叉查找樹
下面我們就來一起梳理一下和二叉查找樹相關(guān)的知識點：
- 建立二叉查找樹
- 刪除二叉查找樹中指定元素
- 非遞歸遍歷二叉查找樹（先序遍歷、中序遍歷制肮、后序遍歷）
二冒窍、代碼實現(xiàn)
2.1 建立二叉查找樹
二叉查找樹的表示
二叉查找樹可以用Tree來表示，它包含一個root變量豺鼻，用于存放這棵樹的根結(jié)點综液，size表示樹中元素的個數(shù)，每個結(jié)點Node包含以下的變量：
-
parent：指向其父結(jié)點 -
left儒飒、right：分別指向它的左孩子和右孩子 -
value：該結(jié)點存儲的值
代碼實現(xiàn)
下面我們輸入一個數(shù)組p谬莹，通過它建立一個二叉查找樹，并通過 遞歸中序遍歷 的方式打印出樹中的元素，按照二叉查找樹的定義附帽，最后輸出的結(jié)果必然是遞增排序的埠戳。
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;
//待插入結(jié)點的父結(jié)點，如果遍歷完為空蕉扮，說明此時是一個空樹整胃。
Node pNode = null;
//新的結(jié)點。
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<len; i++) {
int value = p[i];
insertNode(tree, value);
}
return tree;
}
//遞歸的方式中序打印二叉查找樹喳钟，最后輸出的順序必然是遞增的爪模。
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[] = {4,5,6,1,2,3};
Tree tree = createBinTree(p, p.length);
printInOrder(tree.root);
}
}
運行結(jié)果
>> 1
>> 2
>> 3
>> 4
>> 5
>> 6
2.2 刪除二叉查找樹中指定元素
在二叉查找樹中刪除某個元素，其核心思想就是 找到待刪除結(jié)點的父結(jié)點荚藻，并將該父結(jié)點的left或right指向 待刪除結(jié)點的孩子結(jié)點
- 如果待刪除結(jié)點只有一個孩子結(jié)點，那么用 該孩子結(jié)點替換待刪除結(jié)點 即可洁段。
- 如果待刪除結(jié)點有兩個孩子結(jié)點应狱，那么就需要進行如下幾步操作：
- 第一步：找到 待刪除結(jié)點的右子樹的最小結(jié)點 作為替換結(jié)點，如果該結(jié)點不是右子樹的根節(jié)點祠丝，那么還需要 先用最小結(jié)點的右結(jié)點來替換最小結(jié)點
- 第二步：用第一步找到的結(jié)點替換待刪除結(jié)點
- 第三步：將待刪除結(jié)點的左子樹的根節(jié)點嫁接到替換結(jié)點 上疾呻。
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;
//待插入結(jié)點的父結(jié)點，如果遍歷完為空写半，說明此時是一個空樹岸蜗。
Node pNode = null;
//新的結(jié)點。
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<len; i++) {
int value = p[i];
insertNode(tree, value);
}
return tree;
}
static Node searchNode(Tree tree, int value) {
if (tree == null) {
return null;
}
Node find = null;
Node node = tree.root;
while (node != null) {
if (node.value > 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);
}
}
運行結(jié)果
>> 1
>> 2
>> 4
>> 5
>> 6
2.3 非遞歸遍歷方式
解決思路
對于二叉樹的遞歸遍歷，相信大家已經(jīng)很熟悉了悔捶，這里演示的是如何通過“椓蹇叮”來實現(xiàn)二叉樹的非遞歸遍歷：
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;
//待插入結(jié)點的父結(jié)點，如果遍歷完為空蜕该，說明此時是一個空樹犁柜。
Node pNode = null;
//新的結(jié)點。
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<len; i++) {
int value = p[i];
insertNode(tree, value);
}
return tree;
}
//先序遍歷堂淡。
static void printPreOrder(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;
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];
//如果沒有孩子結(jié)點绢淀。
boolean hasNoChild = (curNode.left == null && curNode.right == null);
//如果它的左孩子或者右孩子已經(jīng)被訪問過萤悴。
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);
}
}
運行結(jié)果
- 先序遍歷 -
3
1
2
5
4
6
- 中序遍歷 -
1
2
3
4
5
6
- 后序遍歷 -
6
4
5
2
1
3
更多文章，歡迎訪問我的 Android 知識梳理系列：
- Android 知識梳理目錄：http://www.reibang.com/p/fd82d18994ce
- Android 面試文檔分享：http://www.reibang.com/p/8456fe6b27c4
