两个吃奶一个添下面视频_人妻第一页香蕉网_欧美xxxx少妇_妺妺窝人体色www婷婷

一、什么是樹(shù)

樹(shù)是一種類(lèi)似鏈表的數(shù)據(jù)結(jié)構(gòu),不過(guò)鏈表的結(jié)點(diǎn)是以線(xiàn)性方式簡(jiǎn)單地指向其后繼指點(diǎn),而樹(shù)的一個(gè)結(jié)點(diǎn)可以指向許多個(gè)結(jié)點(diǎn)。樹(shù)是一種典型的非線(xiàn)性結(jié)構(gòu)。樹(shù)結(jié)構(gòu)是表達(dá)具有層次特性的圖結(jié)構(gòu)的一種方法。


二、相關(guān)術(shù)語(yǔ)

樹(shù)

● 根結(jié)點(diǎn):根結(jié)點(diǎn)就是一個(gè)沒(méi)有雙親結(jié)點(diǎn)的結(jié)點(diǎn)。一棵樹(shù)中最多有一個(gè)根結(jié)點(diǎn)(如圖2-1的結(jié)點(diǎn)A就是根結(jié)點(diǎn))。

● 邊:邊表示從雙親結(jié)點(diǎn)到孩子結(jié)點(diǎn)的鏈接(如圖2-1的所有鏈接)。

● 葉子結(jié)點(diǎn):沒(méi)有孩子結(jié)點(diǎn)的結(jié)點(diǎn)叫做葉子結(jié)點(diǎn)(如圖2-1中的E、J、K、H、I )。

● 兄弟結(jié)點(diǎn):擁有相同的雙親結(jié)點(diǎn)的所有孩子結(jié)點(diǎn)叫做兄弟結(jié)點(diǎn)(如圖2-1中的B、C、D是A的兄弟結(jié)點(diǎn))。

● 祖先結(jié)點(diǎn):如果存在一條從根結(jié)點(diǎn)到q的路徑,且結(jié)點(diǎn)p出現(xiàn)在這條路徑上,那么就可以把p叫做q的祖先結(jié)點(diǎn)(如圖2-1中A、C、G是K的祖先結(jié)點(diǎn))。

● 結(jié)點(diǎn)的大?。航Y(jié)點(diǎn)的大小是指子孫的個(gè)數(shù),包括其自身(如圖2-1中子樹(shù)C的大小為3)。

樹(shù)的層

● 樹(shù)的層:位于相同深度的所有結(jié)點(diǎn)的集合叫做樹(shù)的層(如圖2-2中的1和4具有相同的層)。

● 結(jié)點(diǎn)的深度:是指從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑長(zhǎng)度(如圖2-2中的5深度為2,3-4-5)。

● 結(jié)點(diǎn)的高度:是指從結(jié)點(diǎn)到最深結(jié)點(diǎn)的路徑長(zhǎng)度。樹(shù)的高度是指根結(jié)點(diǎn)到樹(shù)中最深結(jié)點(diǎn)的路徑長(zhǎng)度。只含有根結(jié)點(diǎn)的樹(shù)的高度是0(如圖2-2樹(shù)的高度為2)。

斜樹(shù)

● 斜樹(shù):如果樹(shù)中除了葉子結(jié)點(diǎn)外,其余每個(gè)結(jié)點(diǎn)都只有一個(gè)孩子結(jié)點(diǎn),則這種樹(shù)稱(chēng)為斜樹(shù)(如圖2-3)。



三、二叉樹(shù)

如果一棵樹(shù)中的每個(gè)結(jié)點(diǎn)有0、1或2個(gè)孩子結(jié)點(diǎn),那么這個(gè)樹(shù)就稱(chēng)為二叉樹(shù)??諛?shù)也是一棵有效的二叉樹(shù)。一棵二叉樹(shù)可以看作由根結(jié)點(diǎn)和兩棵不相交的子樹(shù)組成,如圖3-1所示。

二叉樹(shù)示例


1. 二叉樹(shù)的類(lèi)型

(1)嚴(yán)格二叉樹(shù):二叉樹(shù)中的每個(gè)結(jié)點(diǎn)要么有兩個(gè)孩子結(jié)點(diǎn),要么沒(méi)有孩子結(jié)點(diǎn)(如圖3-2所示)。

嚴(yán)格二叉樹(shù)


(2)滿(mǎn)二叉樹(shù):二叉樹(shù)的每個(gè)結(jié)點(diǎn)恰好有兩個(gè)孩子結(jié)點(diǎn)且所有葉子結(jié)點(diǎn)在同一層(如圖3-3所示)。

滿(mǎn)二叉樹(shù)

(3)完全二叉樹(shù):假定二叉樹(shù)的高度為h。對(duì)于完全二叉樹(shù),如果將所有結(jié)點(diǎn)從根結(jié)點(diǎn)開(kāi)始從左至右,從上至下,依次編號(hào)(假定根結(jié)點(diǎn)編號(hào)為1),那么將得到從1~n(n為結(jié)點(diǎn)總數(shù))的完整序列。如果所有葉子結(jié)點(diǎn)的深度為h或者h(yuǎn)-1,且結(jié)點(diǎn)在編號(hào)過(guò)程中沒(méi)有漏掉任何數(shù)字,那么就叫做完全二叉樹(shù)(如圖3-4所示)。

完全二叉樹(shù)

2. 二叉樹(shù)的性質(zhì)

假定樹(shù)的高度為h,且根結(jié)點(diǎn)的深度為0。

二叉樹(shù)性質(zhì)

從圖3-5可得出如下性質(zhì):

(1)滿(mǎn)二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)n為[2^(h+1)] -1。因?yàn)樵摌?shù)總共有h層,每一層結(jié)點(diǎn)都是滿(mǎn)的。

(2)滿(mǎn)二叉樹(shù)的葉子結(jié)點(diǎn)個(gè)數(shù)是2^h。

3. 二叉樹(shù)的結(jié)構(gòu)

表示一個(gè)結(jié)點(diǎn)的方法之一是定義兩個(gè)指針,一個(gè)指向左孩子結(jié)點(diǎn),另一個(gè)指向右孩子結(jié)點(diǎn),中間為數(shù)據(jù)字段(如圖3-6所示)。

二叉樹(shù)的結(jié)構(gòu)

代碼實(shí)現(xiàn):

public class BinaryTreeNode {
    private int data;
    private BinaryTreeNode left;
    private BinaryTreeNode right;

    public int getData(){
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public BinaryTreeNode getLeft() {
        return left;
    }

    public void setLeft(BinaryTreeNode left) {
        this.left = left;
    }

    public BinaryTreeNode getRight() {
        return right;
    }

    public void setRight(BinaryTreeNode right) {
        this.right = right;
    }}

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

訪(fǎng)問(wèn)樹(shù)中所有結(jié)點(diǎn)的過(guò)程叫做遍歷,遍歷的目標(biāo)是按照某種特定的順序訪(fǎng)問(wèn)樹(shù)的所有結(jié)點(diǎn)。

(1)遍歷的分類(lèi)

● 前序遍歷(DLR):訪(fǎng)問(wèn)當(dāng)前結(jié)點(diǎn),遍歷左子樹(shù),再遍歷右子樹(shù)。

● 中序遍歷(LDR):先遍歷左子樹(shù),訪(fǎng)問(wèn)當(dāng)前結(jié)點(diǎn),再遍歷右子樹(shù)。

● 后序遍歷(LRD):先遍歷左子樹(shù),再遍歷右子樹(shù),訪(fǎng)問(wèn)當(dāng)前結(jié)點(diǎn)。

● 層次遍歷。

以下圖所示的樹(shù)為例。

二叉樹(shù)的遍歷

①前序遍歷

● 基于前序遍歷,圖3-7所示樹(shù)的前序遍歷結(jié)果如下:

前序遍歷結(jié)果:
1
2
4
5
3
6
7

Process finished with exit code 0

● 遞歸前序遍歷,代碼實(shí)現(xiàn)如下:

    public void PreOrder(BinaryTreeNode root){
        if(root!=null){
            System.out.print(root.getData());
            PreOrder(root.getLeft());
            PreOrder(root.getRight());
        }
    }

● 非遞歸前序遍歷,需要采用一個(gè)棧來(lái)記錄當(dāng)前結(jié)點(diǎn),以便在完成左子樹(shù)遍歷后能返回到右子樹(shù)進(jìn)行遍歷。首先處理當(dāng)前結(jié)點(diǎn),在遍歷左子樹(shù)之前,把當(dāng)前結(jié)點(diǎn)保留到棧中,當(dāng)遍歷完左子樹(shù)之后,該元素出棧,然后找到其右子樹(shù)進(jìn)行遍歷,直至???。代碼實(shí)現(xiàn)如下:

   public void PreOrderNonRecursive(BinaryTreeNode root){
        if(root==null){
            return;
        }
        Stack s=new Stack();
        while (true){
            while (root!=null){
                System.out.print(root.getData());
                s.push(root);
                root=root.getLeft();
            }
            if(s.isEmpty()){
                break;
            }
            root=(BinaryTreeNode) s.pop();
            root=root.getRight();
        }
    }

②中序遍歷

● 基于中序遍歷,圖3-7所示樹(shù)的中序遍歷結(jié)果如下:

中序遍歷結(jié)果:
4
2
5
1
6
3
7

Process finished with exit code 0

● 遞歸中序遍歷,代碼實(shí)現(xiàn)如下:

    public void InOrder(BinaryTreeNode root){
        if(root!=null){
            InOrder(root.getLeft());
            System.out.print(root.getData());
            InOrder(root.getRight());
        }
    }

● 非遞歸中序遍歷,與前序遍歷的區(qū)別是,首先要移動(dòng)到結(jié)點(diǎn)的左子樹(shù),完成左子樹(shù)的遍歷后,再將當(dāng)前結(jié)點(diǎn)出棧進(jìn)行處理。

