關(guān)于樹的基本概念可以查看此篇文章樹鳖枕、堆、集合

1桨螺、一般樹的實現(xiàn)：

樹結(jié)構(gòu)可以由遞歸實現(xiàn)宾符，也可以由鏈表實現(xiàn)：
鏈表實現(xiàn)的單個節(jié)點的表示方法：

class TreeNode{
    Object element;  //節(jié)點的值
    TreeNode firstChild; //該節(jié)點的第一個子節(jié)點
    TreeNode nextSibling; //下一個兄弟節(jié)點
}

樹的遍歷：分為前序遍歷、后續(xù)遍歷灭翔，二叉樹還有一種特殊的遍歷方法（中序遍歷）魏烫；
前序遍歷：及對節(jié)點的處理，先于其子節(jié)點進行肝箱，其時間復雜度為O(n);
后序遍歷：及對節(jié)點的處理哄褒，晚于其子節(jié)點進行，其時間復雜度為O(n);
[圖片上傳失敗...(image-754579-1509972359621)]

前序遍歷為：A-B-D-#-#-#-C-E-#-#-#

后序遍歷為：#-#-D-#-B-#-#-E-#-C-A

2煌张、二叉樹的實現(xiàn)：

二叉樹是一顆樹呐赡，其每個節(jié)點都不能有多于兩個的兒子；

其單個節(jié)點為：

    private static class BinaryNode<T>{
        T element;
        BinaryNode<T> leftBinaryNode;
        BinaryNode<T> rightBinaryNode;
        
        BinaryNode(T element){
            this.element=element;
        }

        public BinaryNode(T element, BinaryNode<T> leftBinaryNode, BinaryNode<T> rightBinaryNode) {
            this.element = element;
            this.leftBinaryNode = leftBinaryNode;
            this.rightBinaryNode = rightBinaryNode;
        }
        
    }

二叉搜索樹的實現(xiàn)：

package tree;

import com.sun.jmx.remote.internal.ArrayQueue;

import java.nio.BufferUnderflowException;
import java.util.Queue;

public class myBinaryTree<T extends Comparable<? super T>> {
    private BinaryNode<T> root;
    public myBinaryTree(){
        root=null;
    }
    public boolean isEmpty(){
        return root==null;
    }
    public void makeEmpty(){
        root=null;
    }
    public boolean contains(T item){
        return contains(item,root);
    }

    private boolean contains(T item,BinaryNode<T> t){
        if(t==null){
            return false;
        }
        int compareValue=item.compareTo(t.element);
        if(compareValue<0){
            return contains(item,t.leftBinaryNode);
        }
        else if(compareValue>0){
            return contains(item,t.rightBinaryNode);
        }
        else {
            return true;
        }
    }


    public T findMin(){
        if(isEmpty())
            throw new BufferUnderflowException();
        return findMin(root).element;
    }
    private BinaryNode<T> findMin(BinaryNode<T> t){
        if(t==null){
            return null;
        }
        while (t.leftBinaryNode!=null){
            t=t.leftBinaryNode;
        }
        return t;
    }


    public T findMax(){
        if(isEmpty())
            throw new BufferUnderflowException();
        return findMax(root).element;
    }
    private BinaryNode<T> findMax(BinaryNode<T> t){
        if(t==null){
            return null;
        }
        while (t.rightBinaryNode!=null){
            t=t.rightBinaryNode;
        }
        return t;
    }

    public void insert(T item){
        root=insert(item,root);
    }
    private BinaryNode<T> insert(T item,BinaryNode<T> t){
        if(t==null){
            return new BinaryNode<T>(item,null,null);
        }
        int compareValue=item.compareTo(t.element);
        if(compareValue<0){
            t.leftBinaryNode=insert(item,t.leftBinaryNode);
        }
        else if(compareValue>0){
            t.rightBinaryNode=insert(item,t.rightBinaryNode);
        }
        else{
            ;
        }

        return t;
    }

    public int height(){
        if(isEmpty()){
            return 0;
        }
        else
            return height(root);
    }
    private int height(BinaryNode<T> t){
        if(t==null){
            return 0;
        }
        else
            return 1+Math.max(height(t.rightBinaryNode),height(t.leftBinaryNode));
    }


