二叉排序樹開端：
先來看一張二叉排序樹的圖：
它或者是一顆空樹，或者是一顆具有如下性質(zhì)的樹：
1）若左子樹不為空，那么左子樹上面的所有節(jié)點(diǎn)的關(guān)鍵字值都比根節(jié)點(diǎn)的關(guān)鍵字值小
2）若右子樹不為空，那么右子樹上面的所有節(jié)點(diǎn)的關(guān)鍵字值都比根節(jié)點(diǎn)的關(guān)鍵字值大
3）左右子樹都為二叉樹
4）沒有重復(fù)值（這一點(diǎn)在實(shí)際中可以忽略）
下面咱們手動(dòng)來根據(jù)上面的規(guī)則來畫一張二叉排序樹，先來對(duì)這個(gè)樹的規(guī)則了解清楚，比如數(shù)列“5、2、7、3、4、1、6”，下面來讓它生成一個(gè)二叉排序樹：
先拿5作為根結(jié)點(diǎn)：
然后再拿2，由于它比5要小，所以放在5的左邊：
再拿7,由于它比5要大，則放在它的右邊：
接著再拿3，先跟5比，比它小則往它的左邊找，此時(shí)則跟2進(jìn)行對(duì)比，由于它比2要大，則放在2的右邊，如下：
再拿4，它比5小則往左找，到了2，則于它比2要大則繼續(xù)往它的右邊找，則到了3，由于它比3也要大，則將其放到3的右邊，如下：
接著再拿1，比5比2都要小，則放在2的左邊，如下：
最后6，由于它比5大，則往右找，由于它比7要小，則放到7的左邊，最終整個(gè)二叉排序樹就出來了：
好，如果對(duì)上面的樹進(jìn)行一下中序遍歷（左中右）的話，其結(jié)果會(huì)讓你吃驚：1、2、3、4、5、6、7，居然取出來的結(jié)果就變成有序的了。。
接下來咱們則用代碼來生成上面的這棵樹，我們之前在定義數(shù)的結(jié)構(gòu)時(shí)也就是一個(gè)數(shù)據(jù)域，一個(gè)左結(jié)點(diǎn)，一個(gè)右結(jié)點(diǎn)，回憶一下：
但是！！此時(shí)需要增加一個(gè)信息了，也就它的父結(jié)點(diǎn)，為啥？這為之后的刪除節(jié)點(diǎn)做準(zhǔn)備，這里可以簡(jiǎn)單試想一下，假如我們要?jiǎng)h除排序二叉樹中的這樣一個(gè)節(jié)點(diǎn)：
如果要?jiǎng)h除的節(jié)點(diǎn)木有父節(jié)點(diǎn)的信息，請(qǐng)問下面的節(jié)點(diǎn)如何鏈接上它的父節(jié)點(diǎn)？所以咱們來定義一下：
主要操作：
添加節(jié)點(diǎn)：
首先定義一個(gè)添加方法：
那接下添加肯定有比較大小的過程，首先如果沒有根結(jié)點(diǎn)，則直接將要添加的數(shù)據(jù)作為根節(jié)點(diǎn)既可，如下：
接下來則是需要進(jìn)行數(shù)據(jù)大小比較的，如果該數(shù)比節(jié)點(diǎn)小則往左找，比它大則往右找，代碼如下：
當(dāng)跳出循環(huán)則代表是已經(jīng)找到待插入元素所存放的位置了，接下來則需要根據(jù)這個(gè)數(shù)據(jù)生成一個(gè)新節(jié)點(diǎn)將其插入到樹當(dāng)中，如下：
遍歷：
咱們直接用中序遍歷既可，遍歷出來就是一個(gè)有序數(shù)列：
好，接下來咱們來驗(yàn)證一下程序是否寫得有問題：
那如果有重復(fù)值呢？試一下：
以上就構(gòu)建了一個(gè)去重復(fù)值的排序二叉樹。
查詢節(jié)點(diǎn)：
查詢就比較簡(jiǎn)單了，待查找的數(shù)比當(dāng)前結(jié)點(diǎn)要小則往左找，則它大則往右找，如下：
下面來調(diào)用一下：
嗯~~確實(shí)是木問題，接下來咱們來找一個(gè)找不到的值：
刪除節(jié)點(diǎn)：
接下來最最復(fù)雜的操作來了，刪除節(jié)點(diǎn)。。為啥難呢？下面寫著就知道了，總之它有四種情況，下面一個(gè)個(gè)情況來逐步處理：
①、要?jiǎng)h除的節(jié)點(diǎn)是葉子節(jié)點(diǎn)：比如：
這種情況處理比較簡(jiǎn)單，只要讓父結(jié)點(diǎn)的子結(jié)點(diǎn)為null既可，如下：
先把整個(gè)框架條件定好，接下來先處理第一種情況，先來處理一下特殊情況：如果整棵樹就只有一個(gè)結(jié)點(diǎn)：
其也滿足葉子結(jié)點(diǎn)的條件，所以可以這樣處理：
然后再來處理正常葉子的情況：
②、要?jiǎng)h除的結(jié)點(diǎn)它只有左孩子，比如：
也就是再來處理這個(gè)條件分支：
其思路就是需要將要?jiǎng)h除結(jié)點(diǎn)的左孩子往上頂替回來，也就是說：
所以看一下具體實(shí)現(xiàn)，所先判斷是否刪的是根結(jié)點(diǎn)：
接下來else的條件則是說明要?jiǎng)h除的結(jié)點(diǎn)不是根結(jié)點(diǎn)了，但是此時(shí)還存在兩種情況，一種是在父節(jié)點(diǎn)左邊，另一種是在父節(jié)點(diǎn)右邊，如下：
所以代碼條件框架如下：
處理也比較簡(jiǎn)單，直接將要?jiǎng)h除結(jié)點(diǎn)的左孩子接到父節(jié)點(diǎn)上既可，如下：
③、要?jiǎng)h除的結(jié)點(diǎn)只有右孩子，跟情況2類似。所以直接依葫蘆畫瓢既可，只是將左孩子統(tǒng)一換成右孩子既可，如下：
/**
* 刪除節(jié)點(diǎn)
*/
public void deleteNode(TreeNode node) {
if (node == null) {
throw new NoSuchElementException();
} else {
//先得到父親，方便后面的操作
TreeNode parent = node.parent;
if (node.left == null && node.right == null) {
//1、node是個(gè)葉子
if (parent == null)//如果要?jiǎng)h除的結(jié)點(diǎn)就是整棵樹的唯一結(jié)點(diǎn)，則將root置為Null，因?yàn)閯h掉之后就空樹了嘛
root = null;
else if (parent.right == node) {
parent.right = null;//直接將右結(jié)點(diǎn)置為null
} else if (parent.left == node) {
parent.left = null;//直接將左結(jié)點(diǎn)置為null
}
node.parent = null;
} else if (node.left != null && node.right == null) {
//2、只有左孩子
if (parent == null) {
//說明刪除的結(jié)點(diǎn)是根結(jié)點(diǎn)，直接將子結(jié)點(diǎn)接上來
node.parent = null;
node.left.parent = null;//將它的左孩子作為根結(jié)點(diǎn)
root = node.left;//重新更新根結(jié)點(diǎn)
} else {
if (parent.left == node) {
//要?jiǎng)h除的節(jié)點(diǎn)是在父親的左邊
parent.left = node.left;
} else if (parent.right == node) {
//要?jiǎng)h除的節(jié)點(diǎn)是在父親的右邊
parent.right = node.left;
}
node.parent = null;
}
} else if (node.left == null && node.right != null) {
//3、只有右孩子
if (parent == null) {
//說明刪除的結(jié)點(diǎn)是根結(jié)點(diǎn)，直接將子結(jié)點(diǎn)接上來
node.parent = null;
node.right.parent = null;//將它的左孩子作為根結(jié)點(diǎn)
root = node.right;//重新更新根結(jié)點(diǎn)
} else {
if (parent.left == node) {
//要?jiǎng)h除的節(jié)點(diǎn)是在父親的左邊
parent.left = node.right;
} else if (parent.right == node) {
//要?jiǎng)h除的節(jié)點(diǎn)是在父親的右邊
parent.right = node.right;
}
node.parent = null;
}
} else if (node.left != null && node.right != null) {
//4、有左右孩子
//TODO
}
}
}
[](file:///Applications/%E5%8D%B0%E8%B1%A1%E7%AC%94%E8%AE%B0.app/Contents/Resources/common-editor-mac/mac.html# "復(fù)制代碼")
其實(shí)代碼此時(shí)已經(jīng)有bug了，修改如下：
[](file:///Applications/%E5%8D%B0%E8%B1%A1%E7%AC%94%E8%AE%B0.app/Contents/Resources/common-editor-mac/mac.html# "復(fù)制代碼")
/**
* 刪除節(jié)點(diǎn)
*/
public void deleteNode(TreeNode node) {
if (node == null) {
throw new NoSuchElementException();
} else {
//先得到父親，方便后面的操作
TreeNode parent = node.parent;
if (node.left == null && node.right == null) {
//1、node是個(gè)葉子
if (parent == null)//如果要?jiǎng)h除的結(jié)點(diǎn)就是整棵樹的唯一結(jié)點(diǎn)，則將root置為Null，因?yàn)閯h掉之后就空樹了嘛
root = null;
else if (parent.right == node) {
parent.right = null;//直接將右結(jié)點(diǎn)置為null
} else if (parent.left == node) {
parent.left = null;//直接將左結(jié)點(diǎn)置為null
}
node.parent = null;
} else if (node.left != null && node.right == null) {
//2、只有左孩子
if (parent == null) {
//說明刪除的結(jié)點(diǎn)是根結(jié)點(diǎn)，直接將子結(jié)點(diǎn)接上來
node.parent = null;
node.left.parent = null;//將它的左孩子作為根結(jié)點(diǎn)
root = node.left;//重新更新根結(jié)點(diǎn)
} else {
if (parent.left == node) {
//要?jiǎng)h除的節(jié)點(diǎn)是在父親的左邊
node.left.parent = parent;
parent.left = node.left;
} else if (parent.right == node) {
//要?jiǎng)h除的節(jié)點(diǎn)是在父親的右邊
node.left.parent = parent;
parent.right = node.left;
}
node.parent = null;
}
} else if (node.left == null && node.right != null) {
//3、只有右孩子
if (parent == null) {
//說明刪除的結(jié)點(diǎn)是根結(jié)點(diǎn)，直接將子結(jié)點(diǎn)接上來
node.parent = null;
node.right.parent = null;//將它的左孩子作為根結(jié)點(diǎn)
root = node.right;//重新更新根結(jié)點(diǎn)
} else {
if (parent.left == node) {
//要?jiǎng)h除的節(jié)點(diǎn)是在父親的左邊
node.right.parent = parent;
parent.left = node.right;
} else if (parent.right == node) {
//要?jiǎng)h除的節(jié)點(diǎn)是在父親的右邊
node.right.parent = parent;
parent.right = node.right;
}
node.parent = null;
}
} else if (node.left != null && node.right != null) {
//4、有左右孩子
//TODO
}
}
}
④、要?jiǎng)h除的結(jié)點(diǎn)既有左孩子，又有右孩子。比如：
也就是對(duì)應(yīng)這個(gè)條件的代碼：
此時(shí)最復(fù)雜的操作來了，下面得留個(gè)心，很容易寫錯(cuò)的，因?yàn)樯婕暗降那闆r也挺多的，下面一個(gè)個(gè)情況進(jìn)行分析然后進(jìn)行一一處理：
情況一：
那此時(shí)刪掉之后，得由7往上補(bǔ)，因?yàn)槎剂擞医Y(jié)點(diǎn)，都比左邊的數(shù)要大，所以最終形態(tài)會(huì)是：
那下面用代碼來處理這種情況：
這里還有一種情況如下：
也就是要?jiǎng)h除的節(jié)點(diǎn)不是根節(jié)點(diǎn)，那此時(shí)則直接將7往上替換既可，如下：
所以這塊邏輯的代碼比較簡(jiǎn)單：
類似的，還有可能在根結(jié)點(diǎn)左邊，如下：
像這種處理也是類似，直接將7頂替上來既可：
所以相似的處理代碼：
情況二：
此時(shí)就要注意啦，就不能直接將7給被上去了啦，為啥，假如把7替上去，就不符合排序二叉樹了？所以應(yīng)該是遍歷它的左孩子將其最小的4頂上去，如下：
所以下面來實(shí)現(xiàn)一下，先來封裝一下找節(jié)點(diǎn)最小值的方法：
此時(shí)也就是找到了這個(gè)結(jié)點(diǎn)了：
接下來則需要將這個(gè)4放到5的位置，如何做呢？先這樣做：
所以先處理這種情況，得一個(gè)個(gè)來，不然很容易繞暈的，而且必須要畫圖，具體代碼如下：
此時(shí)的形態(tài)就變?yōu)椋?/p>
好，接下來需要對(duì)最小節(jié)點(diǎn)做引用處理，因?yàn)橛锌赡茉谒旅孢€有樹，比如：
此時(shí)則需要將4這棵最小的值的右子樹得先處理好了，才能將4作為根節(jié)點(diǎn)，所以代碼處理如下：
所以此時(shí)的形態(tài)就變?yōu)椋?/p>
注意需要將4的父結(jié)點(diǎn)的引用給去掉，以便將4頂上去，所以修改一下代碼：
好，接下來再處理第三步，則應(yīng)該是將7作為4的右子樹，形態(tài)就會(huì)變?yōu)椋?/p>
所以這一步的代碼為：
同樣的它也有一種特殊情況，比如要?jiǎng)h的這個(gè)節(jié)點(diǎn)不是根結(jié)點(diǎn)，如下：
此時(shí)直接將4接到根結(jié)點(diǎn)既可，如下：
所以代碼如下：
此時(shí)處理的是根結(jié)點(diǎn)的情況，也就是形態(tài)會(huì)成了這樣了：
接下來再來處理有父節(jié)點(diǎn)的：
有父節(jié)點(diǎn)的就有兩種情況，一個(gè)是被刪除的子節(jié)點(diǎn)位于父節(jié)點(diǎn)左邊，一個(gè)是位于父節(jié)點(diǎn)右邊，下面以位于父節(jié)點(diǎn)右邊為例來看一下目前的形態(tài)：
于是乎，整個(gè)刪除節(jié)點(diǎn)的代碼如下：
/**
* 刪除節(jié)點(diǎn)
*/
public void deleteNode(TreeNode node) {
if (node == null) {
throw new NoSuchElementException();
} else {
//先得到父親，方便后面的操作
TreeNode parent = node.parent;
if (node.left == null && node.right == null) {
//1、node是個(gè)葉子
if (parent == null)//如果要?jiǎng)h除的結(jié)點(diǎn)就是整棵樹的唯一結(jié)點(diǎn)，則將root置為Null，因?yàn)閯h掉之后就空樹了嘛
root = null;
else if (parent.right == node) {
parent.right = null;//直接將右結(jié)點(diǎn)置為null
} else if (parent.left == node) {
parent.left = null;//直接將左結(jié)點(diǎn)置為null
}
node.parent = null;
} else if (node.left != null && node.right == null) {
//2、只有左孩子
if (parent == null) {
//說明刪除的結(jié)點(diǎn)是根結(jié)點(diǎn)，直接將子結(jié)點(diǎn)接上來
node.parent = null;
node.left.parent = null;//將它的左孩子作為根結(jié)點(diǎn)
root = node.left;//重新更新根結(jié)點(diǎn)
} else {
if (parent.left == node) {
//要?jiǎng)h除的節(jié)點(diǎn)是在父親的左邊
node.left.parent = parent;
parent.left = node.left;
} else if (parent.right == node) {
//要?jiǎng)h除的節(jié)點(diǎn)是在父親的右邊
node.left.parent = parent;
parent.right = node.left;
}
node.parent = null;
}
} else if (node.left == null && node.right != null) {
//3、只有右孩子
if (parent == null) {
//說明刪除的結(jié)點(diǎn)是根結(jié)點(diǎn)，直接將子結(jié)點(diǎn)接上來
node.parent = null;
node.right.parent = null;//將它的左孩子作為根結(jié)點(diǎn)
root = node.right;//重新更新根結(jié)點(diǎn)
} else {
if (parent.left == node) {
//要?jiǎng)h除的節(jié)點(diǎn)是在父親的左邊
node.right.parent = parent;
parent.left = node.right;
} else if (parent.right == node) {
//要?jiǎng)h除的節(jié)點(diǎn)是在父親的右邊
node.right.parent = parent;
parent.right = node.right;
}
node.parent = null;
}
} else if (node.left != null && node.right != null) {
//4、有左右孩子
if (node.right.left == null) {
//如果被刪除的右子樹的左子樹為空，則直接補(bǔ)上右子樹
node.right.left = node.left;
if (parent == null) {
//如果要?jiǎng)h的根結(jié)點(diǎn)
root = node.right;
} else {
//如果不是根結(jié)點(diǎn)
if (parent.right == node) {
parent.right = node.right;
} else {
parent.left = node.right;
}
}
node.left = null;
node.right = null;
node.parent = null;
} else {
//需要補(bǔ)上右子樹的左子樹上最小的一位
TreeNode treeNode = getMinLeftTreeNode(node.right);
treeNode.left = node.left;
//將最小左子樹結(jié)點(diǎn)的右子樹全部接上來
TreeNode leftNodeParent = treeNode.parent;
leftNodeParent.left = treeNode.right;
treeNode.right.parent = leftNodeParent;
treeNode.parent = null;
//將最小左子樹結(jié)點(diǎn)頂?shù)礁恢?
treeNode.right = node.right;
//處理根情況
if (parent == null) {
//要?jiǎng)h除的節(jié)點(diǎn)既為根節(jié)點(diǎn)
node.left = null;
node.right = null;
root = leftNodeParent;
} else {
//要?jiǎng)h除的節(jié)點(diǎn)不是根節(jié)點(diǎn)
if (parent.left == node) {
//左節(jié)點(diǎn)
parent.left = treeNode;
} else {
//右節(jié)點(diǎn)
parent.right = treeNode;
}
treeNode.parent = parent;
node.left = null;
node.right = null;
node.parent = null;
}
}
}
}
}
真的是。。暈菜了~~太TM復(fù)雜了，下面先來論證一下是否寫得靠譜：
真是實(shí)力打臉，得找bug了。。
再運(yùn)行：
嗯，對(duì)了，再來測(cè)：
繼續(xù)找bug：
下面看一下為啥輸出不對(duì)了，調(diào)一下：
另外，在刪2時(shí)，發(fā)現(xiàn)它的parent還是5，不太對(duì)，所以得繼續(xù)找原因，發(fā)現(xiàn)是這塊的問題：
再運(yùn)行：
正確了，可見這塊刪除只要有一個(gè)關(guān)系沒處理好其結(jié)果就會(huì)有問題，面試要誰(shuí)問到手寫它，我覺得沒個(gè)幾個(gè)小時(shí)肯定是很難寫得非常正確的，好下面繼續(xù)再測(cè)試：
看一下結(jié)果：
哇塞，真不容易~~完美！！最后代碼定格在：
package com.datastruct.test.tree;
import java.util.NoSuchElementException;
public class SearchBinaryTree {
//根節(jié)點(diǎn)
TreeNode root;
public TreeNode put(int data) {
if (root == null) {//如果沒有根節(jié)點(diǎn)，則直接將其作為根節(jié)點(diǎn)
TreeNode node = new TreeNode(data);
root = node;
return root;
}
TreeNode parent = null;
TreeNode node = root;
while (node != null) {
parent = node;//再往下移之前需要記錄一下父元素，以便在找到要插入的位置時(shí)將其進(jìn)行連接上
if (data < node.data) {
//則往左找
node = node.left;
} else if (data > node.data) {
//則往右找
node = node.right;
} else {
//如果已經(jīng)有相同的重復(fù)節(jié)點(diǎn)了，則直接返回，因?yàn)槎媾判驑涫遣辉试S重復(fù)的
return node;
}
}
//生成一個(gè)新節(jié)點(diǎn)將其插入
TreeNode newNode = new TreeNode(data);
if (data < parent.data) {
parent.left = newNode;
} else {
parent.right = newNode;
}
newNode.parent = parent;
return newNode;
}
/**
* 中序遍歷
*/
public void midOrderTraverse(TreeNode root) {
if (root == null)
return;
midOrderTraverse(root.left);
System.out.print(root.data + " ");
midOrderTraverse(root.right);
}
/**
* 查找接點(diǎn)
*/
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.left;
} else if (data > node.data) {
//則往右找
node = node.right;
}
}
return null;
}
/**
* 刪除節(jié)點(diǎn)
*/
public void deleteNode(TreeNode node) {
if (node == null) {
throw new NoSuchElementException();
} else {
//先得到父親，方便后面的操作
TreeNode parent = node.parent;
if (node.left == null && node.right == null) {
//1、node是個(gè)葉子
if (parent == null)//如果要?jiǎng)h除的結(jié)點(diǎn)就是整棵樹的唯一結(jié)點(diǎn)，則將root置為Null，因?yàn)閯h掉之后就空樹了嘛
root = null;
else if (parent.right == node) {
parent.right = null;//直接將右結(jié)點(diǎn)置為null
} else if (parent.left == node) {
parent.left = null;//直接將左結(jié)點(diǎn)置為null
}
node.parent = null;
} else if (node.left != null && node.right == null) {
//2、只有左孩子
if (parent == null) {
//說明刪除的結(jié)點(diǎn)是根結(jié)點(diǎn)，直接將子結(jié)點(diǎn)接上來
node.parent = null;
node.left.parent = null;//將它的左孩子作為根結(jié)點(diǎn)
root = node.left;//重新更新根結(jié)點(diǎn)
} else {
if (parent.left == node) {
//要?jiǎng)h除的節(jié)點(diǎn)是在父親的左邊
node.left.parent = parent;
parent.left = node.left;
} else if (parent.right == node) {
//要?jiǎng)h除的節(jié)點(diǎn)是在父親的右邊
node.left.parent = parent;
parent.right = node.left;
}
node.parent = null;
}
} else if (node.left == null && node.right != null) {
//3、只有右孩子
if (parent == null) {
//說明刪除的結(jié)點(diǎn)是根結(jié)點(diǎn)，直接將子結(jié)點(diǎn)接上來
node.parent = null;
node.right.parent = null;//將它的左孩子作為根結(jié)點(diǎn)
root = node.right;//重新更新根結(jié)點(diǎn)
} else {
if (parent.left == node) {
//要?jiǎng)h除的節(jié)點(diǎn)是在父親的左邊
node.right.parent = parent;
parent.left = node.right;
} else if (parent.right == node) {
//要?jiǎng)h除的節(jié)點(diǎn)是在父親的右邊
node.right.parent = parent;
parent.right = node.right;
}
node.parent = null;
}
} else if (node.left != null && node.right != null) {
//4、有左右孩子
if (node.right.left == null) {
//如果被刪除的右子樹的左子樹為空，則直接補(bǔ)上右子樹
node.right.left = node.left;
if (parent == null) {
//如果要?jiǎng)h的根結(jié)點(diǎn)
node.right.parent = null;
node.right.left.parent = node.right;
root = node.right;
} else {
//如果不是根結(jié)點(diǎn)
if (parent.right == node) {
parent.right = node.right;
} else {
parent.left = node.right;
}
node.right.parent = parent;
node.left.parent = node.right;
}
node.left = null;
node.right = null;
node.parent = null;
} else {
//需要補(bǔ)上右子樹的左子樹上最小的一位
TreeNode treeNode = getMinLeftTreeNode(node.right);
treeNode.left = node.left;
node.left.parent = treeNode;
//將最小左子樹結(jié)點(diǎn)的右子樹全部接上來
TreeNode leftNodeParent = treeNode.parent;
leftNodeParent.left = treeNode.right;
if (treeNode.right != null)
treeNode.right.parent = leftNodeParent;
treeNode.parent = null;
//將最小左子樹結(jié)點(diǎn)頂?shù)礁恢?
treeNode.right = node.right;
//處理根情況
if (parent == null) {
//要?jiǎng)h除的節(jié)點(diǎn)既為根節(jié)點(diǎn)
node.left = null;
node.right = null;
leftNodeParent.parent = treeNode;
root = treeNode;
} else {
//要?jiǎng)h除的節(jié)點(diǎn)不是根節(jié)點(diǎn)
if (parent.left == node) {
//左節(jié)點(diǎn)
parent.left = treeNode;
} else {
//右節(jié)點(diǎn)
parent.right = treeNode;
}
treeNode.parent = parent;
node.left = null;
node.right = null;
node.parent = null;
}
}
}
}
}
/**
* 找左節(jié)點(diǎn)最小值
*/
private TreeNode getMinLeftTreeNode(TreeNode node) {
TreeNode curNode = null;
if (node == null)
return null;
else {
curNode = node;
while (curNode.left != null) {
curNode = curNode.left;
}
}
return curNode;
}
public class TreeNode {
int data;
TreeNode left;
TreeNode right;
TreeNode parent;
public TreeNode(int data) {
this.data = data;
this.left = null;
this.right = null;
this.parent = null;
}
}
}
