二叉树(数据结构及算法08)

概念:

二叉树(Binary Tree)是n(n≥0)个结点的有限集合，该集合或者为空集(称为空二叉树)，或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

image.png

1、二叉树类型

1、斜树

image.png

2、满二叉树

image.png

3、完全二叉树

image.png

2、二叉树的存储结构

1、顺序存储

image.png

2、链式存储

image.png

3、二叉树的遍历

1、前序（DLR）

规则是若二叉树为空，则空操作返回，否则先访问跟结点，然后前序遍历左子树，再前序遍历右子树。

image.png

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

2、中序(LDR)

规则是若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树

image.png

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

3、后序（LRD）

规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。

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;

    }

    /**
     * 中序访问树的所有节点
     */
    public void midOrderTraverse(Node root){//逻辑
        if(root==null){
            return;
        }
        midOrderTraverse(root.leftChild);//逻辑
        System.out.println("mid:"+root.data);//输出
        midOrderTraverse(root.rightChild);//逻辑
    }
    /**
     * 前序访问树的所有节点  Arrays.sort();
     */
    public void preOrderTraverse(Node root){
        if(root==null){
            return;
        }
        System.out.println("pre:"+root.data);
        preOrderTraverse(root.leftChild);
        preOrderTraverse(root.rightChild);
    }
    /**
     * 后序访问树的所有节点
     */
    public void postOrderTraverse(Node root){
        if(root==null){
            return;
        }
        postOrderTraverse(root.leftChild);
        postOrderTraverse(root.rightChild);
        System.out.println("post:"+root.data);
    }






    /**
     * 节点
     */
    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);
    }
}

打印结果:

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