【数据结构】树

1.基础知识

1.1 树的定义1.2树的实现 2. 二叉树

2.1 二叉树的实现2.2 表达式树 3. 二叉查找树4. 二叉平衡树（AVL树）

树(tree)可以用几种方式定义。定义树的一种自然的方式是递归的方式。一棵树是一些节点的集合。这个集合可以是空集;若不是空集，则树由称作根( root )的节点 r r r以及0个或多个非空的(子)树 T 1 T_1 T1​, T 2 T_2 T2​,…, T k T_k Tk​,组成，这些子树中每一棵的根都被来自根r的一条有向的边（edge）所连结。

对任意节点 n i n_i ni​， n i n_i ni​的深度( depth)为从根到 n i n_i ni​的唯一的路径的长。因此，根的深度为0。 n i n_i ni​的高（height）是从 n i n_i ni​到一片树叶的最长路径的长。因此所有的树叶的高都是0。一棵树的高等于它的根的高。一棵树的深度等于它的最深的树叶的深度；该深度总是等于这棵树的高。

第一儿子/下一兄弟表示法

class TreeNode{
	Object element;
	TreeNode firstchild;
	TreeNode nextsibling;
}

二叉树是一棵树，其中每个结点的子结点都不能多余两个。

class BinaryNode{
	Object element;
	BinaryNode left;
	BinaryNode right;
}

(后续更新)

二叉查找树的性质是，对于树中的每个节点X，它的左子树中所有项的值小于X中的项，而它的右子树中所有项的值大于X中的项。

package dataStructure.tree;

import java.nio.BufferUnderflowException;
// 继承了Comparable，为了在下面方便使用compareTo方法
public class BinarySearchTree> {
	// 二叉树结点定义
    private static class BinaryNode{
        BinaryNode(AnyType theElement){
            this(theElement,null,null);
        }
        BinaryNode(AnyType theElement,BinaryNode lt,BinaryNode rt){
            element=theElement;
            left=lt;
            right=rt;
        }
        AnyType element;
        BinaryNode left;
        BinaryNode right;
    }
    private BinaryNode root; // 二叉树根节点

    // 初始化，根节点设为null
    public BinarySearchTree(){
        root=null;
    }
    // 置空，根节点置为null
    public void makeEmpty(){
        root=null;
    }
    // 判空，判断根节点是否等于null
    public boolean isEmpty(){
        return root==null;
    }
    // 判断该二叉搜索树中是否包含x
    public boolean contains(AnyType x){
        return contains(x,root);
    }
    // 找到二叉搜索树的最小值
    public AnyType findMin(){
        if(isEmpty()) throw new BufferUnderflowException();
        return findMin(root).element;
    }
    // 找到二叉搜索树的最大值
    public AnyType findMax(){
        if(isEmpty()) throw new BufferUnderflowException();
        return findMax(root).element;
    }
    // 打印该二叉树
    public void printTree(){
        if(isEmpty())
            System.out.println("Empty tree");
        else
            printTree(root);
    }
    // 判断二叉树t中是否包含x
    private boolean contains(AnyType x,BinaryNode t){
        if(t==null) return false;
        int compareResult =x.compareTo(t.element);
        if(compareResult<0)
            return contains(x,t.left);
        else if(compareResult>0)
            return contains(x,t.right);
        else
            return true;
    }
    // 查找最小值的递归实现
    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){
        // 在这个方法体内，t只是root的拷贝，t所指向的内容不断被改变，
        // 但root指向的内容从未改变，因为root从未被传进来。
        if(t!=null)
            while(t.right!=null)
                t=t.right;
        return t;
    }
    // 插入元素
    private BinaryNode insert(AnyType x,BinaryNode t){
        if(t==null)
            return new BinaryNode<>(x,null,null);
        int compareResult=x.compareTo(t.element);
        if(compareResult<0)
            t.left=insert(x,t.left);
        else if(compareResult>0)
            t.right=insert(x,t.right);
        else
            ;  //这代表插入元素与树中某一元素相等
        return t;
    }
    // 删除元素
    private BinaryNode remove(AnyType x,BinaryNode t){
        if(t==null)
            return t;
        int compareResult=x.compareTo(t.element);
        if(compareResult<0)
            t.left=remove(x,t.left);
        else if(compareResult>0)
            t.right=remove(x,t.right);
        else if(t.left!=null && t.right!=null){
            // 如果t只有左右子树，在右子树中找到最小元素，填入当前结点，
            // 然后在右子树中删除该最小元素
            t.element=findMin(t.right).element;
            t.right=remove(t.element,t.right);
        }
        else
            // 如果t只有左子树，执行赋值操作t=t.left即可
            // 如果t只有右子树，执行赋值操作t=t.right即可
            // 如果t没有子树，说明t为叶结点，直接删掉即可。t=null
            t=(t.left!=null) ? t.left : t.right;
        return t;
    }
    // 打印二叉树t
    private void printTree(BinaryNode t){
        // 根-左-右：先序遍历
        if(t!=null){
            printTree(t.left);
            System.out.println(t.element);
            printTree(t.right);
        }
    }
}

