# 用Java實現二叉樹

## Java深度優先搜索

Java的深度優先搜索算法指南，同時使用Tree和Graph數據結構。

## 2.二叉樹

``````class Node {

int value;

Node left;

Node right;

Node(int value) {

this.value = value;

right = null;

left = null;

}

}``````

``````public class BinaryTree {

Node root;

// ...

}``````

## 3.常用操作

### 3.1。插入元素

• 如果新節點的值小於當前節點的值，我們轉到左子節點
• 如果新節點的值大於當前節點的值，則轉到正確的子節點
• 噹噹前節點為null時，我們到達了葉節點，我們可以在該位置插入新節點

``````private Node addRecursive(Node current, int value) {

if (current == null) {

return new Node(value);

}

if (value < current.value) {

} else if (value > current.value) {

} else {

return current;

}

return current;

}``````

``````public void add(int value) {

}``````

``````private BinaryTree createBinaryTree() {

BinaryTree bt = new BinaryTree();

return bt;

}``````

### 3.2。尋找元素

``````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);

}``````

``````public boolean containsNode(int value) {

return containsNodeRecursive(root, value);

}``````

``````@Test

BinaryTree bt = createBinaryTree();

assertTrue(bt.containsNode(6));

assertTrue(bt.containsNode(4));

assertFalse(bt.containsNode(1));

}``````

### 3.3。刪除元素

``````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;

}``````

• 一個節點沒有子節點–這是最簡單的情況；我們只需要在其父節點中將此節點替換為null
• **一個節點恰好有一個子節點-**在父節點中，我們用其唯一的子節點替換該節點。
• 一個節點有兩個孩子–這是最複雜的情況，因為它需要對樹進行重組

``````if (current.left == null && current.right == null) {

return null;

}``````

``````if (current.right == null) {

return current.left;

}

if (current.left == null) {

return current.right;

}``````

``````private int findSmallestValue(Node root) {

return root.left == null ? root.value : findSmallestValue(root.left);

}``````

``````int smallestValue = findSmallestValue(current.right);

current.value = smallestValue;

current.right = deleteRecursive(current.right, smallestValue);

return current;``````

``````public void delete(int value) {

root = deleteRecursive(root, value);

}``````

``````@Test

public void givenABinaryTree_WhenDeletingElements_ThenTreeDoesNotContainThoseElements() {

BinaryTree bt = createBinaryTree();

assertTrue(bt.containsNode(9));

bt.delete(9);

assertFalse(bt.containsNode(9));

}``````

## 4.穿越樹

### 4.1。深度優先搜索

``````public void traverseInOrder(Node node) {

if (node != null) {

traverseInOrder(node.left);

System.out.print(" " + node.value);

traverseInOrder(node.right);

}

}``````

``3 4 5 6 7 8 9``

``````public void traversePreOrder(Node node) {

if (node != null) {

System.out.print(" " + node.value);

traversePreOrder(node.left);

traversePreOrder(node.right);

}

}``````

``6 4 3 5 8 7 9``

``````public void traversePostOrder(Node node) {

if (node != null) {

traversePostOrder(node.left);

traversePostOrder(node.right);

System.out.print(" " + node.value);

}

}``````

``3 5 4 7 9 8 6``

### 4.2。廣度優先搜索

``````public void traverseLevelOrder() {

if (root == null) {

return;

}

while (!nodes.isEmpty()) {

Node node = nodes.remove();

System.out.print(" " + node.value);

if (node.left != null) {

}

if (node.right != null) {

}

}

}``````

``6 4 8 3 5 7 9``