二叉樹的鍊式結構周遊

所謂周遊(Traversal)就是指沿着某條搜尋路線,依次對樹中每個結點均做一次且僅做一次通路,通路結點所做的操作依賴于具體的問題應用,如下圖是一顆二叉樹,紅色路線位周遊路線

 二叉樹的周遊按照通路結點的順序分為:

前序周遊(PreOrder Traversal):先通路根結點,再通路左右子樹

中序周遊(InOrder Traversal):先通路左子樹,然後是根結點,其次是右子樹

後序周遊(PostOrder Traversal):先通路左子樹,然後是右子樹,最後是根結點

除了前中後序外還可以對二叉樹進行層序周遊,層序周遊就是設根結點所在的一層為第一層,首先通路第一層,然後依次從左到右通路第二層上的結點,接着是第三層上的結點,以此類推,自上而下,自左至右逐層通路樹的結點的過程就是層序周遊.周遊路線如圖所示

 前序周遊:

/**
     * 前序周遊
     * @param root
     */

    private static void preOrderTraversal(Node root){
       if(root != null){
           //根 左子樹的前序周遊 右子樹的前序周遊
           System.out.print(root.value + " ");

           preOrderTraversal(root.left);
           preOrderTraversal(root.right);
       }
    }
           

中序周遊:

/**
     * 中序周遊
     * @param root
     */

    private static void inOrderTraversal(Node root){
        if(root != null){
            //左子樹的中序周遊 根 右子樹的中序周遊
            inOrderTraversal(root.left);
            System.out.print(root.value+" ");
            inOrderTraversal(root.right);
        }
    }
           

後序周遊:

/**
     * 後序周遊
     * @return
     */

    private static void postOrderTraversal(Node root){
        if(root != null){
            //左子樹的後序周遊 右子樹的後序周遊 根
            postOrderTraversal(root.left);
            postOrderTraversal(root.right);
            System.out.print(root.value +" ");
        }
    }
           

求二叉樹的結點個數:

/**
     * 求二叉樹節點個數
     */
    private static int count=0;
    //用前序周遊求二叉樹的節點個數
    private static void countByTraversal(Node root){
        if(root != null){
            count++;
            countByTraversal(root.left);
            countByTraversal(root.right);
        }
    }
           

求二叉樹中國葉子結點個數:

/**
     * 求二叉樹葉子節點個數
     * @param root
     * @return
     */
    private static int leafCount(Node root){
        //葉子節點個數
        if(root == null){
            return 0;
        }else if(root.left == null && root.right == null){
            return 1;
        }else{
            return leafCount(root.left)+leafCount(root.right);
        }
    }
           

求二叉樹的高度:

/**
     * 求二叉樹的高度
     * @param root
     * @return
     */
    private static int height(Node root){
        //空樹
        //其他  max(left,right)+1;
        if(root == null){
            return 0;
        }else{
            int left = height(root.left);
            int right = height(root.right);
            return (left>right ? left:right)+1;
        }
    }
           

求二叉樹第k層的結點個數:

/**
     * 求k層節點個數
     * @param root
     * @param k
     * @return
     */
    private static int kLevel(Node root,int k){
        if(root == null){
            return 0;
        }else if(k == 1){
            return 1;
        }else{
            return kLevel(root.left,k-1)+kLevel(root.right,k-1);
        }
    }
           

在二叉樹中查找元素:

/**
     * 在二叉樹中查找元素
     * @param root
     * @param v
     * @return
     */
    private static Node find(Node root,char v){
        if(root == null){
            return null;
        }
        if(root.value == v){
            return root;
        }
        Node r = find(root.left,v);
        if(r != null){
            return r;
        }
        r=find(root.right,v);
        if(r != null){
            return r;
        }
        return null;
    }