[数据结构与算法]二叉树的前序遍历

二叉树：每个子节点最多只能有两个节点

子节点分为左节点和右节点

满二叉树：n:层数，所有叶子节点都在最后一层，节点数为2^n-1

完全二叉树：所有的叶子节点在最后一层或者倒数第二层

最后一层叶子结点在左边连续，倒数第二层叶子结点在右边连续

?

?这是二叉树的前序遍历

其他两个长得差不多

怎么判断是什么遍历呢？？？

根节点在最前面就是前序遍历

根节点在最后面就是后序遍历

根节点在中间就是中序遍历?

节点类

class Node{
    public int no;
    public String name;
    public Node left;
    public Node right;
    public Node(int no,String name){
        this.no = no;
        this.name = name;
    }
    @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();
        }
    }
}

二叉树类

class BinaryTree{
    public Node root;
    public BinaryTree(Node root){
        this.root = root;
    }
    public void preOrder(){
        if(this.root!=null){
            this.root.preOrder();
        }
    }
}

测试类

public class BinaryTreeTest {
    public static void main(String[] args) {
        Node node1 = new Node(1,"a1");
        Node node2 = new Node(2,"a2");
        Node node3 = new Node(3,"a3");
        Node node4 = new Node(4,"a4");
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        BinaryTree binaryTree = new BinaryTree(node1);
        binaryTree.preOrder();
    }
}

输出

一定要记得写toString

要不然结果就是 地址

?

?