一棵AVL树是其每个节点的左子树和右子树的高度最多差1的二叉查找树（或者空树）。
AVL树每次插入/删除结点后，都必须重新平衡，以保持AVL树独有的特性。

import java.nio.BufferUnderflowException;
// AvlTree class
//
// CONSTRUCTION: with no initializer
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x )       --> Insert x
// void remove( x )       --> Remove x (unimplemented)
// boolean contains( x )  --> Return true if x is present
// boolean remove( x )    --> Return true if x was present
// Comparable findMin( )  --> Return smallest item
// Comparable findMax( )  --> Return largest item
// boolean isEmpty( )     --> Return true if empty; else false
// void makeEmpty( )      --> Remove all items
// void printTree( )      --> Print tree in sorted order
// ******************ERRORS********************************
// Throws BufferUnderflowException as appropriate


public class AvlTree> {
    
    private static class AvlNode {  // 子类：AVL树结点
        AvlNode( AnyType theElement )  {
            this( theElement, null, null );
        }
        AvlNode( AnyType theElement, AvlNode lt, AvlNode rt ) {
            element  = theElement;
            left     = lt;
            right    = rt;
            height   = 0;
        }
        AnyType           element;      // The data in the node
        AvlNode  left;         // Left child
        AvlNode  right;        // Right child
        int               height;       // Height
    }
    private AvlNode root; // 根节点

    
    // AVL树的构造方法
    public AvlTree( ) {
        root = null;
    }
    // 向树中插入x，如果树中已有相同的x，则新的插入的x会被忽略
    public void insert( AnyType x ) {
        root = insert( x, root );
    }
    // 从树中删除x，如果x没被找到，那就什么也不做
    public void remove( AnyType x ) {
        root = remove( x, root );
    }

