[[388287]]

 為什么需要樹(shù)這種結(jié)構(gòu)

1.數(shù)組存儲(chǔ)方式分析：

• 優(yōu)點(diǎn)：通過(guò)下標(biāo)方式訪問(wèn)元素，速度快。對(duì)于有序數(shù)組，還可以使用二分查找提高檢索速度。
• 缺點(diǎn)：如果檢索某個(gè)具體的值，或者插入值(按一定的順序)會(huì)整體移動(dòng)，效率較低。

2.鏈?zhǔn)酱鎯?chǔ)方式分析：

• 優(yōu)點(diǎn)：在一定程度上對(duì)數(shù)組存儲(chǔ)方式優(yōu)化(比如：插入一個(gè)數(shù)值節(jié)點(diǎn)，只需要將插入節(jié)點(diǎn)，鏈接到鏈表中即可，刪除效率很高)。
• 缺點(diǎn)：在進(jìn)行檢索時(shí)，效率仍然很低，需要從頭結(jié)點(diǎn)開(kāi)始遍歷。

3.樹(shù)存儲(chǔ)方式分析：能提高數(shù)據(jù)存儲(chǔ)，讀取的效率，比如利用二叉排序樹(shù)(Binary sort tree)，即可以保證數(shù)據(jù)的檢索速度，同時(shí)也可以保證數(shù)據(jù)的插入、刪除、修改的速度。假設(shè)一組[7,3,10,1,5,9,12]以樹(shù)的方式存儲(chǔ)，分析如下圖：

二叉樹(shù)的前序遍歷、中序遍歷、后序遍歷

• 前序遍歷：輸出父節(jié)點(diǎn)、輸出左邊節(jié)點(diǎn)、輸出右邊節(jié)點(diǎn);
• 中序遍歷：輸出左邊節(jié)點(diǎn)、輸出父節(jié)點(diǎn)、輸出右邊節(jié)點(diǎn);
• 后序遍歷：輸出左邊節(jié)點(diǎn)、輸出右邊節(jié)點(diǎn)、輸出父節(jié)點(diǎn);

需求案例

完成一個(gè)如下二叉樹(shù)節(jié)點(diǎn)存儲(chǔ)、前序遍歷搜索、中序遍歷搜索、后序遍歷搜索和刪除節(jié)點(diǎn)功能。

對(duì)于刪除節(jié)點(diǎn)要求如下：

1. 如果刪除的節(jié)點(diǎn)是葉子節(jié)點(diǎn)，則刪除該節(jié)點(diǎn)。
2. 如果刪除的節(jié)點(diǎn)是非葉子節(jié)點(diǎn)，則刪除該樹(shù)。
3. 測(cè)試，刪除5號(hào)葉子節(jié)點(diǎn)和3號(hào)子樹(shù)。

代碼案例

package com.xie.tree; 
 
public class BinaryTreeDemo { 
 
