Error message here!

Hide Error message here!

Error message here!

Hide Error message here!

Error message here!

Close

# 数据结构之二叉树解析

Kevin.ZhangCG 2019-01-21 09:23:00 阅读数:229 评论数:0 点赞数:0 收藏数:0

……

• 该节点是叶节点，没有子节点

• 该节点有一个子节点

• 该节点有两个子节点

• 把后继父节点的leftChild字段置为后继的右子节点；

• 把后继的rightChild字段置为要删除节点的右子节点；

• 把待删除节点从它父节点的leftChild或rightChild字段删除，把这个字段置为后继；

• 把待删除的左子节点移除，将后继的leftChild字段置为待删除节点的左子节点。

```public class BNode {
public int key;
public double data;
public BNode parent;
public BNode leftChild;
public BNode rightChild;
public void displayNode() {
System.out.println("{" + key + ":" + data + "}");
}
}```
```public class BinaryTree {
private BNode root; // 根节点
public BinaryTree(BNode root) {
root = null;
}
//二搜索树查找的时间复杂度为O（logN）
//find node with given key
public BNode find(int key) {
BNode current = root;
while (current.key != key) {
if (key < current.key) {
current = current.leftChild;
} else {
current = current.rightChild;
}
if (current == null) {
return null;
}
}
return current;
}
//插入节点
public void inset(int key, int value) {
BNode newNode = new BNode();
newNode.key = key;
newNode.data = value;
if (root == null) {
root = newNode;
} else {
BNode current = root;
BNode parent;
while (true) {
parent = current;
if (key < current.key) {
//turn left
current = current.leftChild;
if (current == null) {
parent.leftChild = newNode;
newNode.parent = parent;
return;
}
} else {
//trun right
current = current.rightChild;
if (current == null) {
parent.rightChild = newNode;
newNode.parent = parent;
return;
}
}
}
}
}
//遍历二叉树
public void traverse(int traverseType) {
switch (traverseType) {
case 1:
System.out.println("PreOrder Traversal!");
preOrder(root);
break;
case 2:
System.out.println("InOrder Traversal!");
inOrder(root);
break;
case 3:
System.out.println("PostOrder Traversal");
postOrder(root);
default:
System.out.println("PreOrder Traversal!");
preOrder(root);
break;
}
System.out.println("");
}
//前序遍历
public void preOrder(BNode localRoot) {
if (localRoot != null) {
System.out.println(localRoot.data + " ");
preOrder(localRoot.leftChild);
preOrder(localRoot.rightChild);
}
}
//中序遍历
public void inOrder(BNode localRoot) {
if (localRoot != null) {
inOrder(localRoot.leftChild);
System.out.println(localRoot.data + " ");
inOrder(localRoot.rightChild);
}
}
//后序遍历
public void postOrder(BNode localRoot) {
if (localRoot != null) {
postOrder(localRoot.leftChild);
postOrder(localRoot.rightChild);
System.out.println(localRoot.data + " ");
}
}
//查找最小值
/*根据二叉搜索树存储规则：最小值应该是左边那个没有子节点的那个节点*/
public BNode minNumber() {
BNode current = root;
BNode parent = root;
while (current != null) {
parent = current;
current = current.leftChild;
}
return parent;
}
//查找最大值
/*根据二叉搜索树的存储规则：最大值应该是右边那个没有子节点的那个节点*/
public BNode maxNumber() {
BNode current = root;
BNode parent = root;
while (current != null) {
parent = current;
current = current.rightChild;
}
return parent;
}
//删除节点
/*

1、该节点没有子节点（简单）
2、该节点有一个子节点（还行）
3、该节点有两个子节点（复杂）

*/
public boolean delete(int key) {
BNode current = root;
boolean isLeftChild = true;
if (current == null) {
return false;
}
//寻找要删除的节点
while (current.data != key) {
if (key < current.data) {
isLeftChild = true;
current = current.leftChild;
} else {
isLeftChild = false;
current = current.rightChild;
}
if (current == null) {
return false;
}
}
//找到了要删除的节点，下面开始删除
//1、要删除的节点没有子节点，直接将其父节点的左子节点或者右子节点赋为null即可
if (current.leftChild == null && current.rightChild == null) {
return false;
}
//3、要删除的节点有两个子节点
else if (current.leftChild != null && current.rightChild != null) {
return false;
}
//2、要删除的节点有一个子节点，直接将其砍断，将其子节点与其父节点连接起来即可，要考虑特殊情况就是删除根节点，因为根节点没有父节点
else {
return false;
}
}
public boolean deleteNoChild(BNode node, boolean isLeftChild) {
if (node == root) {
root = null;
return true;
}
if (isLeftChild) {
node.parent.leftChild = null;
} else {
node.parent.rightChild = null;
}
return true;
}
public boolean deleteOneChild(BNode node, boolean isLeftChild) {
if (node.leftChild == null) {
if (node == root) {
root = node.rightChild;
node.parent = null;
return true;
}
if (isLeftChild) {
node.parent.leftChild = node.rightChild;
} else {
node.parent.rightChild = node.rightChild;
}
} else {
if (node == root) {
root = node.leftChild;
node.parent = null;
return true;
}
if (isLeftChild) {
node.parent.leftChild = node.leftChild;
} else {
node.parent.rightChild = node.rightChild;
}
}
return true;
}
public boolean deleteTwoChild(BNode node, boolean isLeftChild) {
BNode successor = getSuccessor(node);
if (node == root) {
successor.leftChild = root.leftChild;
successor.rightChild = root.rightChild;
successor.parent = null;
root = successor;
} else if (isLeftChild) {
node.parent.leftChild = successor;
} else {
node.parent.rightChild = successor;
}
//connect successor to node's left child
successor.leftChild = node.leftChild;
return true;
}
//获得要删除节点的后继节点（中序遍历的下一个节点）
public BNode getSuccessor(BNode delNode) {
BNode successor = delNode;
BNode current = delNode.rightChild;
while (current != null) {
successor = current;
current = current.leftChild;
}
if (successor != delNode.rightChild) {
(successor).leftChild = successor.rightChild;
if (successor.rightChild != null) {
//删除后续节点在原来的位置
successor.rightChild.parent = successor.parent;
}
//将后续节点放到正确的位置，与右边连上
successor.rightChild = delNode.rightChild;
}
return successor;
}
}```

https://www.cnblogs.com/Kevin-ZhangCG/p/10286444.html

30万现金开奖等你来领