TreeNode 类
class TreeNode {
int data;
TreeNode leftNode;
TreeNode rightNode;
public TreeNode() {
}
public TreeNode(int data) {
this.data = data;
}
}
1. 前序遍历（中左右）
/**
* 前序遍历
*
* @param root
*/
public static void preOrder(TreeNode root) {
if (root == null)
return;
System.out.print(root.data + " ");
preOrder(root.leftNode);
preOrder(root.rightNode);
}
2. 中序遍历（左中右）
/**
* 中序遍历
*
* @param root
*/
public static void inOrder(TreeNode root) {
if (root == null)
return;
inOrder(root.leftNode);
System.out.print(root.data + " ");
inOrder(root.rightNode);
}
3. 后序遍历（左右中）
/**
* 后序遍历
*
* @param root
*/
public static void postOrder(TreeNode root) {
if (root == null)
return;
postOrder(root.leftNode);
postOrder(root.rightNode);
System.out.print(root.data + " ");
}
4. 查找节点
/**
* 查找节点
*
* @param data
* @param root
* @return
*/
public static TreeNode findNode(int data, TreeNode root) {
if (root == null)
return null;
TreeNode current = root;
while (current.data != data) {
if (data < current.data) {
current = current.leftNode;
} else {
current = current.rightNode;
}
if (current == null)
return null;
}
return current;
}
5. 插入节点
/**
* 插入节点
*
* @param newNode
* @param root
*/
public static void insertNode(TreeNode newNode, TreeNode root) {
if (newNode == null)
return;
if (root == null) {
root = newNode;
return;
}
TreeNode current = root;
while (true) {
if (newNode.data < current.data) {
if (current.leftNode == null) {
current.leftNode = newNode;
return;
}
current = current.leftNode;
} else {
if (current.rightNode == null) {
current.rightNode = newNode;
return;
}
current = current.rightNode;
}
}
}
6. 删除节点
/**
* 删除节点
* @param data
* @param root
* @return
*/
public static boolean deleteNode(int data, TreeNode root) {
if (root == null)
return false;
TreeNode current = root;
TreeNode parent = root;
boolean isLeftChild = false;
while (data != current.data) {
parent = current;
if (data < current.data) {
isLeftChild = true;
current = current.leftNode;
} else {
isLeftChild = false;
current = current.rightNode;
}
if (current == null)
return false;
}
if (current.leftNode == null && current.rightNode == null) {
if (current == root) {
root = null;
return true;
} else if (isLeftChild) {
parent.leftNode = null;
} else {
parent.rightNode = null;
}
} else if (current.leftNode == null) {
if (current == root) {
root = root.rightNode;
return true;
} else if (isLeftChild) {
parent.leftNode = current.rightNode;
} else {
parent.rightNode = current.rightNode;
}
} else if (current.rightNode == null) {
if (current == root) {
root = root.leftNode;
} else if (isLeftChild) {
parent.leftNode = current.leftNode;
} else {
parent.rightNode = current.rightNode;
}
} else {
TreeNode successor = getSuccessor(current);
if (current == root) {
root = successor;
}else if(isLeftChild){
parent.leftNode = successor;
}else{
parent.rightNode = successor;
}
successor.leftNode = current.leftNode;
}
return true;
}
/**
* 获取后继节点
* @param delNode
* @return
*/
private static TreeNode getSuccessor(TreeNode delNode) {
TreeNode successorParent = delNode;
TreeNode successor = delNode;
TreeNode current = delNode.rightNode;
while (current != null) {
successorParent = successor ;
successor = current;
current = current.leftNode;
}
if(successor != delNode.rightNode){
successorParent.leftNode = successor.rightNode;
successor.rightNode = delNode.rightNode;
}
return successor;
}