    public static void main(String[] args) { 
        BinaryTree binaryTree = new BinaryTree(); 
 
        HeroNode root = new HeroNode(1, "宋江"); 
        HeroNode node2 = new HeroNode(2, "吳用"); 
        HeroNode node3 = new HeroNode(3, "盧俊義"); 
        HeroNode node4 = new HeroNode(4, "林沖"); 
        HeroNode node5 = new HeroNode(5, "關(guān)勝"); 
 
        //先手動(dòng)創(chuàng)建該二叉樹(shù)，后面用遞歸方式 
        root.setLeft(node2); 
        root.setRight(node3); 
        node3.setRight(node4); 
        node3.setLeft(node5); 
 
        binaryTree.setRoot(root); 
 
        //前序遍歷 
        System.out.println("前序遍歷"); 
        binaryTree.preOrder(); 
 
        //中序遍歷 
        System.out.println("中序遍歷"); 
        binaryTree.infixOrder(); 
 
        //后續(xù)遍歷 
        System.out.println("后續(xù)遍歷"); 
        binaryTree.postOrder(); 
 
        //前序遍歷查找 
        System.out.println("前序遍歷查找~~"); 
        HeroNode resultNode = binaryTree.preOrderSearch(5); 
        if (resultNode != null) { 
            System.out.printf("找到了，信息為no=%d,name=%s\n", resultNode.getNo(), resultNode.getName()); 
            System.out.println("遍歷次數(shù)：" + HeroNode.preCount); 
        } else { 
            System.out.println("沒(méi)有找到"); 
        } 
 
        //中序遍歷查找 
        System.out.println("中序遍歷查找~~"); 
        HeroNode resultNode1 = binaryTree.infixOrderSearch(5); 
        if (resultNode1 != null) { 
            System.out.printf("找到了，信息為no=%d,name=%s\n", resultNode1.getNo(), resultNode1.getName()); 
            System.out.println("遍歷次數(shù)：" + HeroNode.infoxCount); 
        } else { 
            System.out.println("沒(méi)有找到"); 
        } 
 
        //后序遍歷查找 
        System.out.println("后序遍歷查找~~"); 
        HeroNode resultNode2 = binaryTree.postOrderSearch(5); 
        if (resultNode2 != null) { 
            System.out.printf("找到了，信息為no=%d,name=%s\n", resultNode2.getNo(), resultNode2.getName()); 
            System.out.println("遍歷次數(shù)：" + HeroNode.postCount); 
        } else { 
            System.out.println("沒(méi)有找到"); 
        } 
 
        System.out.println("刪除3號(hào)節(jié)點(diǎn)"); 
        binaryTree.delNo(3); 
        System.out.println("刪除后的節(jié)點(diǎn)"); 
        binaryTree.preOrder(); 
        /** 
         * 前序遍歷 
         * HeroNode{no=1, name=宋江} 
         * HeroNode{no=2, name=吳用} 
         * HeroNode{no=3, name=盧俊義} 
         * HeroNode{no=5, name=關(guān)勝} 
         * HeroNode{no=4, name=林沖} 
         * 中序遍歷 
         * HeroNode{no=2, name=吳用} 
         * HeroNode{no=1, name=宋江} 
         * HeroNode{no=5, name=關(guān)勝} 
         * HeroNode{no=3, name=盧俊義} 
         * HeroNode{no=4, name=林沖} 
         * 后續(xù)遍歷 
         * HeroNode{no=2, name=吳用} 
         * HeroNode{no=5, name=關(guān)勝} 
         * HeroNode{no=4, name=林沖} 
         * HeroNode{no=3, name=盧俊義} 
         * HeroNode{no=1, name=宋江} 
         * 前序遍歷查找~~ 
         * 找到了，信息為no=5,name=關(guān)勝 
         * 遍歷次數(shù)：4 
         * 中序遍歷查找~~ 
         * 找到了，信息為no=5,name=關(guān)勝 
         * 遍歷次數(shù)：3 
         * 后序遍歷查找~~ 
         * 找到了，信息為no=5,name=關(guān)勝 
         * 遍歷次數(shù)：2 
         * 刪除3號(hào)節(jié)點(diǎn) 
         * 刪除后的節(jié)點(diǎn) 
         * HeroNode{no=1, name=宋江} 
         * HeroNode{no=2, name=吳用} 
         */ 
    } 
} 
 
class BinaryTree { 
    private HeroNode root; 
 
    public void setRoot(HeroNode root) { 
        this.root = root; 
    } 
 
    //前序遍歷 
    public void preOrder() { 
        if (this.root != null) { 
            this.root.preOrder(); 
        } 
    } 
 
    //中序遍歷 
    public void infixOrder() { 
        if (this.root != null) { 
            this.root.infixOrder(); 
        } 
    } 
 
    //刪除節(jié)點(diǎn) 
    public void delNo(int no) { 
        if (this.root != null) { 
            if (this.root.getNo() == no) { 
                this.root = null; 
            } else { 
                this.root.delNo(no); 
            } 
        } 
        return; 
    } 
 
    //后序遍歷 
    public void postOrder() { 
        if (this.root != null) { 
            this.root.postOrder(); 
        } 
    } 
 
    //前序遍歷查找 
    public HeroNode preOrderSearch(int no) { 
        if (root != null) { 
            return root.preOrderSearch(no); 
        } else { 
            return null; 
        } 
    } 
 
    //中序遍歷查找 
    public HeroNode infixOrderSearch(int no) { 
        if (root != null) { 
            return root.infixOrderSearch(no); 
        } else { 
            return null; 
        } 
    } 
 
    //后序遍歷查找 
    public HeroNode postOrderSearch(int no) { 
        if (root != null) { 
            return root.postOrderSearch(no); 
        } else { 
            return null; 
        } 
    } 
} 
 
class HeroNode { 
    static int preCount = 0; 
    static int infoxCount = 0; 
    static int postCount = 0; 
 
    private int no; 
    private String name; 
    private HeroNode left; 
    private HeroNode right; 
 
    public HeroNode(int no, String name) { 
        this.no = no; 
        this.name = name; 
    } 
 
    public int getNo() { 
        return no; 
    } 
 
    public void setNo(int no) { 
        this.no = no; 
    } 
 
    public String getName() { 
        return name; 
    } 
 
    public void setName(String name) { 
        this.name = name; 
    } 
 
    public HeroNode getLeft() { 
        return left; 
    } 
 
    public void setLeft(HeroNode left) { 
        this.left = left; 
    } 
 
    public HeroNode getRight() { 
        return right; 
    } 
 
    public void setRight(HeroNode right) { 
        this.right = right; 
    } 
 
    @Override 
    public String toString() { 
        return "HeroNode{" + 
                "no=" + no + 
                ", name=" + name + 
                '}'; 
    } 
 
    //前序遍歷 
    public void preOrder() { 
        System.out.println(this); 
        //遞歸向左子樹(shù)前序遍歷 
        if (this.left != null) { 
            this.left.preOrder(); 
        } 
 
        //遞歸向右子樹(shù)前序遍歷 
        if (this.right != null) { 
            this.right.preOrder(); 
        } 
    } 
 
