什么是二叉樹

本篇內容介紹了“什么是二叉樹 ”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！

什么是二叉樹：

二叉樹有兩個節點 分別是左子節點和右子節點

二叉樹中葉子節點全在最底層，除了葉子節點外每個節點都有左右兩個子節點，這種二叉樹叫做滿二叉樹。

葉子節點在最底下兩層，最后一層的葉子節點都靠左排列，并且除了最后一層，其他層的節點個數都要達到最大，這種二叉樹叫做完全二叉樹。

=======================================================

如何存儲（表示）一顆二叉樹？
1 鏈式存儲法： 每個節點有三個字段，其中一個節點存儲數據，另外兩個指向左右子節點的指針。

2 基于數組的順序存儲法：根節點存儲在下標為i=1的位置，左子節點存儲在下標2*i=2的位置，右子節點存儲在2*i+1=2*2+1=5的位置。 所以節點x存儲在數組中下標為i的位置，下標2*i的位置存儲的就是左子節點，下標2*i+1的位置存儲的就是右子節點。 

所以如果該二叉樹是一顆完全二叉樹，那么用數組來存儲是最節省內存的一種方式，因為數組的存儲方式并不像鏈式存儲那樣需要存儲額外的左右子節點的指針，這也是為什么完全二叉樹輝單獨列出來的原因。

二叉樹的遍歷包括 前序遍歷  中序遍歷和后序遍歷。二叉樹的遍歷其實是一個遞歸的過程。遍歷的時間復雜度為O（n）。

==========================================================

二叉查找樹：二叉查找樹就是為了實現快速查找而生的，不僅可以快速查找一個數據，還支持快速插入、刪除一個數據。

二叉樹的查找操作： 我們先取根節點，如果它等于我們要查找的數據，那就返回，如果查找的數據比根節點的值小，那么在左子樹中遞歸查找。如果要查找的數據比根節點的值大，那么就在右子樹中遞歸查找。

二叉樹的插入操作： 如果要插入的數據比節點數據大，并且節點的右子樹為空，就將新數據直接插入右子節點的位置，如果不為空，就再遍歷遞歸右子樹，查找插入位置。同理，要插入的數據比節點數值小，并且節點的左子樹為空，就將新數據插入到左子樹的位置，如果不為空，就遍歷左子樹找到插入的位置。

二叉樹的刪除操作： 有三種情況   1 如果要刪除的節點沒有子節點，只需要將父節點中指向要刪除的節點的指針設置為null。   2 如果要刪除的節點只有一個子節點，只需要更新父節點中，指向要刪除節點的指針，讓它指向要刪除節點的子節點就可以了。  3 如果要刪除的節點有兩個子節點，我們需要找到這個節點的右子樹的最小節點，把它替換到要刪除的節點，然后再刪除掉這個最小節點，因為最小節點肯定沒有左子節點。

時間復雜度： 不管是插入、刪除還是查找，時間復雜度都是跟樹的高度成正比，也就是O（height） 這樣問題就轉換成了如何求一顆包含n個節點的完全二叉樹的高度。樹的高度為最大層數減一，為了方便計算，轉換為層來表示。在完全二叉樹中，第一層有1個節點，第二層有2個節點，第三層有4個節點。  下面一層節點個數是上一次的二倍，第k層包含節點個數是2^(k-1)個。最后一層節點個數在1到2^(L-1)個之間。平衡二叉樹的高度接近logn，所以插入 刪除 查找操作的時間復雜度也比較穩定，是O（logn）。

===========================================================

紅黑樹 

平衡二叉樹：二叉樹中任意一個節點的左右子樹的高度相差不能大于1。完全二叉樹，滿二叉樹都是平衡二叉樹。

平衡二叉樹中平衡的意思就是讓整棵樹看起來比較對稱，比較平衡，不要出現左子樹很高，右子樹很矮的情況。這樣就可以讓整棵樹的高度相對來說低一些，相應的插入、刪除、查找等操作效率更高些。

紅黑樹定義：1 根節點是黑色的

                      2 每個葉子節點都是黑色的空節點，，也就是說葉子節點不存儲數據

                      3 任何相鄰的節點都不能同時為紅色，紅色節點是被黑色節點分開的。

                      4 每個節點從該節點到達其葉子節點的所有路徑，都包含相同數目的黑色節點。

工程中為什么都喜歡用紅黑樹？

堆和棧在絕大多數情況下，操作的效率很高，但也無法避免極端情況下時間復雜度的退化，盡管概率不大，ALV樹是一種高度的平衡二叉樹，查找效率非常高，但是有利有弊，ALV樹為了維持這種高度的平衡，就要付出很大的代價，每次的插入、刪除都要做調整，會比較復雜，耗時，所以堆有頻繁的插入、刪除等操作的數據集合，使用ALV樹的代價就比較高了。而紅黑樹只是做到了近似平衡而非真正的平衡，所以在維護成本上就i比ALV樹要低一些。所以紅黑樹的插入、刪除、查找等操作都比較穩定，在工程中需要面對各種情況，所以更傾向于這種穩定性能的二叉查找樹。

“什么是二叉樹 ”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！