    // 找到树的最小元素；如果树空，则返回null
    public AnyType findMin( ) {
        if( isEmpty( ) )
            throw new BufferUnderflowException( );
        return findMin( root ).element;
    }
    // 找到树的最大元素；如果树空，则返回null
    public AnyType findMax( ) {
        if( isEmpty( ) )
            throw new BufferUnderflowException( );
        return findMax( root ).element;
    }
    // 判断树中是否包含x
    public boolean contains( AnyType x ) {
        return contains( x, root );
    }
    // 将树置空
    public void makeEmpty( ) {
        root = null;
    }
    // 判空
    public boolean isEmpty( ) {
        return root == null;
    }
    // 检查root是否平衡
    public void checkBalance( ) {
        checkBalance( root );
    }
    // 按序打印树的每一个元素
    public void printTree( ) {
        if( isEmpty( ) )
            System.out.println( "Empty tree" );
        else
            printTree( root );
    }

    
    // 不平衡高度的阈值为1；AVL树中任何一个结点的左右子树高度差都不能大于1
    private static final int ALLOWED_IMBALANCE = 1;
    // t此时刚被插入或删除元素，尚未确定是否平衡，需要执行balance操作
    // 这里假设t为从叶结点向上查询，首次出现不平衡的结点
    private AvlNode balance( AvlNode t ) {
        if( t == null )  // 如果树为空，则不需要平衡
            return t;
        // 如果t的左子树比右子树高
        if( height( t.left ) - height( t.right ) > ALLOWED_IMBALANCE )
            if( height( t.left.left ) >= height( t.left.right ) )
                t = rotateWithLeftChild( t ); // 单次左旋转（适用于插入左儿子的左子树）
            else
                t = doubleWithLeftChild( t ); // 双次左-右旋转（适用于插入左儿子的右子树）
        // 如果t的右子树比左子树高
        else if( height( t.right ) - height( t.left ) > ALLOWED_IMBALANCE )
            if( height( t.right.right ) >= height( t.right.left ) )
                t = rotateWithRightChild( t ); // 单次右旋转（适用于插入右儿子的右子树）
            else
                t = doubleWithRightChild( t ); // 双次右-左旋转（适用于插入右儿子的左子树）
        // 重新计算t的高度
        t.height = Math.max( height( t.left ), height( t.right ) ) + 1;
        return t;
    }
    // 检查root是否平衡
    private int checkBalance( AvlNode t ) {
        if( t == null )
            return -1;
        else {
            int hl = checkBalance( t.left );
            int hr = checkBalance( t.right );
            
            if( Math.abs( height( t.left ) - height( t.right ) ) > 1 ||
                    height( t.left ) != hl || height( t.right ) != hr )
                System.out.println( "OOPS!!" ); // 树不平衡
        }
        return height( t );
    }
    // 向子树t中插入x，并返回这个子树新的根节点
    private AvlNode insert( AnyType x, AvlNode t ) {
        if( t == null )
            return new AvlNode<>( x, null, null );
        int compareResult = x.compareTo( t.element );
        if( compareResult < 0 )
            t.left = insert( x, t.left );
        else if( compareResult > 0 )
            t.right = insert( x, t.right );
        else
            ;  // Duplicate; do nothing
        return balance( t );
    }
    // 从一个子树t中删除x，并返回这个子树新的根节点
    private AvlNode remove( AnyType x, AvlNode t ) {
        if( t == null )
            return t;   // Item not found; do nothing
        int compareResult = x.compareTo( t.element );
        if( compareResult < 0 )
            t.left = remove( x, t.left );
        else if( compareResult > 0 )
            t.right = remove( x, t.right );
        else if( t.left != null && t.right != null ){ // Two children
            // 如果删除结点处有两个子树，则在右子树中找到最小元素，放在当前树的根节点，
            // 右子树递归实现删除这个被提出来的最小元素；左子树不需要改变
            t.element = findMin( t.right ).element;
            t.right = remove( t.element, t.right );
        }
        else
            // 如果t有左子树，没有右子树，将t的左子树替代当前结点，
            // 如果t没有左子树，有右子树，将t的右子树替代当前结点，
            // 左右子树都无，则t=null
            t = ( t.left != null ) ? t.left : t.right;
        return balance( t ); // AVL树在删除元素后必须实现balance操作
    }
    // 找到树的最小元素；如果树空，则返回null（私有方法）
    private AvlNode findMin( AvlNode t ) {
        if( t == null )
            return t;
        while( t.left != null )
            t = t.left;
        return t;
    }
    // 找到树的最大元素；如果树空，则返回null（私有方法）
    private AvlNode findMax( AvlNode t ) {
        if( t == null )
            return t;
        while( t.right != null )
            t = t.right;
        return t;
    }
    // 判断树t中是否包含x（私有方法）
    private boolean contains( AnyType x, AvlNode t ) {
        while( t != null ) {
            int compareResult = x.compareTo( t.element );
            if( compareResult < 0 )
                t = t.left;
            else if( compareResult > 0 )
                t = t.right;
            else
                return true;    // Match
        }
        return false;   // No match
    }
    // 按序打印树的每一个元素（私有方法）
    private void printTree( AvlNode t ) {
        // 左-根-右：中序遍历
        if( t != null ) {
            printTree( t.left );
            System.out.println( t.element );
            printTree( t.right );
        }
    }
    // 计算树的高度
    private int height( AvlNode t ) {
        return t == null ? -1 : t.height;
    }
    // 单次左旋转（左儿子左子树）；k2是从下往上首个不平衡结点
    private AvlNode rotateWithLeftChild( AvlNode k2 ) {
        AvlNode k1 = k2.left;
        k2.left = k1.right;
        k1.right = k2;
        k2.height = Math.max( height( k2.left ), height( k2.right ) ) + 1;
        k1.height = Math.max( height( k1.left ), k2.height ) + 1;
        return k1;
    }
    // 单次右旋转（右儿子右子树）；k1是从下往上首个不平衡结点
    private AvlNode rotateWithRightChild( AvlNode k1 ) {
        AvlNode k2 = k1.right;
        k1.right = k2.left;
        k2.left = k1;
        k1.height = Math.max( height( k1.left ), height( k1.right ) ) + 1;
        k2.height = Math.max( height( k2.right ), k1.height ) + 1;
        return k2;
    }
    // 双次左-右旋转（适用于插入左儿子的右子树）（先单右，再单左）
    // k3是从下往上首个不平衡结点
    private AvlNode doubleWithLeftChild( AvlNode k3 ) {
        k3.left = rotateWithRightChild( k3.left );
        return rotateWithLeftChild( k3 );
    }
    // 双次右-左旋转（适用于插入右儿子的左子树）（先单左，再单右）
    // k1是从下往上首个不平衡结点
    private AvlNode doubleWithRightChild( AvlNode k1 )  {
        k1.right = rotateWithLeftChild( k1.right );
        return rotateWithRightChild( k1 );
    }

    
    public static void main( String[] args ) {
        AvlTree t = new AvlTree<>( ); // 创建一棵空的AVL树
        final int SMALL = 20;
        final int NUMS = 100;  // must be even
        final int GAP  =   11;

        System.out.println( "Checking... (no more output means success)" );

        for( int i = GAP; i != 0; i = ( i + GAP ) % NUMS ) {
//            System.out.println( "INSERT: " + i );
            t.insert( i );
            if( NUMS < SMALL )
                t.checkBalance( );
        }

        for( int i = 1; i < NUMS; i+= 2 )  {
//            System.out.println( "REMOVE: " + i );
            t.remove( i );
            if( NUMS < SMALL )
                t.checkBalance( );
        }

        if( NUMS < SMALL ) // 这代表发生了某些意料之外的事情
            t.printTree( );
        if( t.findMin( ) != 2 || t.findMax( ) != NUMS - 2 )
            System.out.println( "FindMin or FindMax error!" );

        // t中包含2-NUMS之间的所有偶数，如果有一个偶数不被包含，输出错误信息
        for( int i = 2; i < NUMS; i+=2 )
            if( !t.contains( i ) )
                System.out.println( "Find error1!" );
        // t中不包含2-NUMS之间的所有奇数，如果有一个奇数被包含，输出错误信息
        for( int i = 1; i < NUMS; i+=2 ) {
            if( t.contains( i ) )
                System.out.println( "Find error2!" );
        }
    }
}

（持续更新中~）