二叉树

二叉树（Binary Tree）是n(n>=0)个结点的有限集合或者为空集合（称为空二叉树），或者由一个根结点和两颗互不相交的， 分为二叉树。
二叉树的种类：

image.png

斜树

image.png
满二叉树
image.png
完全二叉树

二叉树的存储结构

二叉树的存储结构分为顺序存储和链式存储：

image.png

顺序存储

image.png

链式存储

二叉树遍历

二叉树的遍历分为 前序、中序、后序

前序遍历

image.png

规则是若二叉树为空，返回为空，否则先遍历跟结点，然后遍历左树结点，再遍历右树结点

中序遍历

image.png

规则是若树为空，则空操作返回， 否则从根结点开始中序遍历根结点的左子树，然后再访问根结点， 最后再返回中序遍历的右节点

后序遍历

image.png

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

代码如下

    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;
            }
        }

    }