ADT基础（二）—— Tree，Heap and Graph

1 Tree(二叉树)

先根遍历 (若二叉树为空，则退出，否则进行下面操作)
- 访问根节点
- 先根遍历左子树
- 先根遍历右子树
- 退出
访问顺序为：A、B、D、H、I、E、J、C、F、G
中根遍历(若二叉树为空，则退出，否则进行下面操作)
- 中根遍历左子树
- 访问根节点
- 中根遍历右子树
- 退出
访问顺序为：H、D、I、B、J、E、A、F、C、G
后根遍历(若二叉树为空，则退出，否则进行下面操作)
- 后根遍历左子树
- 后根遍历右子树
- 访问根节点
- 退出
访问顺序为：H、I、D、J、E、B、F、G、C、A
广度优先遍历：

访问顺序为：A、B、C、D、E、F、G、H、I、J

//链表表示

public class BinaryNode    //节点类

{

    Object element;

    BinaryNode left; //lefft subtree

    BinaryNode right; //right subtree

};

public class BinaryTree{    //节点树类

    private BinaryNode root;

    public boolean isEmpty(){return root == null;}

    //深度优先遍历，递归,非递归要用栈，而递归本质就是栈

    public void PreOrder(BinaryNode node){  //先根遍历

        if(node!=null){

            System.out.println(node.element);

            PreOrder(node.left);

            PreOrder(node.right);

        }

    }

    public void InOrder(BinaryNode node){  //中根遍历

        if(node!=null){

            InOrder(node.left);

            System.out.println(node.element);

            InOrder(node.right);

        }

    }

    public void PostOrder(BinaryNode node){  //后根遍历

        if(node!=null){

            PostOrder(node.left);

            PostOrder(node.right);

            System.out.println(node.element);

        }

    }

    //广度优先遍历，循环,使用队列

    public void LevelOrder(BinaryNode node){

        Queue q = new Queue();

        while(node){

            System.out.println(node.element);

            if(node.left) q.add(node.left);

            if(node.right) q.add(node.right);

            try{ node = q.delete();}  //弹出值赋给node

            catch(OutOfBounds){return;}

        }

    }

}

//清空

public void clear(BinaryNode node){  //清除某个子树的所有节点

    if(node!=null){

        clear(node.left);

        clear(node.right);

        node = null; //删除节点

    }

}

public void clear(){  ////清空树

    clear(root);

}

//求高度

public int height(BinaryNode node){  //获取以某节点为子树的高度

    if(node==null){

        return 0; //递归结束，空子树高度为0

    }else{

        //递归获取左子树高度

        int l = height(node.left);

        //递归获取右子树高度

        int r = height(node.right);

        //高度应该算更高的一边，（+1是因为要算上自身这一层）

        return l>r? (l+1):(r+1);

    }

}

public int height(){   //获取二叉树的高度

    return height(root);

}

//求节点数

public int size(BinaryNode node){   //获取以某节点为子树的节点数

    if(node==null){

        return 0;

    }else{

        int l = size(node.left);

        int r = size(node.right);

        return l+r+1;

    }

}

public int size(){   //获取二叉树的节点数

    return size(root);

}

//返回某节点的父亲节点,这种二叉树只能递归地靠从根节点遍历来比较获取

public BinaryNode getParent(BinaryNode node,BinaryNode root){

    if(root==null) retun null;

    if(root.left==node||root.right==node) return root;

    if(getParent(root.left,node)!=null) return getParent(root.left,node);

    else return getParent(root.right,node);

}

public BinaryNode getParent(BinaryTreeNode node){

    return (root==null||root==node)? null:getParent(root,node);

}

//已知前序和中序，重新构造二叉树

//核心：找到根节点，分开左右子树

//前序第一个就是根节点，以该点把中序分成左右两部分，左未左子树，右为右子树；同样，左右两部分，同上，递归

public void createBT(String pres,String ins,BinaryNode root){

    int inpos;

    String prestmp,instmp;

    if(pres.length==0) root = null;

    else{

        root = new BinaryNode();

        root.element = pres.charAt(0);

        inpos = 0;

        while(ins.charAt(inpos) != root.element) inpos++;  //找到中序的树根

        prestmp = pres.substring(1,inpos+1);

        instmp = ins.substring(0,inpos);  //左子树

        createBT(pres,ins,t.left);  //递归构造左子树

        prestmp = pres.substring(inpos+1,pres.length()-1);

        instmp = ins.substring(inpos+1,prs.length()-1);  //左子树

        createBT(pres,ins,t.right);  //递归构造左子树

    }

}

//已知后序与中序。算法同，相当于后序反过来找

//已知先序和后序，可以得到不唯一的树。核心：找到树根，分开左右子树

/*

先序遍历中刚遍历到的下一个节点是后序遍历中最后遍历的节点，所以可以将后序遍历拆分成两个子序列，从而进行递归构造。

例如 先序遍历为aebdc，后序遍历为bcdea。

首先可以确定根节点为a，在后序中找先序的下一个节点（也就是e),将原序列拆分成两部分，其左子树包含的元素有bcde，右子树为空。

接着在bcd中寻找先序中e的后一个元素即b的位置，将这个子序列又拆分成了b和cd两部分。如此递归下去就能得到一种可能的二叉树。

*/

2 Tree(二叉搜索树)

//查找

private BinaryNode find( Comparable x, BinaryNode t ){

    if( t = = null ) return null;

    if( x. compareTo( t.element ) < 0 ) return find( x, t.left );

    else if( x.compareTo( t.element ) > 0 ) return find( x, t.right );

    else return t; //Match

}

private BinaryNode findMin( BinaryNode t ){

    if( t = = null ) return null;

    else if( t.left = = null ) return t;

    return findMin(t.left);

}

//递归或循环都可

private BinaryNode findMax( BinaryNode t ){

    if( t != null )

    	while( t.right != null )

    		t = t.right;

    return t;

}

//插入

private BinaryNode insert( Comparable x, BinaryNode t )

{

    if( t == null )

        t = new BinaryNode( x, null, null );

    else if( x.compareTo( t.element ) < 0 )

        t.left = insert( x, t.left );

    else if( x.compareTo( t.element ) > 0 )

        t.right = insert( x, t.right );

    else ;//duplicate; do nothing

    return t;

}

//删除

//三种情况：叶，只有一个非空子树的节点，有两个非空子树的节点

//用左子树的最大或右子树的最小(都是叶节点)来换，然后把左子树最大和右子树最小删除

private BinaryNode remove( Comparable x, BinaryNode t){

    if( t == null ) return t;

    if( x.compareTo( t.element ) < 0 )

        t.left = remove( x, t.left );

    else if( x.compareTo( t.element ) > 0 )

        t.right = remove( x, t.right );

    else if( t.left != null && t.right != null ){  //找到了

        t.element = findMin( t.right ).element;  //左子树max或右子树min

        t.right = remove(t.element, t.right );

    }else  //左右子树一边为空或全为空，可以替换成左子树或右子树

        t = ( t.left != null ) ? t.left : t.right;

}

巴特西

ADT基础（二）—— Tree，Heap and Graph

ADT基础（二）—— Tree，Heap and Graph

1 Tree(二叉树)

2 Tree(二叉搜索树)

最新文章

热门文章