Java實(shí)現(xiàn)二叉樹(shù)的基本操作詳解

更新時(shí)間：2022年10月21日 09:16:29 作者：心榮～

這篇文章主要為大家詳細(xì)介紹了Java數(shù)據(jù)結(jié)構(gòu)與算法中二叉樹(shù)的基本操作，文中的示例代碼講解詳細(xì)，具有一定的學(xué)習(xí)價(jià)值，感興趣的小伙伴可以了解一下

1. 二叉樹(shù)結(jié)點(diǎn)的構(gòu)成

這里采用的是孩子表示法, 所以節(jié)點(diǎn)類(使用的是靜態(tài)內(nèi)部類)中除了數(shù)值域外要有兩個(gè)引用來(lái)表示節(jié)點(diǎn)的左子樹(shù)和右子樹(shù).

static class TreeNode {
        public char val;//數(shù)值
        public TreeNode left;//左子樹(shù)引用
        public TreeNode right;//右子樹(shù)引用

        public TreeNode(char val) {
            this.val = val;
        }
    }

2. 二叉樹(shù)的遍歷

二叉樹(shù)的遍歷 (Traversal) 是指沿著某條搜索路線，依次對(duì)樹(shù)中每個(gè)結(jié)點(diǎn)均做一次且僅做一次訪問(wèn)。訪問(wèn)結(jié)點(diǎn)所做的操作依賴于具體的應(yīng)用問(wèn)題(比如：打印節(jié)點(diǎn)內(nèi)容、節(jié)點(diǎn)內(nèi)容加 1)。遍歷是二叉樹(shù)上最重要的操作之一，是二叉樹(shù)上進(jìn)行其它運(yùn)算之基礎(chǔ)。

其實(shí)不管是前序遍歷，中序遍歷，還是后續(xù)遍歷，二叉樹(shù)的遍歷所走的路徑都是相同的，三者之間的區(qū)別只是獲取根節(jié)點(diǎn)數(shù)據(jù)的時(shí)機(jī)不同。

2.1 前序遍歷

前序遍歷(Preorder Traversal 亦稱先序遍歷)——訪問(wèn)根結(jié)點(diǎn)—>根的左子樹(shù)—>根的右子樹(shù)。

我們利用遞歸解決問(wèn)題的思想, 可以將一個(gè)問(wèn)題拆解為子問(wèn)題去解決, 也就是實(shí)現(xiàn)下面的過(guò)程:

訪問(wèn)根節(jié)點(diǎn)數(shù)據(jù)；
前序遍歷左子樹(shù)；
前序遍歷右子樹(shù);

遞歸結(jié)束條件：如果結(jié)點(diǎn)root為空，則返回。

//前序遍歷
    public void preOrder(TreeNode root) {
        if(root == null) {
            return;
        }
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }

2.2 中序遍歷

中序遍歷(Inorder Traversal)——根的左子樹(shù)—>根節(jié)點(diǎn)—>根的右子樹(shù);

和上面的實(shí)現(xiàn)思想相同, 只是訪問(wèn)根節(jié)點(diǎn)的時(shí)機(jī)不同;

中序遍歷左子樹(shù)；
訪問(wèn)根節(jié)點(diǎn)數(shù)據(jù)；
中序遍歷右子樹(shù);

遞歸結(jié)束條件：如果結(jié)點(diǎn)root為空，則返回。

//中序遍歷
    public void InOrder(TreeNode root) {
        if(root == null) {
            return;
        }
        InOrder(root.left);
        System.out.print(root.val+" ");
        InOrder(root.right);
    }

2.3 后序遍歷

同樣的, 實(shí)現(xiàn)過(guò)程如下,

后序遍歷左子樹(shù)；
后序遍歷右子樹(shù)；
訪問(wèn)根結(jié)點(diǎn)數(shù)據(jù);

遞歸結(jié)束條件：如果結(jié)點(diǎn)root為空，則返回。

//后序遍歷
    public void postOrder(TreeNode root) {
        if(root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");
    }

3. 獲取整棵二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)

獲取樹(shù)中的節(jié)點(diǎn)個(gè)數(shù), 最容易想到的就是遍歷一遍樹(shù), 通過(guò)計(jì)數(shù)實(shí)現(xiàn)了, 代碼寫(xiě)起來(lái)也不難;

