美文网首页
树_01二叉树增删改查遍历

树_01二叉树增删改查遍历

作者: 冉桓彬 | 来源:发表于2017-04-18 20:26 被阅读158次

    遍历 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;
            }
        }
    }
    

    相关文章

      网友评论

          本文标题:树_01二叉树增删改查遍历

          本文链接:https://www.haomeiwen.com/subject/pveqzttx.html