从零开始学数据结构和算法(六)二叉排序树

818 阅读2分钟

简介

  • 概念

    或者是一颗空树,或者是一颗具有如下性质的树:

    1. 若左子树不为空,那么左子树上面的所有节点的关键字值都比根节点的关键字值小
    2. 若右子树不为空,那么右子树上面的所有节点的关键字值都比根节点的关键字值大
    3. 左右子树都为二叉树
    4. 没有重复值(这一点在实际中可以忽略)

    1551003940.jpg

主要操作

  • 添加节点

1551004090.jpg

  • 查询节点

  • 删除节点

    1. 节点是叶子

      1551004188.jpg

    2. 只有左孩子

      1551004223.jpg

    3. 只有右孩子

      1551004269.jpg

    4. 左右孩子都有

      1551004293.jpg

  • 遍历

    用二叉树的中序

树,森林,二叉树的转换

树转换为二叉树

  • 概念

    1551004402.jpg

  • 图解

    1551004461.jpg

森林转换为二叉树

  • 概念

    wa.png

  • 图解

    wawa.png

二叉树转换为树

  • 概念

    1551004606.jpg

  • 图解

    1551004659.jpg

二叉树转换为森林

  • 概念

    1551004700.jpg

  • 图解

    1551004742.jpg

代码示例

public class SearchBinaryTree {
    //根节点
    public TreeNode root;
/**
 * 添加节点
 */
public TreeNode put(int data){
    if(root==null){
        TreeNode node=new TreeNode(data);
        root=node;
        return node;
    }
    TreeNode parent=null;
    TreeNode node=root;
    //找到要放入的位置
    while(node!=null){
        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;
}
    /**
     * 中序遍历
     */
    public void midOrderTraverse(TreeNode root){
        if(root==null){
            return;
        }
        //LDR
        midOrderTraverse(root.leftChild);
        System.out.print(root.data+" ");
        midOrderTraverse(root.rightChild);
    }
    
    /**
     * 查找一个节点
     */
    public TreeNode searchNode(int data){
        if(root==null){
            return null;
        }
        TreeNode node=root;
        while(node!=null){
            if(node.data==data){
                return node;
            }else if(data>node.data){
                node=node.rightChild;
            }else if(data<node.data){
                node=node.leftChild;
            }
        }
        return null;
    }

    /**
     * 删除节点
     * 要删除的节点在树上是一定存在的才删除
     */
    public void delNode(TreeNode node){
        if(node==null){
            throw new NoSuchElementException();
        }else{
            //先得到父亲,方便后面的操作
            TreeNode parent=node.parent;
            //1.叶子
            if(node.leftChild==null && node.rightChild==null){
                //特别的情况:1.树上只有一个节点或是空树
                if(parent==null){
                    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){//如果要删除的是根
                    node.parent=null;
                    node.leftChild.parent=null;
                    root=node.leftChild;
                }else{
                    if(parent.leftChild==node){//要删除的节点是父亲的左边
                        node.leftChild.parent=parent;
                        parent.leftChild=node.leftChild;
    
                    }else{//要删除的节点是父亲的右边
                        node.leftChild.parent=parent;
                        parent.rightChild=node.leftChild;
                    }
                    node.parent=null;
                }
    
            }else if(node.leftChild==null && node.rightChild!=null){
                //3.只有右孩子
                if(parent==null){//如果要删除的是根
                    node.parent=null;
                    node.rightChild.parent=null;
                    root=node.rightChild;
                }else{
                    if(parent.leftChild==node){//要删除的节点是父亲的左边
                        node.rightChild.parent=parent;
                        parent.leftChild=node.rightChild;
                    }else{//要删除的节点是父亲的右边
                        node.rightChild.parent=parent;
                        parent.rightChild=node.rightChild;
                    }
                    node.parent=null;
                }
            }else{//4。有左右两个孩子
                if(node.rightChild.leftChild==null){//1.如果被删除节点的右子树的左子树为空,就直接补上右子树
                    node.rightChild.leftChild=node.leftChild;
                    if(parent==null){
                        root=node.rightChild;
                    }else{
                        if(parent.leftChild==node){
                            parent.leftChild=node.rightChild;
                            //
                        }else{
                            parent.rightChild=node.rightChild;
                            //
                        }
                    }
                    node.parent=null;
                }else{//2.否则就要补上右子树的左子树上最小的一个
                    TreeNode leftNode=getMinLeftTreeNode(node.rightChild);
                    //1
                    leftNode.leftChild=node.leftChild;
                    //2
                    TreeNode leftNodeP=leftNode.parent;
                    leftNodeP.leftChild=leftNode.rightChild;
                    //3
                    leftNode.rightChild=node.rightChild;
                    //4
                    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;
    }

    public static class TreeNode{
        int  data;
        TreeNode leftChild;
        TreeNode rightChild;
        TreeNode parent;
        public TreeNode(int data){
            this.data=data;
            this.leftChild=null;
            this.rightChild=null;
            this.parent=null;
        }
    }
}
  public class ExampleUnitTest {
    @Test
    public void addition_isCorrect() throws Exception {
        SearchBinaryTree tree=new SearchBinaryTree();
        //5  2  7  3  4  1  6
        int[] array=new int[]{5,2,7,3,4,1,6}; 
   for (int i : array) {
        tree.put(i);
    }
    tree.midOrderTraverse(tree.root);

    for(int i=0;i<array.length-1;i++){
        SearchBinaryTree.TreeNode node=tree.searchNode(array[i]);
        tree.delNode(node);
    }

    System.out.println("----");
    tree.midOrderTraverse(tree.root);
    //        System.out.println(node.data);