也可以通過(guò)遞歸解決子問(wèn)題的思想來(lái)實(shí)現(xiàn) , 本質(zhì)上還是在遍歷二叉樹(shù)

節(jié)點(diǎn)的個(gè)數(shù)等于根節(jié)點(diǎn)(1) + 左子樹(shù)節(jié)點(diǎn)個(gè)數(shù) + 右子樹(shù)節(jié)點(diǎn)個(gè)數(shù) ,

遞歸結(jié)束條件: 如果結(jié)點(diǎn)root為空，則返回。

    //獲取樹(shù)中節(jié)點(diǎn)的個(gè)數(shù),遍歷計(jì)數(shù)法
    public static int nodeSize;
    public int size(TreeNode root) {
        //先將nodeSzie置為0
        nodeSize = 0;
        sizefunc(root);
        return nodeSize;
    }
    public void sizefunc(TreeNode root) {
        if(root == null) {
            return;
        }
        nodeSize++;
        sizefunc(root.left);
        sizefunc(root.right);
    }

    //獲取樹(shù)中節(jié)點(diǎn)的個(gè)數(shù),子問(wèn)題思想
    public int size2(TreeNode root) {
        if(root == null) {
            return 0;
        }
        return size2(root.left) + size2(root.right) + 1;
    }

4. 獲取二叉樹(shù)葉子節(jié)點(diǎn)的個(gè)數(shù)

同樣的思考的話和上面一樣, 可以采用計(jì)數(shù)和子問(wèn)題來(lái)實(shí)現(xiàn), 不過(guò)本質(zhì)上是差不多的;

遞歸思路：

如果結(jié)點(diǎn)為空，表示該樹(shù)沒(méi)有結(jié)點(diǎn)返回0，
如果結(jié)點(diǎn)的左右子樹(shù)都為空，表示該結(jié)點(diǎn)為葉子結(jié)點(diǎn)，計(jì)算器+1或者返回1。
一棵二叉樹(shù)的葉子結(jié)點(diǎn)數(shù)為左右子樹(shù)葉子結(jié)點(diǎn)數(shù)之和。

    //獲取葉子節(jié)點(diǎn)的個(gè)數(shù),子問(wèn)題思想
    public int getLeafNodeCount(TreeNode root){
        if(root == null) {
            return 0;
        }
        if(root.left == null && root.right == null) {
            return 1;
        }
        return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
    }
    //獲取葉子節(jié)點(diǎn)的個(gè)數(shù),遍歷計(jì)數(shù)法
    public static int leafSize;
    public int getLeafNodeCount2(TreeNode root){
        leafSize = 0;
        getLeafNodeCount2func(root);
        return leafSize;
    }
    public void getLeafNodeCount2func(TreeNode root) {
        if(root == null) {
            return;
        }
        if(root.left == null && root.right == null) {
            leafSize++;
        }
        getLeafNodeCount2func(root.left);
        getLeafNodeCount2func(root.right);
    }

5. 獲取第K層節(jié)點(diǎn)的個(gè)數(shù)

遞歸思路：

如果結(jié)點(diǎn)為空，返回0，k為1，返回1。
一棵二叉樹(shù)第k層結(jié)點(diǎn)數(shù)為左子樹(shù)和右子樹(shù)第k-1層次的結(jié)點(diǎn)數(shù)之和。

當(dāng)k=1時(shí)，表示第一層次的結(jié)點(diǎn)個(gè)數(shù)，結(jié)點(diǎn)個(gè)數(shù)為1，每遞歸一層，從根節(jié)點(diǎn)來(lái)說(shuō)是第k層, 那么相對(duì)于根節(jié)點(diǎn)的子樹(shù)來(lái)說(shuō)就是k-1層，所以一棵二叉樹(shù)第k層結(jié)點(diǎn)數(shù)為左子樹(shù)，右子樹(shù)第k-1層次的結(jié)點(diǎn)數(shù)之和。

public int getKLevelNodeCount(TreeNode root, int k) {
        if(root == null || k <= 0) {
            return 0;
        }
        if(k == 1) {
            return 1;
        }
        return getKLevelNodeCount(root.left, k-1) + getKLevelNodeCount(root.right, k-1);
    }

