這部分主要是用代碼實現有序二叉樹、樹遍歷、刪除節點

目錄

1.構建有序二叉樹

1.1原理

?1.2插入實現

2.廣度優先遍歷--隊列實現

3.深度優先遍歷--遞歸實現

3.1先序遍歷

3.2中序遍歷

3.3后序遍歷

4.刪除

4.1刪除葉子節點

4.2刪除有一棵子樹的節點

4.3刪除有兩棵子樹的節點

5.整體代碼

---

1.構建有序二叉樹

1.1原理

左邊節點值小于父節點，右邊節點值大于父節點，看下圖

?1.2插入實現

當傳入value值時，判斷root節點是否為空：空的話建立新節點做root；不空，建立一個中間節點index，然后循環按照插入原理判斷插到哪，代碼如下：

 public void insert(int value){Node node = new Node(value);if(root==null){root = node;return;}Node index = root;while(true) {if(index.value>value) {//要插入的節點值小if(index.left==null) {//插入index.left=node;return;}index=index.left;}else{//要插入的節點值大if(index.right==null){index.right=node;return;}index=index.right;}}

2.廣度優先遍歷--隊列實現

廣度優先遍歷就是層次遍歷，使用隊列實現。當隊列中進入一個新節點，輸出后就找這個節點的左右孩子入隊。

代碼如下：

    public void levelOrder() {Queue<Node> queue = new LinkedList<Node>();if(root!=null) {queue.add(root);}Node index;while (!queue.isEmpty()){index = queue.poll();System.out.print(index.value+Messages.getString("BinaryTree.0")); //$NON-NLS-1$if(index.left!=null){queue.add(index.left);}if(index.right!=null) {queue.add(index.right);}}System.out.println();}

3.深度優先遍歷--遞歸實現

3.1先序遍歷

就是根-左-右的順序，使用遞歸實現，代碼如下：

    /** 先序遍歷*/public void beforeOrder(Node node){if(node==null) {return;}System.out.print(node.value+Messages.getString("BinaryTree.1"));beforeOrder(node.left);beforeOrder(node.right);}

3.2中序遍歷

使用左-根-右順序

    /** 中序遍歷*/public void inOrder(Node node){if(node==null){return;}inOrder(node.left);System.out.print(node.value+Messages.getString("BinaryTree.2")); //$NON-NLS-1$inOrder(node.right);}

3.3后序遍歷

使用左-右-根順序，代碼如下：

    /** 后序遍歷*/public void afterOrder(Node node) {if(node==null) {return;}afterOrder(node.left);afterOrder(node.right);System.out.print(node.value+Messages.getString("BinaryTree.3")); }

4.刪除

刪除比較復雜，要分三種情況：

4.1刪除葉子節點

1. 找到目標節點：在二叉搜索樹中定位要刪除的目標節點target?。
2. 找到父節點：確定target節點的父節點parent?。
3. 判斷父節點情況：
   • 若無父節點，意味著target是根節點，直接將根節點置為null?。
   • 若有父節點，判斷target是parent的左子還是右子：是左子就執行parent.left = null?；是右子就執行parent.right = null?。

需要額外寫一個函數來尋找父節點，代碼如下：

    /*** 找目標值的父節點*/public Node searchParent(int value) {if(root==null) {return null;}Node index = root;while (index!=null) {if((index.left!=null&&index.left.value==value)||(index.right!=null&&index.right.value==value)) {return index;}else if (index.value>value) {index=index.left;}else {index = index.right;}}return null;}

這部分代碼如下：

		if(target.left==null&&target.right==null) {//葉子節點//沒有父節點if(parent==null) {root=null;return;}//有父節點if(parent.left!=null&&parent.left.value==value) {parent.left=null;}else {parent.right=null;}}

4.2刪除有一棵子樹的節點

1. 找到目標節點：確定要刪除的節點target?。
2. 找到父節點：找到target節點的父節點parent?。
3. 判斷父節點和子樹情況：
   • 若無父節點，即target是根節點，若target有左子樹，讓根節點指向其左子樹（root = root.left?）；若有右子樹，讓根節點指向其右子樹（root = root.right?）。
   • 若有父節點，先確定target是parent的左子還是右子，再根據target自身有左子樹還是右子樹，調整parent相應子樹指針（如parent.left = target.left?或parent.right = target.right?）。

代碼如下：

			//有一棵子樹的節點//沒有父節點if(parent==null) {//目標節點有左子樹還是右子樹if(target.left!=null) {root = root.left;}else {root=root.right;}return;}//有父節點//判斷目標節點是父節點的左孩子還是右孩子if(parent.left!=null&&parent.left.value==value) {//左孩子//目標節點有左子樹還是右子樹if(target.left!=null) {parent.left = target.left;}else {parent.left = target.right;}}else {//右孩子//目標節點有左子樹還是右子樹if(target.left!=null) {parent.right = target.left;}else {parent.right = target.right;}}

4.3刪除有兩棵子樹的節點

1. 找到目標節點：定位要刪除的節點target?。
2. 替換節點選擇：獲取target左子樹的最大值節點或者右子樹的最小值節點作為替換節點。
3. 刪除目標節點：用選定的替換節點替代target節點的位置 ，并處理好相關子樹連接關系（如parent.left = target.right?或parent.right = target.left?等）。

需要額外寫一個判斷最小值的函數：

	/*** 找樹當中的最小值*/public int min(Node node) {Node index = node;while(index.left!=null) {index=index.left;}return index.value;}

?

代碼如下：

 if(target.left!=null&&target.right!=null) {//有兩棵子樹的節點int minVal = min(target.right);delete(minVal);target.value = minVal;}

5.整體代碼

代碼如下：

package com.qcby.樹;import java.util.LinkedList;
import java.util.Queue;public class BinaryTree {Node root;/*** 插入*/public void insert(int value){Node node = new Node(value);if(root==null){root = node;return;}Node index = root;while(true) {if(index.value>value) {//要插入的節點值小if(index.left==null) {//插入index.left=node;return;}index=index.left;}else{//要插入的節點值大if(index.right==null){index.right=node;return;}index=index.right;}}}/** 廣度優先遍歷*/public void levelOrder() {Queue<Node> queue = new LinkedList<Node>();if(root!=null) {queue.add(root);}Node index;while (!queue.isEmpty()){index = queue.poll();System.out.print(index.value+Messages.getString("BinaryTree.0")); //$NON-NLS-1$if(index.left!=null){queue.add(index.left);}if(index.right!=null) {queue.add(index.right);}}System.out.println();}/** 先序遍歷*/public void beforeOrder(Node node){if(node==null) {return;}System.out.print(node.value+Messages.getString("BinaryTree.1")); //$NON-NLS-1$beforeOrder(node.left);beforeOrder(node.right);}/** 中序遍歷*/public void inOrder(Node node){if(node==null){return;}inOrder(node.left);System.out.print(node.value+Messages.getString("BinaryTree.2")); //$NON-NLS-1$inOrder(node.right);}/** 后序遍歷*/public void afterOrder(Node node) {if(node==null) {return;}afterOrder(node.left);afterOrder(node.right);System.out.print(node.value+Messages.getString("BinaryTree.3")); //$NON-NLS-1$}/** 查找*/public Node search(int value) {if(root==null) {return null;}Node index = root;while (index!=null) {if(index.value==value){return index;}else if(index.value>value) {index = index.left;}else {index=index.right;}}return null;}/*** 找目標值的父節點*/public Node searchParent(int value) {if(root==null) {return null;}Node index = root;while (index!=null) {if((index.left!=null&&index.left.value==value)||(index.right!=null&&index.right.value==value)) {return index;}else if (index.value>value) {index=index.left;}else {index = index.right;}}return null;}/*** 找樹當中的最小值*/public int min(Node node) {Node index = node;while(index.left!=null) {index=index.left;}return index.value;}/*** 刪除*/public void delete(int value){if(root==null) {System.out.println(Messages.getString("BinaryTree.4")); return;}//找目標節點Node target = search(value);if(target==null) {System.out.println(Messages.getString("BinaryTree.5")); return;}//找目標節點的父節點Node parent = searchParent(value);//三種情況，分情況討論if(target.left==null&&target.right==null) {//葉子節點//沒有父節點if(parent==null) {root=null;return;}//有父節點if(parent.left!=null&&parent.left.value==value) {parent.left=null;}else {parent.right=null;}}else if(target.left!=null&&target.right!=null) {//有兩棵子樹的節點int minVal = min(target.right);delete(minVal);target.value = minVal;}else {//有一棵子樹的節點//沒有父節點if(parent==null) {//目標節點有左子樹還是右子樹if(target.left!=null) {root = root.left;}else {root=root.right;}return;}//有父節點//判斷目標節點是父節點的左孩子還是右孩子if(parent.left!=null&&parent.left.value==value) {//左孩子//目標節點有左子樹還是右子樹if(target.left!=null) {parent.left = target.left;}else {parent.left = target.right;}}else {//右孩子//目標節點有左子樹還是右子樹if(target.left!=null) {parent.right = target.left;}else {parent.right = target.right;}}}}@Overridepublic String toString() {return "BinaryTree [root=" + root + "]";}}

?