二叉排序树
2017-11-17 本文已影响0人
scarerow
二叉排序树百度百科定义
二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。
二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
-
（1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；
-
（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
-
（3）左、右子树也分别为二叉排序树；
百度百科图.png
二叉排序树代码实现
数据结构
public class TreeNode{
int data;
// 左子树（节点）
TreeNode leftChild;
// 右子树（右节点）
TreeNode rightChild;
// 父节点
TreeNode parent;
public TreeNode(int data) {
super();
this.data = data;
this.leftChild = null;
this.rightChild = null;
this.parent = null;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public TreeNode getLeftChild() {
return leftChild;
}
public void setLeftChild(TreeNode leftChild) {
this.leftChild = leftChild;
}
public TreeNode getRightChild() {
return rightChild;
}
public void setRightChild(TreeNode rightChild) {
this.rightChild = rightChild;
}
public TreeNode getParent() {
return parent;
}
public void setParent(TreeNode parent) {
this.parent = parent;
}
}
插入
插入原理：
- 如果根节点为空，插入根节点
- 依次和每个节点比较，大于获取节点右边，小于获取节点左边，直到查到到叶子节点
- 和查找到的叶子节点比较，决定放到左边还是右边
- 插入节点的父节点等于查找到的节点
public TreeNode put(int data) {
//根节点为空，插入根节点
if (root == null) {
TreeNode node = new TreeNode(data);
root = node;
return node;
}
//依次和每个节点比较，大于获取节点右边，小于获取节点左边
// 直到查到到叶子节点
TreeNode parent = null;
TreeNode node = root;
for(; node != null;) {
// parent 作用是记录查找符合要求的叶子节点
parent = node;
if (data < node.data) {
node = node.leftChild;
} else if(data > node.data) {
node = node.rightChild;
} else {
return node;
}
}
// 和查找到的叶子节点比较，决定放到左边还是右边
TreeNode newNode = new TreeNode(data);
if (data < parent.data) {
parent.leftChild = newNode;
} else {
parent.rightChild = newNode;
}
// 有坑
newNode.parent = parent;
return newNode;
}
查找
查找节点的原理
- 判断是否为空树，如果为空，返回null
- 用输入值（data）和节点值（node.data）比较，如果data > node.data，data再与node的右子节点比较，
如果data < node.data,data再与node的左子节点比较 - 如此循环，知道找到node.data = data ，返回node,或者查找到叶子节点还没找到，返回空
public TreeNode searchNode (int data) {
if (root == null) {
return null;
}
TreeNode node = root;
while (node != null) {
if (node.data == data) {
return node;
} else if (node.data < data) {
node = node.rightChild;
} else if(node.data > data) {
node = node.leftChild;
}
}
return null;
}
删除
/**
* 删除一个节点
* @param node
*/
private void delNode(TreeNode node){
if(node == null) {
throw new NoSuchElementException();
} else {
// 一 先找到parent节点
TreeNode parent = node.parent;
//1：没有孩子
if (node.leftChild ==null && node.rightChild ==null) {
if (parent == null) {
//只有一个Root节点，删除掉，树就变成了空树
root = null;
} else if (parent.rightChild == node) {
parent.rightChild = null;
} else if(parent.leftChild == node) {
parent.leftChild = null;
}
node.parent = null;
} else if (node.leftChild != null && node.rightChild == null) {
//2：只有左孩子
if (parent == null) {
// 删除root节点
node.parent = null;
node.leftChild.parent = null;
root = node.leftChild;
} else {
//判断删除的节点是父节点的左节点，还是右节点
if (parent.leftChild == node) {
parent.leftChild = node.leftChild;
} else {
parent.rightChild = node.leftChild;
}
node.parent = null;
}
} else if (node.leftChild == null && node.rightChild != null) {
//3：只有右孩子
if (parent == null) {
// 删除root节点
node.parent = null;
node.rightChild.parent = null;
root = node.rightChild;
} else {
//判断删除的节点是父节点的左节点，还是右节点
if (parent.leftChild == node) {
parent.leftChild = node.rightChild;
} else {
parent.rightChild = node.rightChild;
}
node.parent = null;
}
} else {
/*
* 有左右两个孩子的步骤
* 一 找到右边子树的最小值节点 占用被删除节点的位置
* 二
*
*
* */
//4：有左右两个孩子
// 情况一 ：删除节点的右子树的左子树为空，则把要删除节点的左子树设为删除点的右子树的左子树
if (node.rightChild.leftChild == null) {
node.rightChild.leftChild = node.leftChild;
if (parent == null) {
// 只有一个root节点情况
root = node.rightChild;
} else {
// 判断被删除节点 是左 是右
if (parent.leftChild == node) {
parent.leftChild = node.rightChild;
} else {
parent.rightChild = node.rightChild;
}
}
node.parent = null;
} else {
// 情况二 ： 被删除节点的右节点的左子树不为空
/*
* leftNode ： 删除节点的右子树的最左节点
* node ：被删除的节点
* leftNodeP ：leftNode的父节点
* */
// 1 找到被删除节点的 右子树的最小值节点（这个值最接近被删除节点的值）
TreeNode leftNode = getMinLeftTreeNode(node.rightChild);
// 2 leftNode接收删除节点的左子树
leftNode.leftChild = node.leftChild;
// 3 leftNode的右子树 作为leftNodeP的左子树
TreeNode leftNodeP = leftNode.parent;
leftNodeP.leftChild = leftNode.rightChild;
//4 leftNode的右子树 = node的右子树
leftNode.rightChild = node.rightChild;
// 5 parent 指向新的节点
if (parent == null) {
root = leftNode;
} else {
// 判断删除的节点是父节点的左还是右
if (parent.leftChild == node) {
parent.leftChild = leftNode;
} else {
parent.rightChild = leftNode;
}
}
}
}
}
}
private TreeNode getMinLeftTreeNode(TreeNode node) {
TreeNode curRoot = null;
if (node == null) {
return null;
} else {
curRoot = node;
while(curRoot.leftChild != null) {
curRoot = curRoot.leftChild;
}
}
return curRoot;
}
二叉树bmli
public void midOrderTraverse(TreeNode root) {
if (root == null) {
return;
}
midOrderTraverse(root.leftChild);
System.out.print(root.data + " ");
midOrderTraverse(root.rightChild);
}
public void preOrderTraverse(TreeNode root) {
if (root == null) {
return;
}
System.out.println("pre Order: " + root.data);
preOrderTraverse(root.leftChild);
preOrderTraverse(root.rightChild);
}
public void postOrderTraverse(TreeNode root) {
if (root == null) {
return;
}
preOrderTraverse(root.leftChild);
preOrderTraverse(root.rightChild);
System.out.println("pre Order: " + root.data);
}
