原理
后續(xù)原理妒穴，先上代碼
代碼
樹節(jié)點
package per.lihao.tree;
/**
* @author : LiHao
* @date : 2018/12/4 9:59
*/
public class TreeNode {
/**
* 關鍵字
*/
private int data;
/**
* 左子樹節(jié)點
*/
private TreeNode lnode;
/**
* 右子樹節(jié)點
*/
private TreeNode rnode;
/**
* 父節(jié)點
*/
private TreeNode parent;
private boolean stackFirst = false;
public TreeNode getParent() {
return parent;
}
public void setParent(TreeNode parent) {
this.parent = parent;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public TreeNode getLnode() {
return lnode;
}
public void setLnode(TreeNode lnode) {
this.lnode = lnode;
}
public TreeNode getRnode() {
return rnode;
}
public void setRnode(TreeNode rnode) {
this.rnode = rnode;
}
public boolean isStackFirst() {
return stackFirst;
}
public void setStackFirst(boolean stackFirst) {
this.stackFirst = stackFirst;
}
public TreeNode(){}
public TreeNode(int k){
data = k;
}
}
二叉樹
package per.lihao.tree;
import java.util.Stack;
/**
* 二叉樹
* @author : LiHao
* @date : 2018/12/26 10:41
*/
public class BinaryTree {
/**
* 根節(jié)點
*/
protected TreeNode root;
public BinaryTree(){}
/**
* 構造函數(shù)
* @param node
*/
public BinaryTree(TreeNode node){
root = node;
}
public TreeNode getRoot() {
return root;
}
public void setRoot(TreeNode root) {
this.root = root;
}
/**
* 遞歸
* 中序遍歷根節(jié)點
*/
public void inOrderTraversalRecursion(){
inOrderTraversalRecursion(root);
System.out.println();
}
/**
* 遞歸
* 中序遍歷
* @param node
*/
protected void inOrderTraversalRecursion(TreeNode node){
if (node==null){
return;
}
inOrderTraversalRecursion(node.getLnode());
System.out.print(node.getData()+" ");
inOrderTraversalRecursion(node.getRnode());
}
/**
* 循環(huán)
* 中序遍歷根節(jié)點
*/
public void inOrderTraversalLoop(){
inOrderTraversalLoop(root);
System.out.println();
}
/**
* 循環(huán)
* 中序遍歷
* @param node
*/
protected void inOrderTraversalLoop(TreeNode node){
Stack<TreeNode> stack = new Stack<>();
TreeNode currentNode = node;
TreeNode temp;
// 一直往左找，同時沿線的節(jié)點放入棧借宵，直到最左邊的子節(jié)點為空
// 出棧，并打印該節(jié)點，然后轉(zhuǎn)向該節(jié)點的右子節(jié)點
while (currentNode!=null || !stack.isEmpty()){
while (currentNode!=null){
stack.push(currentNode);
currentNode = currentNode.getLnode();
}
if (!stack.isEmpty()){
temp = stack.pop();
System.out.print(temp.getData() + " ");
currentNode = temp.getRnode();
}
}
}
/**
* 遞歸
* 前序遍歷根節(jié)點
*/
public void preOrderTraversalRecursion(){
preOrderTraversalRecursion(root);
System.out.println();
}
/**
* 遞歸
* 前序遍歷
* @param node
*/
protected void preOrderTraversalRecursion(TreeNode node){
if (node==null){
return;
}
System.out.print(node.getData() + " ");
preOrderTraversalRecursion(node.getLnode());
preOrderTraversalRecursion(node.getRnode());
}
/**
* 循環(huán)
* 前序遍歷根節(jié)點
*/
public void preOrderTraversalLoop(){
preOrderTraversalLoop(root);
System.out.println();
}
/**
* 循環(huán)
* 前序遍歷
* @param node
*/
protected void preOrderTraversalLoop(TreeNode node){
Stack<TreeNode> stack = new Stack<>();
TreeNode currentNode = node;
TreeNode temp;
// 一直往左找了嚎，同時打印沿線的節(jié)點并放入棧，直到最左邊的子節(jié)點為空
// 出棧，然后轉(zhuǎn)向該節(jié)點的右子節(jié)點
while (currentNode!=null || !stack.isEmpty()){
while (currentNode!=null){
System.out.print(currentNode.getData() + " ");
stack.push(currentNode);
currentNode = currentNode.getLnode();
}
if (!stack.isEmpty()){
temp = stack.pop();
currentNode = temp.getRnode();
}
}
}
/**
* 遞歸
* 后序遍歷根節(jié)點
*/
public void postOrderTraversalRecursion(){
postOrderTraversalRecursion(root);
System.out.println();
}
/**
* 遞歸
* 后序遍歷
* @param node
*/
protected void postOrderTraversalRecursion(TreeNode node){
if (node==null){
return;
}
postOrderTraversalRecursion(node.getLnode());
postOrderTraversalRecursion(node.getRnode());
System.out.print(node.getData() + " ");
}
/**
* 循環(huán)
* 后序遍歷根節(jié)點
*/
public void postOrderTraversalLoop(){
postOrderTraversalLoop(root);
System.out.println();
}
/**
* 循環(huán)
* 后續(xù)遍歷
* @param node
*/
public void postOrderTraversalLoop(TreeNode node){
Stack<TreeNode> stack = new Stack<>();
TreeNode currentNode = node;
TreeNode temp;
// 先一直往左找歪泳，沿線節(jié)點放入棧萝勤，且節(jié)點處的stackfirst=false
// 當遇到左孩子為空時，取其右孩子繼續(xù)尋找呐伞，此時父節(jié)點的stackfirst=true
// 為true時打印節(jié)點
while (currentNode!=null || !stack.isEmpty()){
while (currentNode!=null){
stack.push(currentNode);
currentNode = currentNode.getLnode();
}
if (!stack.isEmpty()){
// 不取出節(jié)點敌卓，先判斷其stackfirst值
temp = stack.peek();
if (temp.isStackFirst()){
temp = stack.pop();
System.out.print(temp.getData() + " ");
}else {
temp.setStackFirst(true);
currentNode = temp.getRnode();
}
}
}
}
/**
* 生成測試樹
* 10
* / \
* 3 12
* /
* 34
* \
* 23
* @return node
*/
public static TreeNode makeTreeTest(){
TreeNode root = new TreeNode(10);
root.setLnode(new TreeNode(3));
TreeNode node1 = new TreeNode(12);
TreeNode node2 = new TreeNode(34);
TreeNode node3 = new TreeNode(23);
node1.setLnode(node2);
node2.setRnode(node3);
root.setRnode(node1);
return root;
}
}
二叉搜索樹
package per.lihao.tree;
/**
* 二叉搜索樹/二叉排序樹
* @author : LiHao
* @date : 2018/12/24 15:21
*/
public class BinarySearchTree extends BinaryTree {
/**
* 插入數(shù)據(jù) 自動生成樹結(jié)構
* @param k int
*/
public void insert(int k){
TreeNode node = new TreeNode(k);
insertNode(node);
}
/**
* 插入數(shù)據(jù)數(shù)組 自動生成樹結(jié)構
* @param ks int[]
*/
public void insert(int[] ks){
for (int k:ks){
insert(k);
}
}
/**
* 插入節(jié)點對象 構造BST樹
* @param node
*/
private void insertNode(TreeNode node){
// 若根節(jié)點為空，則返回當前節(jié)點為根節(jié)點
if (root==null){
root = node;
return;
}
TreeNode temp = root;
while (true){
if (node.getData()<=temp.getData()){
//若有左子樹伶氢，說明還需繼續(xù)比較趟径，移動到左子樹的根節(jié)點
if (temp.getLnode()!=null){
temp = temp.getLnode();
}
//若沒有左子樹，說明此node可以變作葉子節(jié)點
else {
temp.setLnode(node);
node.setParent(temp);
return;
}
}else {
//若有右子樹癣防，說明還需繼續(xù)比較蜗巧，移動到右子樹的根節(jié)點
if (temp.getRnode()!=null){
temp = temp.getRnode();
}else {
temp.setRnode(node);
node.setParent(temp);
return;
}
}
}
}
/**
* 查詢關鍵字節(jié)點，無則返回null
* @param k 關鍵字
* @return
*/
public TreeNode search(int k){
TreeNode temp = root;
while (temp != null){
if (temp.getData() == k){
return temp;
}else if (temp.getData()>=k){
temp = temp.getLnode();
}else{
temp = temp.getRnode();
}
}
return temp;
}
/**
* 查找關鍵字k的前驅(qū)節(jié)點蕾盯，若沒有 則返回null
* @param k
* @return
*/
public TreeNode searchPredecessor(int k){
TreeNode node = search(k);
if (node==null){
return node;
}
// 若有左子樹幕屹，則前驅(qū)為左子樹中最右邊的節(jié)點
TreeNode temp = node.getLnode();
while (temp!=null){
if (temp.getRnode()!=null){
temp = temp.getRnode();
}else {
return temp;
}
}
// 若無左子樹，則需要尋找當前節(jié)點的第一個有右孩子且左孩子中沒有該節(jié)點的祖先
if (temp==null){
temp = node.getParent();
while (temp!=null){
// 左父母的左子樹如果為空级遭，則前驅(qū)就是左父母
// 若是右父母望拖，需要找到其右父母的左父母
if (temp.getLnode()==null){
break;
}else {
if (temp.getLnode().getData()==k){
temp = temp.getParent();
}else {
break;
}
}
}
}
return temp;
}
/**
* 查找關鍵字k的后繼節(jié)點，若沒有 則返回null
* @param k 關鍵字
* @return
*/
public TreeNode searchSuccessor(int k){
// 首先查找命中的節(jié)點
TreeNode node = search(k);
if (node==null){
return null;
}
TreeNode temp = node.getRnode();
while (temp!=null){
if (temp.getLnode()!=null){
temp = temp.getLnode();
}else {
return temp;
}
}
if (temp==null){
temp = node.getParent();
while (temp!=null){
if (temp.getRnode()==null){
break;
}else {
if (temp.getRnode().getData()==k){
temp = temp.getParent();
}else {
break;
}
}
}
}
return temp;
}
/**
* 刪除某節(jié)點
* @param k
*/
public void delete(int k){
// 首先查找k 不存在則返回
TreeNode node = search(k);
if (node==null){
return;
}
if (node.getLnode()!=null && node.getRnode()!=null){
// 查詢其前驅(qū)節(jié)點
TreeNode pre = searchPredecessor(k);
node.setData(pre.getData());
if (pre.getParent()==node){
if (pre.getLnode()!=null){
TreeNode preLnode = pre.getLnode();
preLnode.setParent(node);
}
node.setLnode(pre.getLnode());
}else {
TreeNode preParent = pre.getParent();
preParent.setRnode(pre.getLnode());
if (pre.getLnode()!=null){
TreeNode preLnode = pre.getLnode();
preLnode.setParent(preParent);
}
}
}else if (node.getRnode()==null && node.getLnode()==null){
TreeNode parent = node.getParent();
if (node==parent.getLnode()){
parent.setLnode(null);
}else {
parent.setRnode(null);
}
node.setParent(null);
}else {
TreeNode parent = node.getParent();
TreeNode child = (node.getLnode()!=null)?node.getLnode():node.getRnode();
if (node==parent.getLnode()){
parent.setLnode(child);
}else {
parent.setRnode(child);
}
child.setParent(parent);
node.setParent(null);
}
}
public static void main(String[] args) {
BinarySearchTree bst = new BinarySearchTree();
int[] a = {39,27,49,20,38,41,45,48,43};
bst.insert(a);
bst.inOrderTraversalLoop();
bst.delete(49);
bst.inOrderTraversalLoop();
}
}
