C語言中文網 目錄
首頁 > 編程筆記 > C++筆記 閱讀:306

什么是二叉樹,二叉樹及其應用

二叉樹是一個結點的集合,其中每個結點最多與兩個后繼結點相關聯,分別稱為左側子結點和右側子結點。二叉樹中的每個結點并不是全都有兩個子結點,也可能只有一個結點或兩個結點都可能被省略。在二叉樹中,沒有子結點的結點稱為葉結點

包含子結點的結點稱為其子結點的父結點。對于一個定義為二叉樹的非空的結點集合,每個結點必須至多有一個父結點,并且必須有一個結點是沒有父結點的。這個沒有父結點的結點稱為二叉樹的根結點。一個空的結點集合可以構成一個空的二叉樹。

鏈表和二叉樹有一些相似之處。二叉樹的根對應于鏈表的頭部,二叉樹結點的子結點對應于鏈表中的后繼結點,二叉樹結點的父結點對應于鏈表中結點的前驅結點。當然,空鏈表的模擬是空的二叉樹。

二叉樹的實現

二叉樹可用于將值存儲到其結點中。因此,二叉樹中的結點就是一個結構或類對象,它包含一個用于存儲值的成員,以及另外兩個指向該結點的左側和右側子結點的成員:
struct TreeNode
{
    int value;
    TreeNode *left;
    TreeNode *right;
};
二叉樹本身就是由指向根結點的指針所代表的。圖 1 給出了一個二叉樹示例,其中未顯示結點中存儲的值。如果該結點不具有相應的子結點,則結點中的 left 指針或 right 指針將設置為 nullptr。

二叉樹示意圖
圖 1 二叉樹示意圖

二叉樹之所以稱為樹,是因為它們類似于倒置的樹。任何非空樹都可以分為根結點、左子樹和右子樹。直觀地看,子樹就是從一個特定的結點向下的樹的整個分支。圖 2 顯示了如圖 1 所示二叉樹的左子樹。

非空二叉樹可以分為根結點、左子樹和右子樹
圖 2 非空二叉樹可以分為根結點、左子樹和右子樹

二叉樹的應用

對于任何線性數據結構(如數組或標準鏈表)來說,如果在其結構體中保存了大量信,那么在搜索其數據時速度會較慢,這是因為線性數據結構的連續性所致。

反觀二叉樹及其相似概念的結構則不同,它們是可用于大量信息搜索的優秀數據結構。它們常用于數據庫應用程序,以組織鍵值,建立對數據庫記錄的索引。當用來方便搜索時,二叉樹稱為二叉搜索樹。

信息存儲在二叉搜索樹中,將使樹中的信息搜索變得簡單。例如,來看圖 3 中的二叉搜索樹示例。

二叉搜索樹示例
圖 3 二叉搜索樹示例

該圖描繪了一個二叉搜索樹,每個結點存儲了一個字母,根結點保存的是字母 M。根結點的左側子結點保存了字母 F,右側子結點保存的是 R。

事實上,在二叉搜索樹中,結點左側的所有結點的值都小于結點的值。同樣,結點右側的所有結點的值都大于結點的數據。

當應用程序搜索二叉搜索樹時,它將從根結點開始。如果根結點不包含搜索值,則根據搜索值是小于還是大于根結點的值,應用程序會相應分支到左側或右側子結點。這個過程一直持續到找到值或者確定搜索值不在樹中。圖 4 顯示了在所顯示的二叉樹中查找字母 P 的搜索模式。

在二叉樹中查找字母 P
圖 4 在二叉樹中查找字母 P

這種搜索二叉樹的方式讓人想起在排序的數組上使用的二分搜索技術。假設二叉樹是平衡的(意味著在每個結點處,左右子樹的結點數大致相同),則搜索將在每一步中將剩余要搜索的樹的大小減小一半,這使得在相對較少的步驟中搜索包含大量信息的樹成為可能。

精美而實用的網站,提供C語言C++STLLinuxShellJavaGo語言等教程,以及socketGCCviSwing設計模式JSP等專題。

Copyright ?2011-2018 biancheng.net, 陜ICP備15000209號

底部Logo