树，二叉树，前中后序遍历-java

树示意图

树的常用术语(结合示意图理解):

结点 ： 结点是数据结构中的基础，是构成复杂数据结构的基本组成单位。

根结点 ：没有父节点的结点称为根节点

父结点 ： ：若一个结点含有子结点，则这个结点称为其子结点的父结点；

子结点 ：

叶子结点 ：没有子结点的结点

结点 的权(节点值)

结点的度： 一个结点含有的子结点的个数称为该结点的度

路径(从root节点找到该结点 的路线)

层 ： 根结点的层次为1，其余结点的层次等于该结点的双亲结点的层次加1

树的高度(最大层数) ： 树中结点的最大层次

森林 :多颗子树构成森林

二叉树

定义： 每个结点至多拥有两棵子树(即二叉树中不存在度大于2的结点)，并且，二叉树的子树有左右之分，其次序不能任意颠倒。

二叉树的性质

性质1：二叉树第i层上的结点数目最多为2i-1(i>=1)

性质2：深度为k的二叉树至多有2k-1个结点（k>=1）

性质3：包含n个结点的二叉树的高度至少为(log2n)+1

性质4：在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1

满二叉树

定义：高度为h，并且由2h-1个结点组成的二叉树，称为满二叉树

完全二叉树

完全二叉树从根结点到倒数第二层满足完美二叉树，最后一层可以不完全填充，其叶子结点都靠左对齐。

二叉树的遍历

前序遍历: 先输出父节点，再遍历左子树和右子树

这棵树的前序遍历为：ABDEGHCF

中序遍历: 先遍历左子树，再输出父节点，再遍历右子树

这棵树的中序遍历为：DBGEHACF

后序遍历: 先遍历左子树，再遍历右子树，最后输出父节点

这棵树的后序遍历为：DGHEBFCA

小结: 看输出父节点的顺序，就确定是前序，中序还是后序

层次遍历：按层次遍历

这棵树的层次遍历为：ABCDEFGH

利用递归实现遍历

以图中为例

package tree;

/**
 * @author: xingt   [email protected]
 * @date: 2019/11/2, 19:32
 * @version: 1.0
 */
public class BinaryTreeDemo {
    public static void main(String[] args) {
        //创建一颗二叉树
        BinaryTree binaryTree = new BinaryTree();
        //创建节点
        Node root = new Node(1,"a");
        Node node2 = new Node(2,"b");
        Node node3 = new Node(3,"c");
        Node node4 = new Node(4,"d");
        Node node5 = new Node(5,"e");
        Node node6 = new Node(6,"f");
        //设置节点
        root.setLeft(node2);
        root.setRight(node3);
        node3.setLeft(node4);
        node3.setRight(node5);
        node4.setLeft(node6);

        binaryTree.setRoot(root);

        System.out.println("前序遍历");
        binaryTree.preOrder();

        System.out.println("中序遍历");
        binaryTree.infixOrder();

        System.out.println("后序遍历");
        binaryTree.postOrder();

    }





}

class BinaryTree{
    private Node root;

    public void setRoot(Node root) {
        this.root = root;
    }

    //前序遍历
    public void preOrder(){
        if(this.root !=null){
            this.root.preOrder();
        }else{
            System.out.printf("二叉树为空，无法遍历");
        }
    }

    //前序遍历
    public void infixOrder(){
        if(this.root !=null){
            this.root.infixOrder();
        }else{
            System.out.printf("二叉树为空，无法遍历");
        }
    }

    //前序遍历
    public void postOrder(){
        if(this.root !=null){
            this.root.postOrder();
        }else{
            System.out.printf("二叉树为空，无法遍历");
        }
    }
}


class Node{
    private int no;
    private String name;
    private Node left;
    private Node right;
    public Node(int no, String name){
        //super();
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

    //前序遍历
    public void preOrder(){
        //先输出父节点
        System.out.println(this);
        //递归向左子树前序遍历
        if(this.left != null){
            this.left.preOrder();
        }
        //递归向右子树前序遍历
        if(this.right != null){
            this.right.preOrder();
        }

    }
    //中序遍历
    public void infixOrder(){
        //递归向左子树遍历
        if(this.left != null){
            this.left.infixOrder();
        }
        //输出父节点
        System.out.println(this);
        //递归向右子树遍历
        if(this.right != null){
            this.right.infixOrder();
        }
    }


    //后续遍历
    public void postOrder(){
        //递归向左子树遍历
        if(this.left != null){
            this.left.postOrder();
        }
        //递归向右子树遍历
        if(this.right != null){
            this.right.postOrder();
        }
        //输出父节点
        System.out.println(this);
    }
}

//输出结果
前序遍历
Node{no=1, name='a'}
Node{no=2, name='b'}
Node{no=3, name='c'}
Node{no=4, name='d'}
Node{no=6, name='f'}
Node{no=5, name='e'}
中序遍历
Node{no=2, name='b'}
Node{no=1, name='a'}
Node{no=6, name='f'}
Node{no=4, name='d'}
Node{no=3, name='c'}
Node{no=5, name='e'}
后序遍历
Node{no=2, name='b'}
Node{no=6, name='f'}
Node{no=4, name='d'}
Node{no=5, name='e'}
Node{no=3, name='c'}
Node{no=1, name='a'}