現(xiàn)在很多公司在招聘開發(fā)崗位的時(shí)候，都會(huì)事先在招聘信息中注明面試者應(yīng)當(dāng)具備的知識(shí)技能，而且在面試的過(guò)程中，有部分對(duì)于技能掌握程度有嚴(yán)格要求的公司還會(huì)要求面試者手寫代碼，這個(gè)環(huán)節(jié)很考驗(yàn)面試者的基礎(chǔ)功底和實(shí)力！
這不，前些天一個(gè)朋友去阿里面試的時(shí)候，在二面過(guò)程中就被要求使用Java實(shí)現(xiàn)二叉樹，王二Dog由于沒有準(zhǔn)備這方面的知識(shí)，沒有答上來(lái)，然后就讓回家等通知了。
所以有利用給王二Dog講解二叉樹的機(jī)會(huì)，我整體梳理了下二叉樹常見的面試點(diǎn)，發(fā)出來(lái)供大家一起交流學(xué)習(xí)。希望對(duì)你的面試有所幫助。
二叉樹是遞歸數(shù)據(jù)結(jié)構(gòu)，其中每個(gè)節(jié)點(diǎn)最多可以有2個(gè)子節(jié)點(diǎn)。
常見類型的二叉樹是二叉搜索樹，其中每個(gè)節(jié)點(diǎn)的值大于或等于左子節(jié)點(diǎn)值，并且小于或等于右子節(jié)點(diǎn)中的節(jié)點(diǎn)值。
這是這種二叉樹的直觀表示：
對(duì)于實(shí)現(xiàn)，我們將使用 Node 類來(lái)存儲(chǔ) int 值并保存對(duì)每個(gè)子節(jié)點(diǎn)的引用：
重慶分公司
重慶分公司
class Node {
int value;//本節(jié)點(diǎn)的值
Node left;//左邊的子節(jié)點(diǎn)
Node right;//右邊的子節(jié)點(diǎn)
Node(int value) {
this. value = value;
right = null;
left = null;
}
}然后，讓我們添加樹的根節(jié)點(diǎn)，通常稱為 根：
public class BinaryTree {
Node root;
// ...}現(xiàn)在，讓我們看看可以在二叉樹上執(zhí)行的最常見操作有哪些？
我們要介紹的第一個(gè)操作是插入新節(jié)點(diǎn)。
首先，我們必須找到我們想要添加新節(jié)點(diǎn)的位置，以便對(duì)樹進(jìn)行排序。我們將從根節(jié)點(diǎn)開始遵循這些規(guī)則：
首先，我們將創(chuàng)建一個(gè)遞歸方法來(lái)進(jìn)行插入：
private Node addRecursive(Node current, int value) {
if (current == null) {
return new Node(value);
}
if (value < current.value) {
current.left = addRecursive(current.left, value);
} else if (value > current.value) {
current.right = addRecursive(current.right, value);
} else {
// value already exists
return current;
}
return current;
}接下來(lái)，我們將創(chuàng)建一個(gè)遞歸方法來(lái)創(chuàng)建根節(jié)點(diǎn)：
public void add(int value) {
root = addRecursive(root, value);
}現(xiàn)在讓我們看看如何使用此方法從我們的示例中創(chuàng)建樹：
private BinaryTree createBinaryTree() {
BinaryTree bt = new BinaryTree();
bt.add(6);
bt.add(4);
bt.add(8);
bt.add(3);
bt.add(5);
bt.add(7);
bt.add(9);
return bt;
}現(xiàn)在讓我們添加一個(gè)方法來(lái)檢查樹是否包含特定值。
和以前一樣，我們首先創(chuàng)建一個(gè)遍歷樹的遞歸方法：
private boolean containsNodeRecursive(Node current, int value) {
if (current == null) {
return false;
}
if (value == current.value) {
return true;
}
return value < current.value
? containsNodeRecursive(current.left, value)
: containsNodeRecursive(current.right, value);
}在這里，我們通過(guò)將其與當(dāng)前節(jié)點(diǎn)中的值進(jìn)行比較來(lái)搜索該值，然后根據(jù)該值繼續(xù)在左或右子節(jié)點(diǎn)中繼續(xù)查找。
接下來(lái)，我們讓創(chuàng)建一個(gè)公共方法來(lái)查找：
public boolean containsNode(int value) {
return containsNodeRecursive(root, value);
}現(xiàn)在，讓我們創(chuàng)建一個(gè)簡(jiǎn)單的測(cè)試來(lái)驗(yàn)證樹真的包含插入的元素：
@Test
public void givenABinaryTree_WhenAddingElements_ThenTreeContainsThoseElements() {
BinaryTree bt = createBinaryTree();
assertTrue(bt.containsNode(6));
assertTrue(bt.containsNode(4));
assertFalse(bt.containsNode(1));
}另一種常見操作是從樹中刪除節(jié)點(diǎn)。
首先，我們必須以與之前類似的方式找到要?jiǎng)h除的節(jié)點(diǎn)：
private Node deleteRecursive(Node current, int value) {
if (current == null) {
return null;
}
if (value == current.value) {
// Node to delete found
// ... code to delete the node will go here
}
if (value < current.value) {
current.left = deleteRecursive(current.left, value);
return current;
}
current.right = deleteRecursive(current.right, value);
return current;
}一旦我們找到要?jiǎng)h除的節(jié)點(diǎn)，就有3種主要的不同情況：
讓我們看看當(dāng)節(jié)點(diǎn)是葉節(jié)點(diǎn)時(shí)我們?nèi)绾螌?shí)現(xiàn)第一種情況：
if (current.left == null && current.right == null) {
return null;
}現(xiàn)在讓我們繼續(xù)討論節(jié)點(diǎn)有一個(gè)子節(jié)點(diǎn)的情況：
if (current.right == null) {
return current.left;
}
if (current.left == null) {
return current.right;
}在這里，我們返回 非null 子節(jié)點(diǎn)，以便將其分配給父節(jié)點(diǎn)。
最后，我們必須處理節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)的情況。
首先，我們需要找到將替換已刪除節(jié)點(diǎn)的節(jié)點(diǎn)。我們將使用節(jié)點(diǎn)的最小節(jié)點(diǎn)刪除右側(cè)子樹：
private int findSmallestValue(Node root) {
return root.left == null ? root.value : findSmallestValue(root.left);
}然后，我們將最小值分配給要?jiǎng)h除的節(jié)點(diǎn)，之后，我們將從右側(cè)子樹中刪除它：
int smallestValue = findSmallestValue(current.right);
current.value = smallestValue;
current.right = deleteRecursive(current.right, smallestValue);
return current;最后，我們讓創(chuàng)建刪除的公共方法：
public void delete(int value) {
root = deleteRecursive(root, value);
}現(xiàn)在，讓我們檢查刪除是否按預(yù)期工作：
@Test
public void givenABinaryTree () {
BinaryTree bt = createBinaryTree();
assertTrue(bt.containsNode(9));
bt.delete(9);
assertFalse(bt.containsNode(9));
}在此，我們將看到遍歷樹的不同方式，詳細(xì)介紹深度優(yōu)先和廣度優(yōu)先搜索。
我們將使用之前使用的相同樹，并且我們將顯示每個(gè)案例的遍歷順序。
深度優(yōu)先搜索是一種在每個(gè)子節(jié)點(diǎn)探索下一個(gè)兄弟之前盡可能深入的遍歷。
有幾種方法可以執(zhí)行深度優(yōu)先搜索：in-order, pre-order 和 post-order。
in-order：首先訪問(wèn)左子樹，然后訪問(wèn)根節(jié)點(diǎn)，最后訪問(wèn)右子樹：
public void traverseInOrder(Node node) {
if (node != null) {
traverseInOrder(node.left);
System.out.print(" " + node.value);
traverseInOrder(node.right);
}
}如果我們調(diào)用此方法，控制臺(tái)輸出：
3 4 5 6 7 8 9pre-order：首先訪問(wèn)根節(jié)點(diǎn)，然后是左子樹，最后是右子樹：
public void traversePreOrder(Node node) {
if (node != null) {
System.out.print(" " + node.value);
traversePreOrder(node.left);
traversePreOrder(node.right);
}
}如果我們調(diào)用此方法，控制臺(tái)輸出：
6 4 3 5 8 7 9post-order：訪問(wèn)左子樹，右子樹，最后訪問(wèn)根節(jié)點(diǎn)：
public void traversePostOrder(Node node) {
if (node != null) {
traversePostOrder(node.left);
traversePostOrder(node.right);
System.out.print(" " + node.value);
}
}如果我們調(diào)用此方法，控制臺(tái)輸出：
3 5 4 7 9 8 6這是另一種常見的遍歷類型，它在展示進(jìn)入下一級(jí)別之前訪問(wèn)級(jí)別的所有節(jié)點(diǎn)。
這種遍歷也稱為按級(jí)別順序，并從根開始，從左到右訪問(wèn)樹的所有級(jí)別。
對(duì)于實(shí)現(xiàn)，將我們使用 隊(duì)列 按順序保存每個(gè)級(jí)別的節(jié)點(diǎn)。我們將從列表中提取每個(gè)節(jié)點(diǎn)，打印其值，然后將其子節(jié)點(diǎn)添加到隊(duì)列中：
public void traverseLevelOrder() {
if (root == null) {
return;
}
Queue nodes = new LinkedList<>();
nodes.add(root);
while (!nodes.isEmpty()) {
Node node = nodes.remove();
System.out.print(" " + node.value);
if (node.left != null) {
nodes.add(node.left);
}
if (node.right!= null) {
nodes.add(node.right);
}
}
} 在這種情況下，節(jié)點(diǎn)的順序?qū)⑹牵?/p>
6 4 8 3 5 7 9在本文中，我們已經(jīng)了解了如何在Java中實(shí)現(xiàn)已排序的二叉樹及其最常見的操作。你是否從中有所收獲呢？哪怕你能收獲一點(diǎn)點(diǎn)心得，我在此也欣慰了！
“不積跬步，無(wú)以至千里”，希望未來(lái)的你能成為：有夢(mèng)為馬 隨處可棲！加油，少年！
另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。
