二叉樹的那些使用

在計算機科學中，二叉樹（英語：Binary tree）是每個節點最多只有兩個分支(不存在分支度大於2的節點)的樹結構。通常分支被稱作「左子樹」和「右子樹」。二叉樹的分支具有左右次序，不能顛倒。

二叉樹的第i層至多擁有 2^(i-1) 個節點數；深度為k的二叉樹至多總共有 2^(k+1) - 1 個節點數，而總計擁有節點數匹配的，稱為「滿二叉樹」；深度為k有n個節點的二叉樹，當且僅當其中的每一節點，都可以和同樣深度k的滿二叉樹，序號為1到n的節點一對一對應時，稱為「完全二叉樹」。對任何一棵非空的二叉樹T，如果其葉片(終端節點)數為n0，分支度為2的節點數為n2，則n0 = n2 + 1。

與普通樹不同，普通樹的節點個數至少為1，而二叉樹的節點個數可以為0；普通樹節點的最大分支度沒有限制，而二叉樹節點的最大分支度為2；普通樹的節點無左、右次序之分，而二叉樹的節點有左、右次序之分。

二叉樹通常作為數據結構應用，典型用法是對節點定義一個標記函數，將一些值與每個節點相關係。這樣標記的二叉樹就可以實現二叉查找樹和二元堆積，並應用於高效率的搜索和排序。

相對於普通二叉樹，還有一些特殊二叉樹，它們誕生於特殊的場景需求。例如，二叉搜索樹就是因搜索需求而誕生的一種特殊的樹。

具體可以參見

本文初衷是因為Homebrew 的作者@Max Howell的一條twitter

Google: 90% of our engineers use the software you wrote (Homebrew), but you can』t invert a binary tree on a whiteboard so fuck off.

類型(1)完全二叉樹

若設二叉樹的高度為h，除第 h 層外，其它各層 (1～h-1) 的節點數都達到最大個數，第h層有葉子節點，並且葉子節點都是從左到右依次排布，這就是完全二叉樹。

(2)滿二叉樹

除了葉節點外每一個節點都有左右子葉且葉子節點都處在最底層的二叉樹。

(3)平衡二叉樹

平衡二叉樹又被稱為AVL樹（區別於AVL演算法），它是一棵二叉排序樹，且具有以下性質：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，並且左右兩個子樹都是一棵平衡二叉樹。

相關術語

樹的節點：包含一個數據元素及若干指向子樹的分支。

孩子節點：節點的子樹的根稱為該節點的孩子。

雙親節點：B 節點是A 節點的孩子，則A節點是B 節點的雙親。

兄弟節點：同一雙親的孩子節點；

堂兄節點：同一層上節點。

祖先節點: 從根到該節點的所經分支上的所有節點。

子孫節點：以某節點為根的子樹中任一節點都稱為該節點的子孫。

節點層：根節點的層定義為1；根的孩子為第二層節點，依此類推。

樹的深度：樹中最大的節點層。

節點的度：節點子樹的個數。

樹的度： 樹中最大的節點度。

葉子節點：也叫終端節點，是度為 0 的節點。

分支節點：度不為0的節點。

有序樹：子樹有序的樹，如：家族樹。

無序樹：不考慮子樹的順序。

樹的結構#import /** 二叉樹節點 */ @interface DDBinaryTreeNode : NSObject /** 值 */ @property (nonatomic, assign) NSInteger value; /** 左節點 */ @property (nonatomic, strong) DDBinaryTreeNode *leftNode; /** 右節點 */ @property (nonatomic, strong) DDBinaryTreeNode *rightNode; @end樹的遍歷

遍歷是對樹的一種最基本的運算，所謂遍歷二叉樹，就是按一定的規則和順序走遍二叉樹的所有節點，使每一個節點都被訪問一次，而且只被訪問一次。由於二叉樹是非線性結構，因此，樹的遍歷實質上是將二叉樹的各個節點轉換成為一個線性序列來表示。