6. 獲取二叉樹(shù)的高度(深度)

遞歸思路：

如果根結(jié)點(diǎn)為空，則這棵樹(shù)的高度為0，返回0。

一棵二叉樹(shù)的最深深度即為左右子樹(shù)深度的最大值加上1。

// 獲取二叉樹(shù)的高度
    public int getHeight(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int leftHight = getHeight(root.left);
        int rightHight = getHeight(root.right);
        return leftHight>rightHight ? leftHight+1 : rightHight+1;
    }

7. 在二叉樹(shù)中尋找目標(biāo)值

通過(guò)遍歷去搜索比較即可, 前中后序遍歷都可以.

//檢測(cè)值為val的元素是否存在
    public boolean find(TreeNode root, char val) {
        if(root == null) {
            return false;
        }
        if(root.val == val) {
            return true;
        }
        boolean ret1 = find(root.left, val);
        if(ret1){
            return true;
        }
        boolean ret2 = find(root.right, val);
        if(ret2){
            return true;
        }
        return false;
    }

8. 判斷二叉樹(shù)是不是完全二叉樹(shù)

判斷一棵樹(shù)是不是完全二叉樹(shù)，我們可以設(shè)計(jì)一個(gè)隊(duì)列來(lái)實(shí)現(xiàn)，

完全二叉樹(shù)按照從上至下, 從左到右的順序節(jié)點(diǎn)之間是連續(xù)著沒(méi)有空位置的, 這里如果有不了解的可以看一看二叉樹(shù)概念篇的博客; 如果一顆二叉樹(shù)不是完全二叉樹(shù) , 那么樹(shù)中的節(jié)點(diǎn)之間是有空著的位置的(null); 只要找到這個(gè)位置, 后面再?zèng)]有節(jié)點(diǎn)了就是完全二叉樹(shù); 如果空位置后面還有節(jié)點(diǎn)就不是完全二叉樹(shù);

我們可以設(shè)計(jì)一個(gè)隊(duì)列來(lái)實(shí)現(xiàn), 首先將根節(jié)點(diǎn)入隊(duì)，然后循環(huán)每次將隊(duì)頭元素出隊(duì)同時(shí)將出隊(duì)節(jié)點(diǎn)的左右孩子結(jié)點(diǎn)（包括空結(jié)點(diǎn)）依次入隊(duì)，以此類推，直到獲取的結(jié)點(diǎn)為空(就是上面說(shuō)的空位置)，此時(shí)判斷隊(duì)列中的所有元素是否為空，如果為空，就表示這棵二叉樹(shù)為完全二叉樹(shù) ; 否則就不是完全二叉樹(shù).

//判斷一棵樹(shù)是不是完全二叉樹(shù)
    public boolean isCompleteTree(TreeNode root) {
        if(root == null) {
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if(cur == null) {
                break;
            }
            queue.offer(cur.left);
            queue.offer(cur.right);
        }
        //判斷隊(duì)列中是否有不為空的元素
        int size = queue.size();
        while(size != 0) {
            size--;
            if(queue.poll() != null) {
                return false;
            }
        }
        return true;
    }

9. 層序遍歷

層序遍歷的實(shí)現(xiàn)方式與判斷一棵二叉樹(shù)是否是完全二叉樹(shù)類似，都是使用隊(duì)列來(lái)進(jìn)行實(shí)現(xiàn)，只有一點(diǎn)不同, 入隊(duì)時(shí)如果結(jié)點(diǎn)為空，則不需要入隊(duì)，其他的地方完全相同, 出隊(duì)時(shí)獲取到節(jié)點(diǎn)中的元素, 直到最終隊(duì)列和當(dāng)前結(jié)點(diǎn)均為空時(shí)，表示遍歷結(jié)束。

//層序遍歷
    public void levelOrder(TreeNode root) {
        if(root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            System.out.print(cur.val+" ");
            if(cur.left != null) {
                queue.offer(cur.left);
            }
            if(cur.right != null) {
                queue.offer(cur.right);
            }
        }
     }

到此這篇關(guān)于Java實(shí)現(xiàn)二叉樹(shù)的基本操作詳解的文章就介紹到這了,更多相關(guān)Java二叉樹(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: