概念:

二叉樹(shù)(Binary Tree)是n(n≥0)個(gè)結(jié)點(diǎn)的有限集合，該集合或者為空集(稱為空二叉樹(shù))，或者由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的笤虫、分別稱為根結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。

image.png

1、二叉樹(shù)類型

1加勤、斜樹(shù)

image.png

2、滿二叉樹(shù)

image.png

3同波、完全二叉樹(shù)

image.png

2鳄梅、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)

1、順序存儲(chǔ)

image.png

2未檩、鏈?zhǔn)酱鎯?chǔ)

image.png

3戴尸、二叉樹(shù)的遍歷

1、前序（DLR）

規(guī)則是若二叉樹(shù)為空冤狡，則空操作返回孙蒙，否則先訪問(wèn)跟結(jié)點(diǎn)，然后前序遍歷左子樹(shù)悲雳，再前序遍歷右子樹(shù)挎峦。

image.png

void ProOrderTraverse(Tree T){
      if(T == null){
          return;
     }
     printf(“%c”,T-data);
     ProOrderTraverse(T->lchild);
     ProOrderTraverse(T->rchild);
}

2、中序(LDR)

規(guī)則是若樹(shù)為空合瓢，則空操作返回坦胶，否則從根結(jié)點(diǎn)開(kāi)始（注意并不是先訪問(wèn)根結(jié)點(diǎn)），中序遍歷根結(jié)點(diǎn)的左子樹(shù)晴楔，然后是訪問(wèn)根結(jié)點(diǎn)顿苇，最后中序遍歷右子樹(shù)

image.png

void ProOrderTraverse(Tree T){
     if(T == null){
      return;
     }
     ProOrderTraverse(T->lchild);
     printf(“%c”,T-data);
     ProOrderTraverse(T->rchild);
}

3、后序（LRD）

規(guī)則是若樹(shù)為空税弃，則空操作返回纪岁，否則從左到右先葉子后結(jié)點(diǎn)的方式遍歷訪問(wèn)左右子樹(shù)，最后是訪問(wèn)根結(jié)點(diǎn)则果。

image.png

void ProOrderTraverse(Tree T){
     if(T == null){
      return;
     }
     ProOrderTraverse(T->lchild);
     ProOrderTraverse(T->rchild);
     printf(“%c”,T-data);
}

public class BinarayTree {
    Node<String> root;
    public BinarayTree(String data){
        root=new Node<>(data,null,null);
    }
    public void createTree(){
        Node<String> nodeB=new Node<String>("B",null,null);
        Node<String> nodeC=new Node<String>("C",null,null);
        Node<String> nodeD=new Node<String>("D",null,null);
        Node<String> nodeE=new Node<String>("E",null,null);
        Node<String> nodeF=new Node<String>("F",null,null);
        Node<String> nodeG=new Node<String>("G",null,null);
        Node<String> nodeH=new Node<String>("H",null,null);
        Node<String> nodeJ=new Node<String>("J",null,null);
        Node<String> nodeI=new Node<String>("I",null,null);
        root.leftChild=nodeB;
        root.rightChild=nodeC;
        nodeB.leftChild=nodeD;
        nodeC.leftChild=nodeE;
        nodeC.rightChild=nodeF;
        nodeD.leftChild=nodeG;
        nodeD.rightChild=nodeH;
        nodeE.rightChild=nodeJ;
        nodeH.leftChild=nodeI;

    }

    /**
     * 中序訪問(wèn)樹(shù)的所有節(jié)點(diǎn)
     */
    public void midOrderTraverse(Node root){//邏輯
        if(root==null){
            return;
        }
        midOrderTraverse(root.leftChild);//邏輯
        System.out.println("mid:"+root.data);//輸出
        midOrderTraverse(root.rightChild);//邏輯
    }
    /**
     * 前序訪問(wèn)樹(shù)的所有節(jié)點(diǎn)  Arrays.sort();
     */
    public void preOrderTraverse(Node root){
        if(root==null){
            return;
        }
        System.out.println("pre:"+root.data);
        preOrderTraverse(root.leftChild);
        preOrderTraverse(root.rightChild);
    }
    /**
     * 后序訪問(wèn)樹(shù)的所有節(jié)點(diǎn)
     */
    public void postOrderTraverse(Node root){
        if(root==null){
            return;
        }
        postOrderTraverse(root.leftChild);
        postOrderTraverse(root.rightChild);
        System.out.println("post:"+root.data);
    }






    /**
     * 節(jié)點(diǎn)
     */
    public class Node<T>{
        T data;
        Node<T> leftChild;
        Node<T> rightChild;

        public Node(T data, Node<T> leftChild, Node<T> rightChild) {
            this.data = data;
            this.leftChild = leftChild;
            this.rightChild = rightChild;
        }
    }

}

public class ExampleUnitTest {
    @Test
    public void addition_isCorrect() throws Exception {
        BinarayTree binarayTree=new BinarayTree("A");
        binarayTree.createTree();
        binarayTree.midOrderTraverse(binarayTree.root);
        binarayTree.preOrderTraverse(binarayTree.root);
        binarayTree.postOrderTraverse(binarayTree.root);
    }
}

打印結(jié)果:

mid:G
mid:D
mid:I
mid:H
mid:B
mid:A
mid:E
mid:J
mid:C
mid:F

pre:A
pre:B
pre:D
pre:G
pre:H
pre:I
pre:C
pre:E
pre:J
pre:F

post:G
post:I
post:H
post:D
post:B
post:J
post:E
post:F
post:C
post:A