• 💌1.何謂樹
• • 💙 1.1.樹的定義
  • 💙 1.2.樹的特點
  • 💙 1.3.樹的基本術語
• 💌2.認識二叉樹
• • 🔥 1.1.二叉樹的定義
  • 🔥 1.2.二叉樹的分類
  • • 💦 1.2.1.滿二叉樹
    • 💦 1.2.2.完全二叉樹
    • 💦 1.2.3.平衡二叉樹
• 💌3.二叉樹的遍歷
• • 🔥 3.1.前序遍歷
  • 🔥 3.2.中序遍歷
  • 🔥 3.3.后序遍歷
• 💌4.二叉樹節點的查找
• • 🔥 4.1.前序查找
  • 🔥 4.2.中序查找
  • 🔥 4.3.后序查找
• 💌5.二叉樹節點的刪除

---

💌1.何謂樹

💙 1.1.樹的定義

樹是一種數據結構，它是由n（n>=1）個有限節點組成一個具有層次關系的集合。

💙 1.2.樹的特點

(1)每個節點有零個或多個子節點；
(2) 沒有父節點的節點稱為根節點；
(3) 每一個非根節點有且只有一個父節點；
(4) 除了根節點外，每個子節點可以分為多個不相交的子樹。

💙 1.3.樹的基本術語

結點的度：結點擁有的子樹的數目。
葉子節點：度為零的結點。
樹的度：樹中結點的最大的度。
樹的層次：根結點的層次為1，其余結點的層次等于該結點的雙親結點的層次加1。
樹的高度：樹中結點的最大層次。
無序樹：如果樹中結點的各子樹之間的次序是不重要的，可以交換位置。
有序樹：如果樹中結點的各子樹之間的次序是重要的, 不可以交換位置。

---

💌2.認識二叉樹

🔥 1.1.二叉樹的定義

二叉樹是每個節點最多有兩個子樹的樹結構。它有五種基本形態：二叉樹可以是空集；根可以有空的左子樹或右子樹；或者左、右子樹皆為空。

🔥 1.2.二叉樹的分類

💦 1.2.1.滿二叉樹

除了葉子節點之外，其他所有的節點都必須包含左子節點和右子節點

💦 1.2.2.完全二叉樹

對于n層的二叉樹，它的n-1層的節點個數必須達到最大值。第n層包含葉子節點，并且葉子節點從左到右依次排列

💦 1.2.3.平衡二叉樹

它的任意節點的左右子樹的高度差的絕對值不超過1

---

💌3.二叉樹的遍歷

🔥 3.1.前序遍歷

//前序遍歷 根->左—>右public void preOrder(TreeNode temp) {if (temp == null) { //遞歸結束條件return;}System.out.println(temp);preOrder(temp.getLeft());preOrder(temp.getRight());}

🔥 3.2.中序遍歷

//中序遍歷 左->根->右public void infixOrder(TreeNode temp) {if (temp == null) {return;}preOrder(temp.getLeft());System.out.println(temp);preOrder(temp.getRight());}

🔥 3.3.后序遍歷

//后序遍歷 左->右->根public void sufOrder(TreeNode temp) {if (temp == null) {return;}preOrder(temp.getLeft());preOrder(temp.getRight());System.out.println(temp);}

---

💌4.二叉樹節點的查找

以前序遍歷為例
一直遞歸下去，如果找到了進行返回即可。然后用resultNode進行接收，直接返回

🔥 4.1.前序查找

/*** 前序查找* @param temp 節點* @param no 帶查詢id* @return 查詢到的*/public TreeNode preSearch(TreeNode temp, int no) {if (temp == null) {return null;}if (temp.id == no) { //說明找到了，直接返回return temp;}TreeNode resultNode = null;if (temp.getLeft() != null) {resultNode = preSearch(temp.getLeft(), no);}if (resultNode != null) {return resultNode; //如果找到，直接返回，就不用再執行下面的right}if (temp.getRight() != null) {resultNode = preSearch(temp.getRight(), no);}return resultNode;}

🔥 4.2.中序查找

/*** 中序查找* @param cur 節點* @param no 帶查詢id* @return 查詢到的*/public TreeNode infixSearch(TreeNode cur, int no) {if (cur == null) {return null;}TreeNode resultNode = null;if (cur.getLeft() != null) {resultNode = infixSearch(cur.getLeft(), no);}if (resultNode != null) {return resultNode;}if (cur.id == no) {return cur;}if (cur.getRight() != null) {resultNode = infixSearch(cur.getRight(), no);}return resultNode;}

🔥 4.3.后序查找

/*** 后序查找* @param last 節點* @param no 帶查詢id* @return 查詢到的*/public TreeNode sufSearch(TreeNode last, int no) {if (last == null) {return null;}TreeNode resultNode = null;if (last.getLeft() != null) {resultNode = sufSearch(last.getRight(), no);}if (resultNode != null) {return resultNode;}if (last.getRight() != null) {resultNode = sufSearch(last.getRight(), no);}if (last.id == no) {resultNode = last;}return resultNode;}

💌5.二叉樹節點的刪除

💥刪除時如果不是葉子節點需要將整個子樹一塊刪除

這里需要注解的是結束條件，有兩種情況(以左為例子)

1.一直往下遞歸，沒有找到該節點，直接返回即可
2.head.getLeft().id == no，說明它的左子節點是需要進行刪除

/*** 如果是葉子節點，則將葉子節點刪除即可* 如果不是葉子節點，則需要將相關的子樹都刪除* @param no id*/public void deleteTreeNode(TreeNode head, int no) {if (head.getLeft() == null || head.getLeft().id == no) {head.setLeft(null);return;} else if (head.getRight() == null || head.getRight().id == no) {head.setRight(null);return;}deleteTreeNode(head.getLeft(), no);deleteTreeNode(head.getRight(), no);}

總結

以上是生活随笔為你收集整理的【❤️算法系列之二叉树的实现(包含前序、中序、后序遍历以及节点的查找和删除)❤️】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。