原创文章，转载请注明原文章地址，谢谢！
二叉树
二叉树是树的特殊一种，具有如下特点：每个结点最多有两颗子树，结点的度最大为2。左子树和右子树是有顺序的，次序不能颠倒。即使某结点只有一个子树，也要区分左右子树。
斜二叉树
所有的结点都只有左子树，或者只有右子树。
满二叉树
所有的分支结点都存在左子树和右子树，并且所有的叶子结点都在同一层上。
- 满二叉树的特点
非叶子节点的度为2；叶子节点在最下层；在相同深度的二叉树中，满二叉树的节点个数最多，叶子节点数最多。
完全二叉树
若设二叉树的深度为k，除第k层外，其他各层（1～（k-1）层）的节点数都达到最大值，且第k层所有的节点都连续集中在最左边，这样的树就是完全二叉树。
模拟二叉树的实现
public class MyNode {
int data; //节点数据
MyNode leftChild; //左子节点的引用
MyNode rightChild; //右子节点的引用
boolean isDelete;//表示节点是否被删除
public MyNode(int data) {
this.data = data;
}
//打印节点内容
public void display() {
System.out.println(data);
}
}
public interface MyTree {
//查找节点
public MyNode find(int key);
//插入新节点
public boolean insert(int data);
//中序遍历
public void infixOrder(MyNode current);
//前序遍历
public void preOrder(MyNode current);
//后序遍历
public void postOrder(MyNode current);
//查找最大值
public MyNode findMax();
//查找最小值
public MyNode findMin();
//删除节点
public boolean delete(int key);
//Other Method......
}
public class BinaryTree implements MyTree {
//表示根节点
private MyNode root;
//查找节点
public MyNode find(int key) {
MyNode current = root;
while (current != null) {
if (current.data > key) {//当前值比查找值大，搜索左子树
current = current.leftChild;
} else if (current.data < key) {//当前值比查找值小，搜索右子树
current = current.rightChild;
} else {
return current;
}
}
return null;//遍历完整个树没找到，返回null
}
//插入节点
public boolean insert(int data) {
MyNode newMyNode = new MyNode(data);
if (root == null) {//当前树为空树，没有任何节点
root = newMyNode;
return true;
} else {
MyNode current = root;
MyNode parentMyNode = null;
while (current != null) {
parentMyNode = current;
if (current.data > data) {//当前值比插入值大，搜索左子节点
current = current.leftChild;
if (current == null) {//左子节点为空，直接将新值插入到该节点
parentMyNode.leftChild = newMyNode;
return true;
}
} else {
current = current.rightChild;
if (current == null) {//右子节点为空，直接将新值插入到该节点
parentMyNode.rightChild = newMyNode;
return true;
}
}
}
}
return false;
}
//中序遍历
public void infixOrder(MyNode current) {
if (current != null) {
infixOrder(current.leftChild);
System.out.print(current.data + " ");
infixOrder(current.rightChild);
}
}
//前序遍历
public void preOrder(MyNode current) {
if (current != null) {
System.out.print(current.data + " ");
infixOrder(current.leftChild);
infixOrder(current.rightChild);
}
}
//后序遍历
public void postOrder(MyNode current) {
if (current != null) {
infixOrder(current.leftChild);
infixOrder(current.rightChild);
System.out.print(current.data + " ");
}
}
//找到最大值
public MyNode findMax() {
MyNode current = root;
MyNode maxMyNode = current;
while (current != null) {
maxMyNode = current;
current = current.rightChild;
}
return maxMyNode;
}
//找到最小值
public MyNode findMin() {
MyNode current = root;
MyNode minMyNode = current;
while (current != null) {
minMyNode = current;
current = current.leftChild;
}
return minMyNode;
}
@Override
public boolean delete(int key) {
MyNode current = root;
MyNode parent = root;
boolean isLeftChild = false;
//查找删除值，找不到直接返回false
while (current.data != key) {
parent = current;
if (current.data > key) {
isLeftChild = true;
current = current.leftChild;
} else {
isLeftChild = false;
current = current.rightChild;
}
if (current == null) {
return false;
}
}
//如果当前节点没有子节点
if (current.leftChild == null && current.rightChild == null) {
if (current == root) {
root = null;
} else if (isLeftChild) {
parent.leftChild = null;
} else {
parent.rightChild = null;
}
return true;
//当前节点有一个子节点，右子节点
} else if (current.leftChild == null && current.rightChild != null) {
if (current == root) {
root = current.rightChild;
} else if (isLeftChild) {
parent.leftChild = current.rightChild;
} else {
parent.rightChild = current.rightChild;
}
return true;
//当前节点有一个子节点，左子节点
} else if (current.leftChild != null && current.rightChild == null) {
if (current == root) {
root = current.leftChild;
} else if (isLeftChild) {
parent.leftChild = current.leftChild;
} else {
parent.rightChild = current.leftChild;
}
return true;
} else {
//当前节点存在两个子节点
MyNode successor = getSuccessor(current);
if (current == root) {
root = successor;
} else if (isLeftChild) {
parent.leftChild = successor;
} else {
parent.rightChild = successor;
}
successor.leftChild = current.leftChild;
}
return false;
}
public MyNode getSuccessor(MyNode delMyNode) {
MyNode successorParent = delMyNode;
MyNode successor = delMyNode;
MyNode current = delMyNode.rightChild;
while (current != null) {
successorParent = successor;
successor = current;
current = current.leftChild;
}
//后继节点不是删除节点的右子节点，将后继节点替换删除节点
if (successor != delMyNode.rightChild) {
successorParent.leftChild = successor.rightChild;
successor.rightChild = delMyNode.rightChild;
}
return successor;
}
}
博客内容仅供自已学习以及学习过程的记录，如有侵权，请联系我删除，谢谢！
网友评论