請詳細講一下二級考試中有關樹與二叉樹的有關知識

時間 2021-09-15 00:11:59

1樓:匿名使用者

資料結構分為兩大型別:線性結構和非線性結構。

(1)線性結構(非空的資料結構)條件:1)有且只有一個根結點[在資料結構中,沒有前件的結點稱為根結點。];2)每一個結點最多有一個前件,也最多有一個後件。

*:常見的線性結構有線性表、棧、佇列和線性連結串列等。

(2)非線性結構:不滿足線性結構條件的資料結構。

*:常見的非線性結構有樹、二叉樹和圖等。

二叉樹及其基本性質

(1)什麼是二叉樹

二叉樹是一種很有用的非線性結構,它具有以下兩個特點:1)非空二叉樹只有一個根結點;2)每一個結點最多有兩棵子樹,且分別稱為該結點的左子樹與右子樹。

*:根據二叉樹的概念可知,二叉樹的度可以為0(葉結點)、1(只有一棵子樹)或2(有2棵子樹)。(2)二叉樹的基本性質性質1  在二叉樹的第k層上,最多有          個結點。

性質2  深度為m的二叉樹最多有個      個結點。

性質3  在任意一棵二叉樹中,度數為0的結點(即葉子結點)總比度為2的結點多一個。性質4  具有n個結點的二叉樹,其深度至少為          ,其中        表示取         的整數部分。

3、滿二叉樹與完全二叉樹

滿二叉樹:除最後一層外,每一層上的所有結點都有兩個子結點。

完全二叉樹:除最後一層外,每一層上的結點數均達到最大值;在最後一層上只缺少右邊的若干結點。

*:根據完全二叉樹的定義可得出:度為1的結點的個數為0或1。

下圖a表示的是滿二叉樹,下圖b表示的是完全二叉樹:

完全二叉樹還具有如下兩個特性:

性質5  具有n個結點的完全二叉樹深度為          。

性質6  設完全二叉樹共有n個結點,如果從根結點開始,按層序(每一層從左到右)用自然數1,2,…,n給結點進行編號,則對於編號為k(k=1,2,…,n)的結點有以下結論:

①若k=1,則該結點為根結點,它沒有父結點;若k>1,則該結點的父結點的編號為int (k/2)。

②若2k≤n,則編號為k的左子結點編號為2k;否則該結點無子結點。

③若2k+1≤n,則編號為k的右子結點編號為2k+1;否則該結點無右子結點。

4、二叉樹的儲存結構

在計算機中,二叉樹通常採用鏈式儲存結構。

與線性連結串列類似,用於儲存二叉樹中各元素的儲存結點也由兩部分組成:資料域和指標域。但在二叉樹中,由於每一個元素可以有兩個後件(即兩個子結點),因此,用於儲存二叉樹的儲存結點的指標域有兩個:

一個用於指向該結點的左子結點的儲存地址,稱為左指標域;另一個用於指向該結點的右子結點的儲存地址,稱為右指標域。

*:一般二叉樹通常採用鏈式儲存結構,對於滿二叉樹與完全二叉樹來說,可以按層序進行順序儲存[這樣,不僅節省了儲存空間,又能方便地確定每一個結點的父結點與左右子結點的位置,但順序儲存結構對於一般的二叉樹不適用。]。

5、二叉樹的遍歷二叉樹的遍歷是指不重複地訪問二叉樹中的所有結點。二叉樹的遍歷可以分為以下三種:

(1)前序遍歷(dlr):若二叉樹為空,則結束返回。否則:

首先訪問根結點,然後遍歷左子樹,最後遍歷右子樹;並且,在遍歷左右子樹時,仍然先訪問根結點,然後遍歷左子樹,最後遍歷右子樹。

(2)中序遍歷(ldr):若二叉樹為空,則結束返回。否則:

首先遍歷左子樹,然後訪問根結點,最後遍歷右子樹;並且,在遍歷左、右子樹時,仍然先遍歷左子樹,然後訪問根結點,最後遍歷右子樹。(3)後序遍歷(lrd):若二叉樹為空,則結束返回。