設L、D、R分別表示遍歷左子樹、訪問根節點和遍歷右子樹， 則對一棵二叉樹的遍歷有三種情況：DLR（稱為先序遍歷），LDR（稱為中序遍歷），LRD （稱為後序遍歷）。

先序遍歷+ (void)preOrderTraverseTree:(DDBinaryTreeNode *)rootNode handler:(void(^)(DDBinaryTreeNode *treeNode))handler { if (!rootNode) { return; } if (handler) { handler(rootNode); } [self preOrderTraverseTree:rootNode.leftNode handler:handler]; [self preOrderTraverseTree:rootNode.rightNode handler:handler]; }中序遍歷+ (void)inOrderTraverseTree:(DDBinaryTreeNode *)rootNode handler:(void (^)(DDBinaryTreeNode *treeNode))handler { if (!rootNode) { return; } [self inOrderTraverseTree:rootNode.leftNode handler:handler]; if (handler) { handler(rootNode); } [self inOrderTraverseTree:rootNode.rightNode handler:handler]; }後序遍歷+ (void)postOrderTraverseTree:(DDBinaryTreeNode *)rootNode handler:(void(^)(DDBinaryTreeNode *treeNode))handler { if (!rootNode) { return; } [self postOrderTraverseTree:rootNode.leftNode handler:handler]; [self postOrderTraverseTree:rootNode.rightNode handler:handler]; if (handler) { handler(rootNode); } }廣度優先遍歷(Breadth First Search)

從根節點開始，沿著樹的寬度遍歷樹的節點。如果所有節點均被訪問，則演算法中止。

按照從上到下、從左到右的次序進行遍歷。先遍歷完一層，再遍歷下一層。

+ (void)levelTraverseTree:(DDBinaryTreeNode *)rootNode handler:(void(^)(DDBinaryTreeNode *treeNode))handler { if (!rootNode) { return; } NSMutableArray *queueArray = [NSMutableArray array]; //數組當成隊列 [queueArray addObject:rootNode]; //壓入根節點 while (queueArray.count > 0) { DDBinaryTreeNode *node = [queueArray firstObject]; if (handler) { handler(node); } [queueArray removeObjectAtIndex:0]; //彈出最前面的節點，仿照隊列先進先出原則 if (node.leftNode) { [queueArray addObject:node.leftNode]; //壓入左節點 } if (node.rightNode) { [queueArray addObject:node.rightNode]; //壓入右節點 } } }深度優先遍歷(Depth First Search)

DFS是搜索演算法的一種。它沿著樹的深度遍歷樹的節點，儘可能深的搜索樹的分支。

當節點v的所有邊都己被探尋過，搜索將回溯到發現節點v的那條邊的起始節點。這一過程一直進行到已發現從源節點可達的所有節點為止。

如果還存在未被發現的節點，則選擇其中一個作為源節點並重複以上過程，整個進程反覆進行直到所有節點都被訪問為止。

+ (void)depthTraverseTree:(DDBinaryTreeNode *)rootNode handler:(void(^)(DDBinaryTreeNode *treeNode))handler { if (!rootNode) { return; } if (handler) { handler(rootNode); } [self depthTraverseTree:rootNode.leftNode handler:handler]; [self depthTraverseTree:rootNode.rightNode handler:handler]; }樹的翻轉

翻轉二叉樹，又叫求二叉樹的鏡像，就是把二叉樹的左右子樹對調。

+ (DDBinaryTreeNode *)invertBinaryTree:(DDBinaryTreeNode *)rootNode { if (!rootNode) { return nil; } if (!rootNode.leftNode && !rootNode.rightNode) { return rootNode; } [self invertBinaryTree:rootNode.leftNode]; [self invertBinaryTree:rootNode.rightNode]; DDBinaryTreeNode *tempNode = rootNode.leftNode; rootNode.leftNode = rootNode.rightNode; rootNode.rightNode = tempNode; return rootNode; }樹的查找+ (DDBinaryTreeNode *)searchTreeNodeWithValue:(NSInteger)value inTree:(DDBinaryTreeNode *)rootNode { if (!rootNode) { return nil; } if (rootNode.value == value) { return rootNode; } if (value

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！