遍历 http://blog.csdn.net/baoendemao/article/details/39007627
数组缺点: 增删慢
链表缺点: 查找慢
二叉排序树结合了两者的优点;
二叉排序树 Paste_Image.png二叉排序树的特点:
1、若它的左子树不空, 则左子树上所有结点的值均小于它的根结构的值;
2、若它的右子树不空, 则右子树上所有结点的值均小于它的根结构的值;
3、它的左子树和右子树都是二叉排序树;
关于二叉排序树的增删改查:
二分查找:
public Node find(Node root,Key k){
if (root==null){
return null;
}
if (key==null){
return null;
}
if(key.compareTo(root.key)==0){
return root;
}
if(key.compareTo(root.key)<0){
return find(root.left,key);
}
if(key.compareTo(root.key)>0){
return find(root.right,key);
}
}
最坏情形下二叉排序树的查找时间复杂度为O(n), 即如下图所示的worst case:
二叉排序树的三种情形.png所以实际应用中并不会使用二叉排序树,会使用二叉排序树的几种衍生树;
增删查:
public class BinaryTreeNode{
int mData;
BinaryTreeNode mLeft;
BinaryTreeNode mRight;
BinaryTreeNode mParent;
}
public class BinarySearchTree {
private BinaryTreeNode mRoot;
public BinarySearchTree(BinaryTreeNode root){
mRoot = root;
}
//查找
public BinaryTreeNode search(int data){
return search(mRoot,data);
}
public BinaryTreeNode search(BinaryTreeNode node,int data) {
if (node == null || node.mData == data){
return node;
}
if (data < node.mData){
return search(node.mLeft, data);
} else {
return search(node.mRight, data);
}
}
//插入
public void insert(int data){
if (mRoot == null){
mRoot = new BinaryTreeNode();
mRoot.mData = data;
return;
}
searchAndInsert(null,mRoot,data);
}
private BinaryTreeNode searchAndInsert(BinaryTreeNode parent, BinaryTreeNode node, int data){
if (node == null){
node = new BinaryTreeNode();
node.mData = data;
if (parent != null) {
if (data < parent.mData) {
parent.mLeft = node;
} else {
parent.mRight = node;
}
}
return node;
}
if (data == node.mData){
return node;
} else if (data < node.mData) {
return searchAndInsert(node, node.mLeft, data);
} else if (data > node.mData) {
return searchAndInsert(node, node.mRight, data);
}
}
//删除
/**
* 在整个树中, 查找指定数据节点的父节点;
*/
public BinaryTreeNode searchParent(int data) {
return searchParent(null, mRoot, data);
}
public BinaryTreeNode searchParent(BinaryTreeNode parent, BinaryTreeNode node, int data) {
if (node == null) {
return;
}
if (data == node.mData) {
return parent;
} else if (data < node.mData) {
return searchParent(node, node.mLeft, data);
} else if (data > node.mData) {
return searchParent(node, node.mRight, data);
}
}
/**
* 删除指定数据的节点:
*/
public void delete(int data) {
if (mRoot == null || mRoot.mData == data) {//根节点为空或者要删除的就是根节点, 直接删除掉
mRoot = null;
return;
}
// 在删除之前需要找到他的父节点
// 感觉这行代码有些多余, 如果节点存在, 父节点肯定也是存在的.
BinaryTreeNode parent = searchParent(data);
if (parent == null) {//如果父节点为空, 说明这个树是空树, 没法删;
return;
}
//找到要删除的节点
BinaryTreeNode deleteNode = search(parent, data);
//1.如果该树左右孩子均为空, 说明该节点为叶子节点, 直接删除
if (deleteNode.mLeft == null && deleteNode.mRight == null) {
deleteNode = null;
if (parent.mLeft != null && parent.mLeft.mData == data) {
parent.mLeft = null;
} else if (parent.mRight != null && parent.mRight.mData == data) {
parent.mRight = null;
}
return;
} else if (deleteNode.mLeft != null && deleteNode.mRight == null) {
//2.左孩子不为空, 右孩子为空
parent.mLeft = deleteNode.mLeft;
deleteNode = null;
return;
} else if () {
//3.左孩子为空, 右孩子不为空
parent.mRight = deleteNode.mRight;
deleteNode = null;
return;
} else if () {
//4.左右孩子均不为空
BinaryTreeNode right = parent.mRight;
while (right.mLeft != null) {
right = right.mLeft;
}
deleteNode = right;
parent.mLeft = right;
deleteNode = null;
return;
}
}
}
网友评论