否則:首先遍歷左子樹,然後遍歷右子樹,最後訪問根結點,並且,在遍歷左、右子樹時,仍然先遍歷左子樹,然後遍歷右子樹,最後訪問根結點。

2樓:逆

自己上網查計算機二級公共基礎知識!**有要考的知識點!

樹與二叉樹的區別

3樓:清溪看世界

一、性質不同

樹:樹是一種資料結構。

二叉樹:二叉樹是每個結點最多有兩個子樹的一種樹結構。

二、結點不同

樹:樹的每個結點有零個或多個子結點;沒有父結點的結點稱為根結點;每一個非根結點有且只有一個父結點。

二叉樹:每個結點最多有兩個子樹。

三、種類不同

樹:樹的種類包括無序樹、有序樹、二叉樹和霍夫曼樹等。

二叉樹:二叉樹的種類包括完全二叉樹、滿二叉樹和平衡二叉樹。

4樓:匿名使用者

計算機二級公共基礎知識:樹與二叉樹

5樓:殘影悠然

二叉樹不是樹的一種特殊情形,儘管其與樹有許多相似之處,但樹和二叉樹有兩個主要差別:

1. 樹中結點的最大度數沒有限制,而二叉樹結點的最大度數為2;

2. 樹的結點無左、右之分,而二叉樹的結點有左、右之分。

6樓:匿名使用者

二叉樹是樹的一種,開可以有三叉樹、四叉樹、……,以及混合叉樹。

不過一般只討論二叉樹,這是最典型、最有用的資料結構。

7樓:慕容碧點

樹:沒有順序關係,樹的節點有很多,樹不可以為空。

二叉樹:節點是有順序關係,樹的節點最多為二個節點 可以為空。

8樓:拱楓

就是樹下面長了個樹杈子吧

樹和二叉樹的基本知識?

9樓:匿名使用者

二叉樹在電腦科學中,二叉樹是每個結點最多有兩個子樹的有序樹。通常子樹的根被稱版

作「權左子樹」(left subtree)和「右子樹」(right subtree)。二叉樹常被用作二叉查詢樹和二叉堆。二叉樹的每個結點至多隻有二棵子樹(不存在度大於2的結點),二叉樹的子樹有左右之分,次序不能顛倒。

二叉樹的第i層至多有2的(i-1)次方個結點;深度為k的二叉樹至多有2的k次

10樓:匿名使用者

樹或者森林變成 二叉樹 記住「左孩子,右兄弟」 遍歷的先序中序後序都是針對根而言的 連線都是用指標至於一些公式就參見樓上就行了

請詳細的,易懂的講一下什么是流水線冒險

詳細來說,造成流水線阻塞的原因可以分為三類,結構相關 資料相關和控制相關。要易懂的話,其實 冒險 這個詞容易讓人不懂。說白了就是,流水線因為結構相關的原因而產生了阻塞就叫結構冒險,因為控制相關的原因而產生了阻塞就叫控制冒險。所以,流水線冒險的意思就是流水線發生了阻塞。所謂流水線,就是cpu裡的各種功...

請介紹一下有關馭龍氏的事情 詳細一些,謝謝

赫拉鐵力 歷史上正式見載於經傳和正史文獻的第一位真正的劉姓人物,是夏朝後期的劉累。關於劉累這個人,自古以來就流傳著許多神祕傳說。這些傳說主要記載於 竹書紀年 左傳 史記 新唐書 和大量劉氏族譜中。據文獻記載,劉累是帝堯陶唐氏的後裔。他的出生很奇特,一生下來兩手手掌中就各有一個特殊的紋飾,看上去分別是...

英語問一下第二題為什麼選b請寫詳細點

這句話是這樣的 such的後面所接的名詞有講究,如果such後面是可數名詞,就要加a,例如such a person 這樣的一個人 如果such後面是不可數名詞或抽象名詞,則後面不加冠詞,既不加a也不加the,既直接寫成such great harm。這裡的such修飾抽象名詞harm,只是harm...