    public void InOrderNonRecursive(BinaryTreeNode root){
        if(root==null){
            return;
        }
        Stack s=new Stack();
        while (true){
            while (root!=null){
                s.push(root);
                root=root.getLeft();
            }
            if(s.isEmpty()){
                break;
            }
            root=(BinaryTreeNode)s.pop();
            System.out.print(root.getData()+"\n");
            root=root.getRight();
        }
    }

③后序遍歷

● 基于后序遍歷,圖3-7所示樹(shù)的后序遍歷結(jié)果如下:

后序遍歷結(jié)果:
4
5
2
6
7
3
1

Process finished with exit code 0

● 遞歸后序遍歷,代碼實(shí)現(xiàn)如下:

    public void PostOrder(BinaryTreeNode root){
        if(root!=null){
            PostOrder(root.getLeft());
            PostOrder(root.getRight());
            System.out.print(root.getData());
        }
    }

● 非遞歸后序遍歷,在前序和中序遍歷中,當(dāng)元素出棧后就不需要再訪(fǎng)問(wèn)這個(gè)結(jié)點(diǎn)了。但是后序遍歷中,每個(gè)結(jié)點(diǎn)需要訪(fǎng)問(wèn)兩次。這意味著,在遍歷完左子樹(shù)后,需要訪(fǎng)問(wèn)當(dāng)前結(jié)點(diǎn),之后遍歷完右子樹(shù)時(shí),還需要訪(fǎng)問(wèn)當(dāng)前結(jié)點(diǎn)。但只有在第二次訪(fǎng)問(wèn)時(shí)才處理該結(jié)點(diǎn)。

● 解決辦法是,當(dāng)從棧中出棧一個(gè)元素時(shí),檢查這個(gè)元素與棧頂元素的右子結(jié)點(diǎn)是否相同。如果相同,則說(shuō)明已經(jīng)完成了左右子樹(shù)的遍歷。此時(shí)只要再將棧頂元素出棧并輸出該結(jié)點(diǎn)元素。

     public void PostOrderNonRecursive(BinaryTreeNode root){
        Stack stack=new Stack();
        while (true){
            if(root!=null){
                //尋找最左葉子結(jié)點(diǎn)
                stack.push(root);
                root=root.getLeft();
            }else {
                if(stack.isEmpty()){
                    return;
                }else {
                    //判斷當(dāng)前結(jié)點(diǎn)是否有右子節(jié)點(diǎn)
                    if(stack.top().getRight==null){
                        root=stack.pop();
                        System.out.print(root.getData()+"\n");
                        //判斷該結(jié)點(diǎn)是否為棧頂右子節(jié)點(diǎn)
                        while(root==stack.top().getRight()){
                            System.out.print(stack.top().getData()+"\n");
                            root=stack.pop();
                            if(stack.isEmpty()){
                                return;
                            }
                        }
                    }
                }
                if(!stack.isEmpty()){
                    //遍歷結(jié)點(diǎn)右子樹(shù)
                    root=stack.top().getRight();
                }else {
                    root=null;
                }
            }
        }
    }

④層次遍歷

● 基于層次遍歷,圖3-7所示樹(shù)的層次遍歷結(jié)果如下:

層次遍歷結(jié)果:
1
2
3
4
5
6
7

Process finished with exit code 0

層次遍歷,代碼實(shí)現(xiàn)如下:

public void LevelOrder(BinaryTreeNode root){
        BinaryTreeNode temp;
        LLBinaryTreeQueue queue=LLBinaryTreeQueue.creteQueue();
        if(root==null){
            return;
        }
        queue.enQueue(root);
        while (!queue.isEmpty()){
            temp=queue.deQueue();
            //處理當(dāng)前結(jié)點(diǎn)
            System.out.print(temp.getData()+"\n");
            if(temp.getLeft()!=null){
                queue.enQueue(temp.getLeft());
            }
            if(temp.getRight()!=null){
                queue.enQueue(temp.getRight());
            }
        }
    }


點(diǎn)贊(0)

C語(yǔ)言網(wǎng)提供由在職研發(fā)工程師或ACM藍(lán)橋杯競(jìng)賽優(yōu)秀選手錄制的視頻教程,并配有習(xí)題和答疑,點(diǎn)擊了解:

一點(diǎn)編程也不會(huì)寫(xiě)的:零基礎(chǔ)C語(yǔ)言學(xué)練課程

解決困擾你多年的C語(yǔ)言疑難雜癥特性的C語(yǔ)言進(jìn)階課程

從零到寫(xiě)出一個(gè)爬蟲(chóng)的Python編程課程

只會(huì)語(yǔ)法寫(xiě)不出代碼?手把手帶你寫(xiě)100個(gè)編程真題的編程百練課程

信息學(xué)奧賽或C++選手的 必學(xué)C++課程

藍(lán)橋杯ACM、信息學(xué)奧賽的必學(xué)課程:算法競(jìng)賽課入門(mén)課程

手把手講解近五年真題的藍(lán)橋杯輔導(dǎo)課程

Dotcpp在線(xiàn)編譯      (登錄可減少運(yùn)行等待時(shí)間)