統計樹的葉子節點 非葉子節點 兩個孩子節點 單個孩子節點 樹的高度

@Data
@NoArgsConstructor
@AllArgsConstructor
public class BiTree {
    private BiTree lChild, rChild;
    private int data;

    //先序周遊
    public static void PreOrder(BiTree tree) {
        BiTree[] stack = new BiTree[MAX];
        int top = -1;
        stack[++top] = tree;
        while (top != -1) {
            BiTree p = stack[top--];
            while (p != null) {
                print(p);
                if (p.rChild != null) {
                    stack[++top] = p.rChild;
                }
                p = p.lChild;
            }
        }
    }

    //中序周遊
    public static void InOrder(BiTree tree) {
        BiTree[] stack = new BiTree[MAX];
        int top = -1;
        BiTree p = tree;
        while (p != null || top != -1) {
            if (p != null) {
                stack[++top] = p;
                p = p.lChild;
            } else {
                p = stack[top--];
                print(p);
                p = p.rChild;
            }
        }
    }


    static class SNode {
        int flag = 0; //用來記錄該節點是否輸出 0表示未輸出 1表示已經輸出
        BiTree p;

        public SNode(BiTree p) {
            this.p = p;
        }
    }

    //後序周遊
    public static void PostOrder(BiTree tree) {
        SNode[] stack = new SNode[MAX];
        int top = -1;
        BiTree p = tree;
        while (p != null || top != -1) {
            while (p != null) {
                SNode node = new SNode(p);
                stack[++top] = node;
                p = p.lChild;
            }
            SNode node = stack[top--];
            if (node.flag == 0) {
                node.flag = 1;
                stack[++top] = node;
                p = node.p.rChild;
            } else {
                print(node.p);
            }
        }
    }


    //層級周遊
    public static void LevelOrder(BiTree tree) {
        BiTree[] queue = new BiTree[MAX];
        int front = 0, rear = 0;
        queue[rear++] = tree;
        while (front < rear) {
            BiTree p = queue[front++];
            print(p);
            if (p.lChild != null)
                queue[rear++] = p.lChild;
            if (p.rChild != null)
                queue[rear++] = p.rChild;
        }
    }
    //統計葉子節點(遞歸)
    public static int leafCount(BiTree tree) {
        int count = 0;
        if (tree == null) {
            return count;
        } else if (tree.lChild == null && tree.rChild == null) {
            count = 1;
        } else {
            count = leafCount(tree.lChild) + leafCount(tree.rChild);
        }
        return count;
    }

    //統計非葉子節點(遞歸)
    public static int noLeafCount(BiTree tree) {
        int count = 0;
        if (tree == null) {
            return count;
        } else if (tree.lChild != null || tree.rChild != null) {
            count = 1;
            if (tree.lChild != null)
                count += noLeafCount(tree.lChild);
            if (tree.rChild != null)
                count += noLeafCount(tree.rChild);
        }
        return count;
    }

    //統計各種節點(非遞歸)
    public static int LeafCount(BiTree tree) {
        if (tree == null)
            return 0;
        int count = 0;
        int top = -1;
        BiTree[] stack = new BiTree[MAX];
        stack[++top] = tree;
        while (top != -1) {
            BiTree p = stack[top--];
            //if(p.lChild!=null || p.rChild!=null)//統計非葉子節點
            //if(p.lChild!=null && p.rChild!=null)//統計有兩個孩子的節點
            //if ((p.lChild != null && p.rChild == null) || (p.lChild == null && p.rChild != null)) //統計隻有一個孩子的節點
            if (p.lChild == null && p.rChild == null)//統計葉子節點
                count++;
            if (p.lChild != null)
                stack[++top] = p.lChild;
            if (p.rChild != null)
                stack[++top] = p.rChild;
        }
        return count;
    }

    //統計二叉樹的高度
    public static int TreeHigh(BiTree tree) {
        int leftHigh, rightHigh, maxHigh;
        if (tree == null) {
            return 0;
        } else {
            leftHigh = TreeHigh(tree.lChild);
            rightHigh = TreeHigh(tree.rChild);
            maxHigh = leftHigh > rightHigh ? leftHigh : rightHigh;
            return maxHigh + 1;
        }
    }

    public static int treeHigh(BiTree tree) {
        BiTree[] queue = new BiTree[MAX];
        int front = 0, rear = 0;
        queue[rear++] = tree;
        int level = 1, high = 0;
        while (front < rear) {
            BiTree p = queue[front++];
            if (p.lChild != null)
                queue[rear++] = p.lChild;
            if (p.rChild != null)
                queue[rear++] = p.rChild;
            if (front == level) {
                high++;
                level = rear;
            }
        }
        return high;
    }
    //統計二叉樹的寬度


    //判斷二叉樹的是否是完全二叉樹


    private static int MAX = 10;

    public static void main(String[] args) {
        BiTree biTree = init();
        PreOrder(biTree);
        System.out.println();
        InOrder(biTree);
        System.out.println();
        PostOrder(biTree);
        System.out.println();
        LevelOrder(biTree);
        System.out.println();
        System.out.println("葉子節點個數: " + leafCount(biTree));
        System.out.println("非葉子節點個數: " + noLeafCount(biTree));
        System.out.println("葉子節點個數: " + LeafCount(biTree));
        System.out.println("遞歸樹的高度: " + TreeHigh(biTree));
        System.out.println("非遞歸樹的高度: " + treeHigh(biTree));

    }

    private static void print(BiTree p) {
        System.out.print(p.data + " ");
    }

    public BiTree(int data) {
        this.data = data;
    }

    private static BiTree init() {
        BiTree biTree = new BiTree();
        biTree.setData(1);
        BiTree tow = new BiTree(2);
        BiTree three = new BiTree(3);
        BiTree four = new BiTree(4);
        BiTree five = new BiTree(5);
        BiTree six = new BiTree(6);
        BiTree seven = new BiTree(7);
        biTree.setLChild(tow);
        biTree.setRChild(three);
        tow.setLChild(four);
        tow.setRChild(five);
        three.setLChild(six);
        three.setRChild(seven);
        return biTree;
    }
}