二叉树

二叉树的概念

二叉树是一种非线性的数据结构，它是由n个有限结点组成的一个具有层次结构的关系集合。
它有一个特殊的结点，称为根节点，根节点没有前驱节点。如同一颗倒挂的数。树是递归定
义的。

二叉树的各部分概念

节点的度： 一个结点含有的子树的个数称为该节点的度。
树的度： 一棵树中，最大的结点的度称为树的度。
叶子结点或终端结点： 度为0的结点称为叶子节点。
双亲结点： 若叶个结点含有子节点，则这个节点称为该子节点的父亲结点。
孩子结点或子节点： 一个节点含有的子树的根结点称为该节点的子节点。
根节点： 一棵树中，没有双亲节点的结点。
结点的层次： 从根节开始定义起，根为第一层，根的子节点为第二层，以此类推。
树的高度或深度： 树中结点的最大层次。
兄弟结点： 具有相同父亲节点的互称为兄弟节点。
结点的祖先： 从根到该节点所经分支上的所有节点。

二叉树的性质

特点： 1.每个结点最对有两颗子树，即二叉树不存在度大于2的结点。
? ? ? ? ? ? 2.二叉树的子树有左右之分，其子树的次序不能颠倒，因此二叉树是有序? ? ? ? ? ? ? ? ? ? 树。

特殊的二叉树

1.满二叉树： 一个二叉树，如果每一层的节点数都达到了最大值，则这个二叉树就是满二叉树。即：层数为K；节点数为2^k-1,则为满二叉树。
2.完全而二叉树： 完全二叉树的每个节点的相邻结点都不为空。最后一层的最后后一个结点的右相邻无结点。

二叉树的性质

1.根节点为1，则非空而二叉树的第i层最多有2ⁱ-1个结点；层数为K，则二叉树的最大结点树为2^k-1；如果叶子结点为N，度为2的非叶子结点个数为D，则有N=D+1.
2.n个节点的完全二叉树的深度为log₂(n + 1)的值向上取整。
3.对于有n个节点的完全二叉树，按照从上到下，从左到右的顺序从0开始编号，则有：
?????????若i > 0 ，双亲序号：(i - 1) / 2 ; i = 0为根节点，无双亲结点。
?????????若2i+1<n,左孩子序号为2i+1，否则无左孩子。
?????????若2i+1>n,右孩子序号为2i+1，否则无右孩子。

二叉树的遍历方式

import java.util.*;
class Node{
    public char value;
    public Node left;
    public Node right;
    public Node(char value){
        this.value = value;
    }
}
public class Tree {
    //先序遍历（递归） 
    public void preOrderTraversal(Node root){
        if(root == null){
            return ;
        }
        //先序遍历：根，左，右。
        System.out.print(root.value + " ");
        preOrderTraversal(root.left);
        preOrderTraversal(root.right);
    }
    //先序遍历（非递归）
    public void PrevOrderTraversal(Node root) {
        if (root == null) {
            return;
        }
        Stack<Node> stack = new Stack<>();
        Node cur = root;
        while (cur != null || !stack.empty()) {
            while (cur != null) {
                stack.push(cur);
                System.out.print(cur.value + " ");
                cur = cur.left;
            }
            Node top = stack.pop();
            cur = top.right;
        }
        System.out.println();
    }
    //中序遍历（递归）
    public void inOrderTraversal(Node root){
        if(root == null){
            return ;
        }
        inOrderTraversal(root.left);
        System.out.print(root.value + " ");
        inOrderTraversal(root.right);
    }
    //中序遍历（非递归）
    public void InOrderTraversal(Node root) {
        if (root == null) {
            return;
        }
        Stack<Node> stack = new Stack<>();
        Node cur = root;
        while (cur != null || !stack.empty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            Node top = stack.pop();
            System.out.print(top.value + " ");
            cur = top.right;
        }
        System.out.println();
    }
    //后序遍历（递归）
    public void postOrderTraversal(Node root){
        if(root == null){
            return ;
        }
        postOrderTraversal(root.left);
        postOrderTraversal(root.right);
        System.out.print(root.value + " ");
    }
    //后序遍历（非递归）
    public void PostOrderTraversal(Node root) {
        if (root == null) {
            return;
        }
        Stack<Node> stack = new Stack<>();

        Node cur = root;
        Node prev = null;
        while (cur != null || !stack.empty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.peek();
            if (cur.right == null || cur.right == prev) {
                stack.pop();
                System.out.print(cur.value + " ");
                prev = cur;
                cur = null;
            } else {
                cur = cur.right;
            }
        }
        System.out.println();
    }
    //层序遍历
    public void levelOrderTraversal(Node root){
        if(root == null){
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            Node cur = queue.poll();
            System.out.println(cur + " ");
            if(cur.left != null){
                queue.offer(cur.left);
            }
            if(cur.right != null){
                queue.offer(cur.right);
            }
        }
    }
}