    public void printTreeNodeLast(){ //后序遍歷
        if(isEmpty()){
            System.out.println("Tree is empty");
        }
        else {
            printTreeNodeLast(root);
        }
    }
    private void printTreeNodeLast(BinaryNode<T> t){
        if (t!=null){
            printTreeNodeLast(t.leftBinaryNode);
            printTreeNodeLast(t.rightBinaryNode);
            System.out.println(t.element);
        }
    }


    public void printTreeNodeFirst(){ //先序遍歷
        if(isEmpty()){
            System.out.println("Tree is empty");
        }
        else {
            printTreeNodeFirst(root);
        }
    }
    private void printTreeNodeFirst(BinaryNode<T> t){
        if (t!=null){
            System.out.println(t.element);
            printTreeNodeFirst(t.leftBinaryNode);
            printTreeNodeFirst(t.rightBinaryNode);
        }
    }

    public void printTreeNodeMedu(){ //中序遍歷
        if(isEmpty()){
            System.out.println("Tree is empty");
        }
        else {
            printTreeNodeMedu(root);
        }
    }
    private void printTreeNodeMedu(BinaryNode<T> t){
        if (t!=null){
            printTreeNodeMedu(t.leftBinaryNode);
            System.out.print(t.element);
            printTreeNodeMedu(t.rightBinaryNode);
        }
    }

    public void printTree(){ //層序遍歷
        if(isEmpty()){
            System.out.println("Tree is empty");
        }
        else {
            printTree(root);
        }
    }
    private void printTree(BinaryNode<T> t){
        ArrayQueue<BinaryNode<T>> arrayQueue=new ArrayQueue<>(height());
        if(t==null){
            System.out.println("Tree is empty");
        }
        arrayQueue.add(t);
        while (!arrayQueue.isEmpty()){
            BinaryNode<T> binaryNode=arrayQueue.remove(0);
            System.out.println(binaryNode.element);
            if(binaryNode.leftBinaryNode!=null){
                arrayQueue.add(binaryNode.leftBinaryNode);
            }
            if(binaryNode.rightBinaryNode!=null){
                arrayQueue.add(binaryNode.rightBinaryNode);
            }
        }
    }

    public void remove(T item){
        root=remove(item,root);
    }
    private BinaryNode<T> remove(T item,BinaryNode<T> t){
       if(t==null){
           return null;
       }
       int comparaValue=item.compareTo(t.element);
       if(comparaValue>0){
           t.rightBinaryNode=remove(item,t.rightBinaryNode);
       }
       else if(comparaValue<0) {
           t.leftBinaryNode=remove(item,t.leftBinaryNode);
       }
       else {
           if(t.rightBinaryNode!=null&&t.leftBinaryNode!=null){
               t.element=findMin(t.rightBinaryNode).element;
               t.rightBinaryNode=remove(t.element,t.rightBinaryNode);
           }
           else {
               t=(t.leftBinaryNode!=null)?t.leftBinaryNode:t.rightBinaryNode;
           }
       }
        return t;
    }

    private static class BinaryNode<T>{
        T element;
        BinaryNode<T> leftBinaryNode;
        BinaryNode<T> rightBinaryNode;

        BinaryNode(T element){
            this.element=element;
        }

        public BinaryNode(T element, BinaryNode<T> leftBinaryNode, BinaryNode<T> rightBinaryNode) {
            this.element = element;
            this.leftBinaryNode = leftBinaryNode;
            this.rightBinaryNode = rightBinaryNode;
        }

    }
}

3骏融、AVL樹
帶有自平衡調(diào)整的二叉查找樹链嘀，其要求每個節(jié)點的左右子節(jié)點的高度差萌狂，相差不超過1；

package tree;

import com.sun.org.apache.xerces.internal.impl.xpath.regex.Match;

import java.nio.BufferUnderflowException;

public class myAvlTree<T extends Comparable<? super T>> {
    private static final int ALLOWED_HEIGHT=1;
    private AvlNode<T> root;

    public myAvlTree(){
        root=null;
    }

    public boolean isEmpty(){
        return root==null;
    }
    public void insert(T item){
        root=insert(item,root);
    }


    public T findMin(){
        if(isEmpty())
            throw new BufferUnderflowException();
        return findMin(root).element;
    }
    private AvlNode<T> findMin(AvlNode<T> t){
        if(t==null){
            return null;
        }
        while (t.left!=null){
            t=t.left;
        }
        return t;
    }
    private AvlNode<T> insert(T item,AvlNode<T> t){
        if(t==null){
            return new AvlNode<T>(item,null,null);
        }
        int comparaValue=item.compareTo(t.element);
        if(comparaValue>0){
            t.right=insert(item,t.right);
        }
        else if(comparaValue<0){
            t.left=insert(item,t.left);
        }
        else
            ;
        return balance(t);
    }

