日韩伦理无码,欧美操逼逼一区二区,日本一久操操免费

一前序遍歷(Preorder Traversal)

訪問順序：`根節(jié)點，前序遍歷左子樹，前序遍歷右``子樹

image.png

遍歷順序: [7]，[4，2，1，3，5]，[9，8，11，10，12]

帶[]表示分割為根節(jié)點，左子樹節(jié)點，右子樹節(jié)點，下面類似

代碼實現(xiàn) - 遞歸

/// 前序遍歷
- (void)preorder:(TreeNode *)node {
    if (node == nil) {
        return;
    }
    
    NSLog(@"%@",node.description);
    [self preorder:node.left];
    [self preorder:node.right];
}

測試代碼

/// 前序遍歷
- (void)preorder {
    NSArray *data = @[@7,@4,@9,@2,@5,@8,@11,@1,@3,@10,@12];
    
    BinarySearchTree *tree = [[BinarySearchTree alloc] init];
    for (int i = 0; i < data.count; i++) {
        [tree add:data[i]];
    }
    
    [tree preordr];
}

運行結(jié)果

前序遍歷.png

二中序遍歷(Inorder Traversal)

訪問順序：中序遍歷左子樹，根節(jié)點，中序遍歷右子樹

上圖中序遍歷結(jié)果：[1，2，3，4，5]，[7]，[8，9，10，11，12]

2.1 擴展

如果將訪問順序調(diào)整為：中序遍歷右子樹，根節(jié)點，中序遍歷左子樹

遍歷結(jié)果：[12，11，10，9，8]，[7]，[5，4，3，2，1]

總結(jié)：二叉搜索樹的中序遍歷結(jié)果是升序或者降序的

代碼實現(xiàn) - 遞歸

/// 中序遍歷
- (void)inorder:(TreeNode *)node {
    if (node == nil) {
        return;
    }
    [self inorder:node.left];
    NSLog(@"%@",node.description);
    [self inorder:node.right];
}

測試代碼

/// 中序遍歷
- (void)Inorder {
    NSArray *data = @[@7,@4,@9,@2,@5,@8,@11,@1,@3,@10,@12];
    
    BinarySearchTree *tree = [[BinarySearchTree alloc] init];
    for (int i = 0; i < data.count; i++) {
        [tree add:data[i]];
    }
    
    [tree inorder];
}

運行結(jié)果

中序遍歷.png

三后序遍歷(Postorder Traversal)

訪問順序：后序遍歷左子樹，后序遍歷右子樹，根節(jié)點

上圖后序遍歷結(jié)果:
[1，3，2，5，4]，[8，10，12，11，9]，[7]

代碼實現(xiàn) - 遞歸

/// 后序遍歷
- (void)postorder:(TreeNode *)node {
    if (node == nil) {
        return;
    }
    [self postorder:node.left];
    [self postorder:node.right];
    NSLog(@"%@",node.description);
}

測試代碼

/// 后序遍歷
- (void)postorder {
    NSArray *data = @[@7,@4,@9,@2,@5,@8,@11,@1,@3,@10,@12];
    
    BinarySearchTree *tree = [[BinarySearchTree alloc] init];
    for (int i = 0; i < data.count; i++) {
        [tree add:data[i]];
    }
    
    [tree postorder];
}

運行結(jié)果：

后序遍歷.png

四層序遍歷(Level Order Traversal)

訪問順序：從上到下，從左到右，依次訪問每一個節(jié)點
上圖遍歷結(jié)果：[7]，[4，9]，[2，5，8，11]，[1，3，10，12]

實現(xiàn)思路：使用隊列

1. 將根節(jié)點入隊
2. 循環(huán)執(zhí)行以下操作，直到隊列為空
2.1 將隊頭節(jié)點A出隊，進行訪問
2.2 將A的左子節(jié)點入隊
2.3 將A的右子節(jié)點入隊

代碼實現(xiàn) - 迭代

/// 層序遍歷
- (void)levelOrder {
    if (_root == nil) {
        return;
    }
    
    Queue *queue = [[Queue alloc] init];
    [queue enQueue:_root];
    
    while (!queue.isEmpty) {
        TreeNode *node = [queue deQueue];
        NSLog(@"%@",node.description);
        
        if (node.left != nil) { // 左子節(jié)點入隊
            [queue enQueue:node.left];
        }
        
        if (node.right != nil) {    // 右子節(jié)點入隊
            [queue enQueue:node.right];
        }
    }
}

測試代碼

/// 層序遍歷
- (void)levelOrder {
    NSArray *data = @[@7,@4,@9,@2,@5,@8,@11,@1,@3,@10,@12];
    
    BinarySearchTree *tree = [[BinarySearchTree alloc] init];
    for (int i = 0; i < data.count; i++) {
        [tree add:data[i]];
    }
    
    [tree levelOrder];
}

運行結(jié)果：

層序遍歷.png

五遍歷的作用

前序遍歷：樹狀結(jié)構(gòu)展示（注意左右子樹的順序）
中序遍歷：二叉搜索樹的中序遍歷按升序或者降序處理節(jié)點
后序遍歷：適用于一些先子后父的操作
層序遍歷：計算二叉樹的高度，判斷一棵樹是否為完全二叉樹

六根據(jù)遍歷結(jié)果重構(gòu)二叉樹

6.1 以下結(jié)果可以保證重構(gòu)出唯一的一棵二叉樹

前序遍歷 + 中序遍歷
后序遍歷 + 中序遍歷

image.png

6.2 前序遍歷 + 后序遍歷

如果它是一棵真二叉樹，結(jié)果是唯一的
不然結(jié)果不唯一

image.png

即左子樹和右子樹的分割點難以確認

七前序遍歷 + 中序遍歷重構(gòu)二叉樹

八利用前序遍歷樹狀打印二叉樹

代碼實現(xiàn)如下

- (NSString *)description {
    NSMutableString *strM = [NSMutableString stringWithString:@"\n"];
    NSMutableString *prefix = [NSMutableString string];
    [self toString:_root strM:strM prefix:prefix];
    return strM.copy;
}

- (void)toString:(TreeNode *)node strM:(NSMutableString *)strM prefix:(NSMutableString *)prefix {
    if (node == nil) {
        return;
    }
    
    // 前序遍歷二叉樹
    [self toString:node.left strM:strM prefix:[NSMutableString stringWithFormat:@"%@%@",prefix,@"L_"]];
    [strM appendString:[NSString stringWithFormat:@"%@%@ \n",prefix,node.element]];
    [self toString:node.right strM:strM prefix:[NSMutableString stringWithFormat:@"%@%@",prefix,@"R_"]];
}

測試代碼

/// 利用前序遍歷樹狀打印二叉樹
- (void)printBinarySearchTree {
    NSArray *data = @[@7,@4,@9,@2,@5,@8,@11,@1,@3,@10,@12];
    
    BinarySearchTree *tree = [[BinarySearchTree alloc] init];
    for (int i = 0; i < data.count; i++) {
        [tree add:data[i]];
    }
    
    NSLog(@"%@",tree.description);
}

運行結(jié)果

image.png

九翻轉(zhuǎn)二叉樹

226. 翻轉(zhuǎn)二叉樹

示例：

輸入：

     4
   /   \
  2     7
 / \   / \
1   3 6   9

輸出：

     4
   /   \
  7     2
 / \   / \
9   6 3   1

代碼實現(xiàn)如下

十計算二叉樹的高度

遞歸實現(xiàn)

/// 計算二叉樹的高度 - 遞歸實現(xiàn)
- (int)getHeight {
    return [self height:_root];
}

- (int)height:(TreeNode *)node {
    if (node == nil) {
        return 0;
    }
    return 1 + MAX([self height:node.left], [self height:node.right]);
}

迭代實現(xiàn)

/// 計算二叉樹的高度 - 迭代實現(xiàn) - 層序遍歷
- (int)getHeight2 {
    if (_root == nil) {
        return 0;
    }
    
    int height = 0; // 樹的高度
    int levelSize = 1;  // 存儲著每一層的元素數(shù)量
    
    Queue *qu = [[Queue alloc] init];
    [qu enQueue:_root];
    
    // 遍歷隊列
    while (!qu.isEmpty) {
        TreeNode *node = qu.deQueue;
        levelSize--;
        
        if (node.left != nil) {
            [qu enQueue:node.left];
        }
        
        if (node.right != nil) {
            [qu enQueue:node.right];
        }
        
        if (levelSize == 0) {   // // 意味著即將要訪問下一層
            levelSize = qu.size;
            height++;
        }
    }
    
    return height;
}

測試代碼

/// 計算二叉樹的高度
- (void)getTreeHeight {
    NSArray *data = @[@7,@4,@9,@2,@5,@8,@11,@1,@3,@10,@12];
    
    BinarySearchTree *tree = [[BinarySearchTree alloc] init];
    for (int i = 0; i < data.count; i++) {
        [tree add:data[i]];
    }
    
    NSLog(@"遞歸:%d",[tree getHeight]);
    NSLog(@"遞歸:%d",[tree getHeight2]);
}

運行結(jié)果

二叉樹高度.png

十一判斷一棵樹是否為完全二叉樹

實現(xiàn)原理

1. 如果樹為空，返回 false
2. 如果樹不為空，開始層序遍歷二叉樹（使用隊列）
  2.1 如果node.left != nil && node.right != nil，將node.left，node.right按順序入隊列
  2.2 如果node.left == nil && node.right != nil，返回false
  2.3 如果node.left != nil && node.right == nil 或者 node.left == nil && node.right == nil，那么
    2.3.1 后面遍歷的節(jié)點都應(yīng)該為葉子節(jié)點，才是完全二叉樹
    2.3.2 否則返回 false
  2.4 遍歷結(jié)果，返回 true

代碼實現(xiàn)如下

/// 是否為完全二叉樹
- (BOOL)isComplteBinaryTree {
    if (_root == nil) {
        return false;
    }
    
    Queue *qu = [[Queue alloc] init];
    [qu enQueue:_root];
    
    BOOL leaf = false;  // 是否為葉子節(jié)點
    while (!qu.isEmpty) {
        TreeNode *node = qu.deQueue;
        
        if (leaf && !node.isLeaf) { // 處于最后一層了,要求是葉子節(jié)點才可以
            return false;
        }
        
        if (node.hasTwoChildren) {  // 有左右子樹 - 都入隊
            [qu enQueue:node.left];
            [qu enQueue:node.right];
        } else if (node.left == nil && node.right != nil) { // 如果只有一個葉子節(jié)點,必須在左邊才行
            return false;
        } else {    // 后面遍歷的節(jié)點都必須是葉子節(jié)點
            leaf = true;
        }
    }
    
    return true;
}

測試代碼

/// 是否為完全二叉樹
- (void)isComplteBinaryTree {
    NSArray *data = @[@7,@4,@9,@2,@5,@8,@11,@1,@3,@10,@12];
    NSArray *data1 = @[@7,@4,@9,@2,@5,@8,@11];
    NSArray *data2 = @[@7,@4,@9,@2,@5,@8,@11,@1];
    
    BinarySearchTree *tree = [[BinarySearchTree alloc] init];
    for (int i = 0; i < data.count; i++) {
        [tree add:data[i]];
    }
    BinarySearchTree *tree1 = [[BinarySearchTree alloc] init];
    for (int i = 0; i < data1.count; i++) {
        [tree1 add:data1[i]];
    }
    BinarySearchTree *tree2 = [[BinarySearchTree alloc] init];
    for (int i = 0; i < data2.count; i++) {
        [tree2 add:data2[i]];
    }
    NSLog(@"%d",[tree isComplteBinaryTree]);
    NSLog(@"%d",[tree1 isComplteBinaryTree]);
    NSLog(@"%d",[tree2 isComplteBinaryTree]);
}

運行結(jié)果

image.png

為了快速構(gòu)建二叉樹，可以將數(shù)組的元素按照層序遍歷的順序排列好

更多詳細代碼請看項目鏈接

十二前驅(qū)節(jié)點（predecessor）

前驅(qū)節(jié)點：中序遍歷時的前一個節(jié)點

如果是二叉搜索樹，前驅(qū)節(jié)點就是前一個比它小的節(jié)點

視圖.png

分為以下情況分別講解

12.1 node.left != nil

舉例：6，13，8
則查找它的前驅(qū)節(jié)點算法為

predecessor = node.left.right.right.right ...
終止條件：right = nil

12.2 node.left == nil && node.parent != nil

舉例：7，11，9，1
則查找它的前驅(qū)節(jié)點算法為

predecessor = node.parent.parent.parent ...
終止條件：node在parent的右子樹中

12.3 node.left == nil && node.parent == nil

那就沒有前驅(qū)節(jié)點
舉例：沒有左子樹的根節(jié)點

代碼實現(xiàn)

/// 找前驅(qū)節(jié)點
- (TreeNode *)predecessor:(TreeNode *)node {
    if (node == nil) {
        return nil;
    }
    
    /** 1.左子樹不為空
        前驅(qū)節(jié)點在左子樹當中（left.right.right.right....）
     */
    TreeNode *p = node.left;
    if (p != nil) {
        while (p.right != nil) {
            p = p.right;
        }
        return p;
    }
    
    /** 2.左子樹為空,父節(jié)點不為空
        從父節(jié)點、祖父節(jié)點中尋找前驅(qū)節(jié)點
     */
    while (node.parent != nil && node == node.parent.left) {
        node = node.parent;
    }
    
    // node.parent == null
    // node == node.parent.right
    return node.parent;
}

測試代碼

// 找前驅(qū)節(jié)點
- (void)predecessor {
    NSArray *data = @[@8,@4,@13,@2,@6,@10,@1,@3,@5,@7,@9,@12,@11];
    
    BinarySearchTree *tree = [[BinarySearchTree alloc] init];
    for (int i = 0; i < data.count; i++) {
        [tree add:data[i]];
    }
    
    NSLog(@"二叉樹為\n %@",tree.description);
    
    NSArray *data1 = @[@6,@13,@8,@7,@11,@9,@1];
    for (int i = 0; i < data1.count; i++) {
        TreeNode *node = [tree node:data1[i]];
        NSLog(@"%@的前驅(qū)節(jié)點:%@",node.element,[tree predecessor:node].element);
    }
}

運行結(jié)果如下

找前驅(qū)節(jié)點.png

十三后繼節(jié)點（succesor）

后繼節(jié)點：中序遍歷時的后一個節(jié)點

如果是二叉搜索樹，前驅(qū)節(jié)點就是前一個比它大的節(jié)點

二叉樹.png

分為以下情況分別講解

13.1 node.right != nil

舉例：1，8，4
則查找它的后繼節(jié)點算法為

successor = node.right.left.left.left ...
終止條件：left = nil

13.2 node.right == nil && node.parent != nil

舉例：7，6，3，11
則查找它的后繼節(jié)點算法為

successor = node.parent.parent.parent ...
終止條件：node在parent的左子樹中

13.3 node.right == nil && node.parent == nil

那就沒有后繼節(jié)點
舉例：沒有右子樹的根節(jié)點

代碼實現(xiàn)如下

/// 找后繼節(jié)點
- (TreeNode *)successor:(TreeNode *)node {
    if (node == nil) {
        return nil;
    }
    
    /** 1.右子樹不為空
        前驅(qū)節(jié)點在左子樹當中（node.right.left.left.left....）
     */
    TreeNode *p = node.right;
    if (p != nil) {
        while (p.left != nil) {
            p = p.left;
        }
        return p;
    }
    
    /** 2.右子樹為空,父節(jié)點不為空
        從父節(jié)點、祖父節(jié)點中尋找前驅(qū)節(jié)點
     */
    while (node.parent != nil && node == node.parent.right) {
        node = node.parent;
    }
    
    return node.parent;
}

測試代碼如下

// 找后繼節(jié)點
- (void)successor {
    NSArray *data = @[@4,@1,@8,@2,@7,@10,@3,@5,@9,@11,@6];
    
    BinarySearchTree *tree = [[BinarySearchTree alloc] init];
    for (int i = 0; i < data.count; i++) {
        [tree add:data[i]];
    }
    
    NSLog(@"二叉樹為\n %@",tree.description);
    
    NSArray *data1 = @[@1,@8,@4,@7,@6,@3,@11];
    for (int i = 0; i < data1.count; i++) {
        TreeNode *node = [tree node:data1[i]];
        NSLog(@"%@的后繼節(jié)點:%@",node.element,[tree successor:node].element);
    }
}

運行結(jié)果：

找后繼節(jié)點.png

本文會持續(xù)更新中，更多精彩內(nèi)容敬請期待。

本文參考 MJ老師的戀上數(shù)據(jù)結(jié)構(gòu)與算法

《戀上數(shù)據(jù)結(jié)構(gòu)與算法一》筆記

本人技術(shù)水平有限，如有錯誤歡迎指正。
書寫整理不易，您的打賞點贊是對我最大的支持和鼓勵，歡迎點贊打賞。

項目連接鏈接 - 09_Tree

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

《戀上數(shù)據(jù)結(jié)構(gòu)與算法一》筆記（七）二叉樹遍歷

《戀上數(shù)據(jù)結(jié)構(gòu)與算法一》筆記（七）二叉樹遍歷

目錄

一前序遍歷(Preorder Traversal)

二中序遍歷(Inorder Traversal)

2.1 擴展

三后序遍歷(Postorder Traversal)

四層序遍歷(Level Order Traversal)

五遍歷的作用

六根據(jù)遍歷結(jié)果重構(gòu)二叉樹

6.1 以下結(jié)果可以保證重構(gòu)出唯一的一棵二叉樹

6.2 前序遍歷 + 后序遍歷

七前序遍歷 + 中序遍歷重構(gòu)二叉樹

八利用前序遍歷樹狀打印二叉樹

九翻轉(zhuǎn)二叉樹

226. 翻轉(zhuǎn)二叉樹

十計算二叉樹的高度

十一判斷一棵樹是否為完全二叉樹

十二前驅(qū)節(jié)點（predecessor）

12.1 node.left != nil

12.2 node.left == nil && node.parent != nil

12.3 node.left == nil && node.parent == nil

十三后繼節(jié)點（succesor）

13.1 node.right != nil

13.2 node.right == nil && node.parent != nil

13.3 node.right == nil && node.parent == nil

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

《戀上數(shù)據(jù)結(jié)構(gòu)與算法一》筆記（七）二叉樹遍歷

目錄

一 前序遍歷(Preorder Traversal)

二 中序遍歷(Inorder Traversal)

2.1 擴展

三 后序遍歷(Postorder Traversal)

四 層序遍歷(Level Order Traversal)

五 遍歷的作用

六 根據(jù)遍歷結(jié)果重構(gòu)二叉樹

6.1 以下結(jié)果可以保證重構(gòu)出唯一的一棵二叉樹

6.2 前序遍歷 + 后序遍歷

七 前序遍歷 + 中序遍歷重構(gòu)二叉樹

八 利用前序遍歷樹狀打印二叉樹

九 翻轉(zhuǎn)二叉樹

226. 翻轉(zhuǎn)二叉樹

十 計算二叉樹的高度

十一 判斷一棵樹是否為完全二叉樹

十二 前驅(qū)節(jié)點（predecessor）

12.1 node.left != nil

12.2 node.left == nil && node.parent != nil

12.3 node.left == nil && node.parent == nil

十三 后繼節(jié)點（succesor）

13.1 node.right != nil

13.2 node.right == nil && node.parent != nil

13.3 node.right == nil && node.parent == nil

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

一前序遍歷(Preorder Traversal)

二中序遍歷(Inorder Traversal)

三后序遍歷(Postorder Traversal)

四層序遍歷(Level Order Traversal)

五遍歷的作用

六根據(jù)遍歷結(jié)果重構(gòu)二叉樹

七前序遍歷 + 中序遍歷重構(gòu)二叉樹

八利用前序遍歷樹狀打印二叉樹

九翻轉(zhuǎn)二叉樹

十計算二叉樹的高度

十一判斷一棵樹是否為完全二叉樹

十二前驅(qū)節(jié)點（predecessor）

十三后繼節(jié)點（succesor）