寫在前面
資料結構全文
樹結構
集合底層用陣列擴容實現的
節點，一個物件，樹的一個單位
葉子節點，沒有子節點的節點
節點的權，節點值
路徑，從根節點找到該節點的路線
層，同一個級別
樹的高度，層數
森林，多顆子樹
二叉樹，每個節點，最多隻能有兩個子節點
如果二叉樹的所有葉子節點都在最後一層，且節點總數為2^n-1，n為層數，則為滿二叉樹
如果該二叉樹的所有葉子節點都在最後一層或者倒數第二層，而且最後一層的葉子節點在左邊連續，倒數第二層的葉子節點葉在右連續，則為完全二叉樹，滿二叉樹一定是完全二叉樹
遍歷
前序遍歷，先輸出父節點，再遍歷左子樹和右子樹
中序遍歷，先遍歷左子樹，再輸出父節點，再遍歷右子樹
後序遍歷，先遍歷左子樹，在遍歷右子樹，最後輸出父節點
建立樹
class BinaryTree { private Node root； public void setRoot（Node root） { this。root = root； } //前序遍歷 public void preOrder（） { if （this。root ！= null） { this。root。preOrder（）； } else { System。out。println（“empty”）； } } //中序遍歷 public void infixOrder（） { if （this。root ！= null） { this。root。infixOrder（）； } else { System。out。println（“empty”）； } } //後序遍歷 public void postOrder（） { if （this。root ！= null） { this。root。postOrder（）； } else { System。out。println（“empty”）； } }}複製程式碼
建立節點
class Node { private int id； private String name； private Node left； //左節點 private Node right； //右節點 //setter getter toString constructor。。。 //前序遍歷 父左右 public void preOrder（） { //先輸出父節點 System。out。println（this）； //向左子樹前序遍歷 if （this。left ！= null） { this。left。preOrder（）； } //向右子樹前序遍歷 if （this。right ！= null） { this。right。preOrder（）； } } //中序遍歷 左父右 public void infixOrder（） { if （this。left ！= null） { this。left。infixOrder（）； } System。out。println（this）； if （this。right ！= null） { this。right。infixOrder（）； } } //後序編列 左右父 public void postOrder（） { if （this。left ！= null） { this。left。postOrder（）； } if （this。right ！= null） { this。right。postOrder（）； } System。out。println（this）； }}複製程式碼
查詢
查詢順序與遍歷一致
前序查詢
public Node preOrderSearch（int id） { if （this。id == id） { return this； } Node res = null； if （this。left ！= null） { res = this。left。preOrderSearch（id）； } if （res ！= null） { //左子樹找到 return res； } if （this。right ！= null） { res = this。right。preOrderSearch（id）； } if （res ！= null） { //左子樹找到 return res； } return res；}複製程式碼
中序查詢
public Node infixOrderSearch（int id） { Node res = null； if （this。left ！= null） { res = this。left。preOrderSearch（id）； } if （res ！= null） { //左子樹找到 return res； } if （this。id == id） { return this； } if （this。right ！= null） { res = this。right。preOrderSearch（id）； } if （res ！= null） { //左子樹找到 return res； } return res；}複製程式碼
後序查詢
public Node postOrderSearch（int id） { Node res = null； if （this。right ！= null） { res = this。right。preOrderSearch（id）； } if （res ！= null） { //左子樹找到 return res； } if （this。left ！= null） { res = this。left。preOrderSearch（id）； } if （res ！= null） { //左子樹找到 return res； } if （this。id == id） { return this； } return res；}複製程式碼
樹中呼叫
public Node preOrderSearch（int id） { if （this。root ！= null） { return this。root。preOrderSearch（id）； } else { System。out。println（“empty”）； return null； }}public Node infixOrderSearch（int id） { if （this。root ！= null） { return this。root。infixOrderSearch（id）； } else { System。out。println（“empty”）； return null； }}public Node postOrderSearch（int id） { if （this。root ！= null） { return this。root。postOrderSearch（id）； } else { System。out。println（“empty”）； return null； }}複製程式碼
刪除
刪除的節點是葉子節點，刪除該節點；刪除的非葉子節點，刪除該子樹
找的是，刪除節點的父節點，才能幹掉刪除節點
判斷是不是root，樹中判斷root後，再進行子節點的判斷
public void delNode（int id） { if （root ！= null） { //判斷root是不是要刪除的 if （root。getId（） == id） { root = null； } else { root。delNode（id）； } } else { System。out。println（“empty”）； }}複製程式碼
節點，先判斷當前節點的左右子節點是不是，如果不是，繼續遞迴進入，判斷左右子節點的子節點
public void delNode （int id） { if （this。left ！= null && this。left。id == id） { this。left = null； return； } if （this。right ！= null && this。right。id == id） { this。right = null； return； } if （this。left ！= null） { this。left。delNode（id）； } if （this。right ！= null） { this。right。delNode（id）； }}複製程式碼
修改刪除規則
如果非葉子節點只有一個節點，那麼就用該子節點替代；如果非葉子節點有兩個子節點，左子節點替代，右子節點作為左子節點的右子節點
但是沒有實現，如果左右子節點均有子節點怎麼辦
public void delNode （int id） { if （this。left ！= null && this。left。id == id） { if （this。left。left == null && this。left。right == null） { this。left = null； } else if （this。left。left ！= null && this。left。right == null） { //刪除的節點只有左節點 this。left = this。left。left； } else if （this。left。left == null && this。left。right ！= null） { //刪除的節點只有右節點 this。left = this。left。right； } else { //右節點作為左節點的子節點 this。left。left。right = this。left。right； this。left。right = null； //左節點替代刪除的節點 this。left = this。left。left； } return； } if （this。right ！= null && this。right。id == id） { if （this。right。left == null && this。right。right == null） { this。right = null； } else if （this。right。left ！= null && this。right。right == null） { //刪除的節點只有左節點 this。right = this。right。left； } else if （this。right。left == null && this。right。right ！= null） { //刪除的節點只有右節點 this。right = this。right。right； } else { //右節點作為左節點的子節點 this。right。left。right = this。right。right； this。right。right = null； //左節點替代刪除的節點 this。right = this。right。left； } return； } if （this。left ！= null） { this。left。delNode（id）； } if （this。right ！= null） { this。right。delNode（id）； }}複製程式碼
順序儲存二叉樹
陣列轉換為樹
第n個元素的左子節點陣列中下標為2*n+1，右子節點陣列中下標為2*n+2，父節點陣列中下標為（n-1）/2，n為在陣列中的下標
class ArrBinaryTree { private int［］ arr； public ArrBinaryTree（int［］ arr） { this。arr = arr； } public void preOrder（） { this。preOrder（0）； } //順序儲存二叉的前序遍歷 public void preOrder（int index） { //陣列為空 if （arr == null || arr。length == 0） { System。out。println（“empty”）； return； } System。out。println（arr［index］）； //左遍歷 if （（index * 2 + 1） < arr。length） { preOrder（index * 2 + 1）； } //右遍歷 if （（index * 2 + 2） < arr。length） { preOrder（index * 2 + 2）； } }}複製程式碼
線索化二叉樹
對於n個節點的二叉樹，含有n+1個指標域，2n-（n-1）一個節點有兩個指標，n個節點連線只需要n-1個指標
利用二叉連結串列的空指標域存放指向該節點在某種遍歷次序下的前驅和後繼節點，按照這個次序遍歷的前後節點
前序線索化二叉樹
public void threadedNodes（ThreadedNode node） { if （node == null） { return； } //先處理當前節點的前驅節點 if （node。getLeft（） == null） { node。setLeft（preNode）； //修改型別，如果是0才能進入遞迴判斷子樹 node。setLeftType（1）； } //處理後繼節點 if （preNode ！= null && preNode。getRight（） == null） { //讓前驅節點的右指標指向當前節點 preNode。setRight（node）； preNode。setRightType（1）； } //每處理一個節點後，讓當前節點是下一個節點的前驅節點 preNode = node； if （node。getLeftType（） == 0） { threadedNodes（node。getLeft（））； } if （node。getRightType（） == 0） { threadedNodes（node。getRight（））； }}複製程式碼
中序線索化二叉樹
public void threadedNodes（ThreadedNode node） { if （node == null） { return； } //線索 左父右 threadedNodes（node。getLeft（））； //先處理當前節點的前驅節點 if （node。getLeft（） == null） { node。setLeft（preNode）； //修改型別 node。setLeftType（1）； } //處理後繼節點，用當前節點來處理前一個節點的後繼節點 if （preNode ！= null && preNode。getRight（） == null） { //讓前驅節點的右指標指向當前節點 preNode。setRight（node）； preNode。setRightType（1）； } //每處理一個節點後，讓當前節點是下一個節點的前驅節點 //按照中序順序進行排列 preNode = node； threadedNodes（node。getRight（））；}複製程式碼
後續線索化二叉樹
public void threadedNodes（ThreadedNode node） { if （node == null） { return； } threadedNodes（node。getLeft（））； threadedNodes（node。getRight（））； //先處理當前節點的前驅節點 if （node。getLeft（） == null） { node。setLeft（preNode）； //修改型別 node。setLeftType（1）； } //處理後繼節點 if （preNode ！= null && preNode。getRight（） == null） { //讓前驅節點的右指標指向當前節點 preNode。setRight（node）； preNode。setRightType（1）； } //每處理一個節點後，讓當前節點是下一個節點的前驅節點 preNode = node；}複製程式碼
遍歷線索化二叉樹
前序遍歷線索化二叉樹
public void threadedList（） { ThreadedNode node = root； while （node ！= null） { //一直向左輸出，直到找到 LeftType = 1的節點，表明向左到底了 while （node。getLeftType（） == 0） { System。out。println（node）； node = node。getLeft（）； } System。out。println（node）； node = node。getRight（）； }}複製程式碼
中序遍歷線索化二叉樹
public void threadedList（） { ThreadedNode node = root； while （node ！= null） { //找到第一個leftType=1的節點 while （node。getLeftType（） == 0） { node = node。getLeft（）； } System。out。println（node）； //如果當前節點的右指標是後繼節點，就一直輸出 while （node。getRightType（） == 1） { node = node。getRight（）； System。out。println（node）； } node = node。getRight（）； }}複製程式碼
因為後序遍歷順序為左右父，會出現，左子樹輸出完畢，回到當前子樹的父節點，該父節點有作為右子樹左子節點的前驅節點，但是由於該父節點的兩個節點左右都有子節點，那麼就會導致該父節點透過正常方式無法找到下一個節點，就有了兩種處理方式逆序入棧，從右開始入棧和在節點中記錄雙親節點，在遍歷中記錄前一個節點，在遍歷完左子樹後，如果繼續遍歷時，節點的右子節點為上一個節點，則要找到節點的雙親節點，遍歷右節點，也就是雙親節點
後序遍歷線索化二叉樹（逆序）
public void threadedList（） { ThreadedNode node = root； Stack
後序遍歷線索化二叉樹（正序）
public void threadedList（） { ThreadedNode node = root； ThreadedNode pre = null； while （node ！= null） { //找到第一個leftType=1的節點 while （node。getLeftType（） == 0） { node = node。getLeft（）； } System。out。println（node）； //該起始左結點的後繼節點全部找到，並往回指向了一次 while （node。getRightType（） == 1） { //記錄上一個節點，為了進行判斷；如果上一個節點為某個父節點的右子節點 //說明，這右半邊已經處理完成，要找到雙親節點，進行處理 pre = node； node = node。getRight（）； System。out。println（node）； } //往回指向了根節點，置空，準備跳出迴圈 if （node == root） { node = null； } //上一個節點為該節點的右子節點，說明這個節點的樹結構已經走完，找到該節點的雙親節點 while （node ！= null && node。getRight（） == pre） { pre = node； node = node。getParent（）； } //處理右子樹，並從下面一層開始，與上一輪完畢的左子節點是兄弟節點 if （node ！= null && node。getRightType（） == 0） { node = node。getRight（）； } }}
作者：99永遠差一分
連結：https：//juejin。cn/post/7005070335540215816
著作權歸作者所有。商業轉載請聯絡作者獲得授權，非商業轉載請註明出處。