    public void remove(T x){
        if(isEmpty()){
            System.out.println("tree is empty");
            throw new BufferUnderflowException();
        }
        remove(x,root);
    }
    private AvlNode<T> remove(T x,AvlNode<T> t){
        if(t==null){
            return null;
        }
        int comparaVaule=x.compareTo(t.element);
        if(comparaVaule>0){
            t.right=remove(x,t.right);
        }
        else if(comparaVaule<0){
            t.left=remove(x,t.left);
        }
        else if(t.left!=null&&t.right!=null){
            t.element=findMin(t.right).element;
            t.right=remove(t.element,t.left);
        }
        else {
            t=(t.left!=null)?t.left:t.right;
        }
        return t;
    }
    private AvlNode<T> balance(AvlNode<T> t){
        if(t==null){
            return t;
        }
        if(height(t.left)-height(t.right)>ALLOWED_HEIGHT){
            if(height(t.left.left)>=height(t.left.right)){
                t=rotateWithLeftChild(t);
            }
            else{
                t=doubleWithLeftChild(t);
            }
        }
        else if(height(t.right)-height(t.left)>ALLOWED_HEIGHT){
            if(height(t.right.right)>=height(t.right.left)){
                t=rotateWithRightChild(t);
            }
            else {
                t=doubleWithRightChild(t);
            }
        }
        t.height=Math.max(height(t.left),height(t.right))+1;
        return t;
    }
    private AvlNode<T> rotateWithLeftChild(AvlNode<T> k2){
        AvlNode<T> 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;
    }
    private AvlNode<T> doubleWithLeftChild(AvlNode<T> k2){
        k2.left=rotateWithRightChild(k2.left);
        return rotateWithLeftChild(k2);
    }
    private AvlNode<T> rotateWithRightChild(AvlNode<T> k1){
        AvlNode<T> k2=k1.right;
        k1.right=k2.left;
        k2.left=k1;
        k1.height=Math.max(height(k1.right),k1.height);
        k2.height=Math.max(k1.height,height(k2.right))+1;
        return k2;
    }
    private AvlNode<T> doubleWithRightChild(AvlNode<T> k2){
        k2.right=rotateWithLeftChild(k2.left);
        return rotateWithRightChild(k2);
    }


    private int height(AvlNode<T> t){ //計算AVL樹的高度怀泊；
        return t==null?-1:t.height;
    }

    public void printTree(){ //后序遍歷
        if(isEmpty()){
            System.out.println("Tree is empty");
        }
        else {
            printTree(root);
        }
    }
    private void printTree(AvlNode<T> t){
        if (t!=null){
            printTree(t.left);
            printTree(t.right);
            System.out.println(t.element);
        }
    }

    public void printTreelast(){ //先序遍歷
        if(isEmpty()){
            System.out.println("Tree is empty");
        }
        else {
            printTreelast(root);
        }
    }
    private void printTreelast(AvlNode<T> t){
        if (t!=null){
            System.out.println(t.element);
            printTreelast(t.left);
            printTreelast(t.right);

        }
    }


    public void printTreemd(){ //中序遍歷
        if(isEmpty()){
            System.out.println("Tree is empty");
        }
        else {
            printTreemd(root);
        }
    }
    private void printTreemd(AvlNode<T> t){
        if (t!=null){
            printTreemd(t.left);
            System.out.println(t.element);
            printTreemd(t.right);

        }
    }

    private static class AvlNode<T>{
        T element;
        AvlNode<T> left;
        AvlNode<T> right;
        int height; //height
        AvlNode(T element){
            this.element=element;
        }
        public AvlNode(T element, AvlNode<T> left, AvlNode<T> right) {
            this.element = element;
            this.left = left;
            this.right = right;
            height=0;
        }

    }
}


 public static void main(String[] args){
        myAvlTree<Integer> myAvlTree=new myAvlTree<>();
        Integer[] integer={10,3,5,9,8,7,0,4};
        for(Integer ints:integer){
            myAvlTree.insert(ints);
        }
        System.out.println("中序");
        myAvlTree.printTreemd();
    }
    
    
中序
0
3
4
5
7
8
9
10