    //中序遍歷 
    public void infixOrder() { 
        //遞歸向左子樹(shù)中序遍歷 
        if (this.left != null) { 
            this.left.infixOrder(); 
        } 
        System.out.println(this); 
        //遞歸向右子樹(shù)中序遍歷 
        if (this.right != null) { 
            this.right.infixOrder(); 
        } 
    } 
 
    //后序遍歷 
    public void postOrder() { 
        //遞歸向左子樹(shù)后序遍歷 
        if (this.left != null) { 
            this.left.postOrder(); 
        } 
        //遞歸向右子樹(shù)后序遍歷 
        if (this.right != null) { 
            this.right.postOrder(); 
        } 
        System.out.println(this); 
    } 
 
    //遞歸刪除節(jié)點(diǎn) 
    //1.如果刪除的節(jié)點(diǎn)是葉子節(jié)點(diǎn)，則刪除該節(jié)點(diǎn)。 
    //2.如果刪除的節(jié)點(diǎn)是非葉子節(jié)點(diǎn)，則刪除該樹(shù)。 
    public void delNo(int no) { 
        /** 
         * 1.因?yàn)槲覀兊亩鏄?shù)是單向的，所以我們是判斷當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)是否是需要?jiǎng)h除的節(jié)點(diǎn)，而不能去判斷當(dāng)前節(jié)點(diǎn)是否是需要?jiǎng)h除的節(jié)點(diǎn)。 
         * 2.如果當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)不為空，并且左子節(jié)點(diǎn)就是需要?jiǎng)h除的節(jié)點(diǎn)，就將this.left = null；并且返回（結(jié)束遞歸）。 
         * 3.如果當(dāng)前節(jié)點(diǎn)的右子節(jié)點(diǎn)不為空，并且右子節(jié)點(diǎn)就是需要?jiǎng)h除的節(jié)點(diǎn)，將將this.right = null;并且返回（結(jié)束遞歸）。 
         * 4.如果第2步和第3步?jīng)]有刪除節(jié)點(diǎn)，那么就要向左子樹(shù)進(jìn)行遞歸刪除。 
         * 5.如果第4步也沒(méi)有刪除節(jié)點(diǎn)，則應(yīng)當(dāng)向右子樹(shù)進(jìn)行遞歸刪除。 
         */ 
        if (this.left != null && this.left.no == no) { 
            this.left = null; 
            return; 
        } 
 
        if (this.right != null && this.right.no == no) { 
            this.right = null; 
            return; 
        } 
 
        if (this.left != null) { 
            this.left.delNo(no); 
        } 
 
        if (this.right != null) { 
            this.right.delNo(no); 
        } 
 
    } 
 
    //前序遍歷查找 
    public HeroNode preOrderSearch(int no) { 
 
        HeroNode res = null; 
 
        preCount++;//這里必須放在this.no == no 判斷之前，才進(jìn)行實(shí)際的比較 
        //若果找到，就返回 
        if (this.no == no) { 
            return this; 
        } 
        //沒(méi)有找到，向左子樹(shù)遞歸進(jìn)行前序查找 
        if (this.left != null) { 
            res = this.left.preOrderSearch(no); 
        } 
        //如果res ！= null 就直接返回 
        if (res != null) { 
            return res; 
        } 
        //如果左子樹(shù)沒(méi)有找打，向右子樹(shù)進(jìn)行前序查找 
        if (this.right != null) { 
            res = this.right.preOrderSearch(no); 
        } 
        //如果找到就返回 
        if (res != null) { 
            return res; 
        } 
        return res; 
    } 
 
    //中序遍歷查找 
    public HeroNode infixOrderSearch(int no) { 
 
        HeroNode res = null; 
        if (this.left != null) { 
            res = this.left.infixOrderSearch(no); 
        } 
        if (res != null) { 
            return res; 
        } 
        infoxCount++;//這里必須放在this.no == no 判斷之前，才進(jìn)行實(shí)際的比較 
        if (this.no == no) { 
            return this; 
        } 
        if (this.right != null) { 
            res = this.right.infixOrderSearch(no); 
        } 
        if (res != null) { 
            return res; 
        } 
        return res; 
    } 
 
    //后序遍歷查找 
    public HeroNode postOrderSearch(int no) { 
 
        HeroNode res = null; 
        if (this.left != null) { 
            res = this.left.postOrderSearch(no); 
        } 
        if (res != null) { 
            return res; 
        } 
 
        if (this.right != null) { 
            res = this.right.postOrderSearch(no); 
        } 
        if (res != null) { 
            return res; 
        } 
        postCount++;//這里必須放在this.no == no 判斷之前，才進(jìn)行實(shí)際的比較 
        if (this.no == no) { 
            return this; 
        } 
        return res; 
    } 
} 

 【編輯推薦】