二叉树的相关算法实现

29次阅读

共计 1684 个字符,预计需要花费 5 分钟才能阅读完成。

定义树的节点

    typedef struct TreeNode {
        int data;
        struct TreeNode *leftChild;
        struct TreeNode *RightChild;
    } TreeNode;

创建树


 /**
 *          1
 *        /   \
 *       2     3
 *      /\    /
 *     4  5  6
 */

        TreeNode *root = malloc(sizeof(TreeNode));
        root->data = 1;
        
        TreeNode *node1 = malloc(sizeof(TreeNode));
        node1->data = 2;
        
        TreeNode *node2 = malloc(sizeof(TreeNode));
        node2->data = 3;
        
        TreeNode *node3 = malloc(sizeof(TreeNode));
        node3->data = 4;
        node3->leftChild = NULL;
        node3->RightChild = NULL;
        
        TreeNode *node4 = malloc(sizeof(TreeNode));
        node4->data = 5;
        node4->leftChild = NULL;
        node4->RightChild = NULL;
        
        TreeNode *node5 = malloc(sizeof(TreeNode));
        node5->data = 6;
        node5->leftChild = NULL;
        node5->RightChild = NULL;
        
        root->leftChild = node1;
        root->RightChild = node2;
        
        node1->leftChild = node3;
        node1->RightChild = node4;
        
        node2->leftChild = node5;
        node2->RightChild= NULL;

前序遍历

    // 前序遍历 根 -> 左 -> 右
    void preorderTraverse(TreeNode *tree, NSMutableArray *arrayM) {if(tree == NULL) {return;}
        [arrayM addObject:@(tree->data)];// 记录节点
        preorderTraverse(tree->leftChild, arrayM);
        preorderTraverse(tree->RightChild, arrayM);
    }

中序遍历

// 中序遍历 左 -> 根 -> 右
    void midTraverse(TreeNode *tree, NSMutableArray *arrayM) {if(tree == NULL) {return;}
        midTraverse(tree->leftChild, arrayM);
        [arrayM addObject:@(tree->data)];// 记录节点
        midTraverse(tree->RightChild, arrayM);
    }

后序遍历

    // 后序遍历 左 -> 右 -> 根
    void postorderTraversal(TreeNode *tree, NSMutableArray *arrayM) {if(tree == NULL) {return;}
        postorderTraversal(tree->leftChild, arrayM);
        postorderTraversal(tree->RightChild, arrayM);
        [arrayM addObject:@(tree->data)];// 记录节点
    }

输出遍历后的节点

            NSMutableArray *arrayM = [NSMutableArray array];
            preorderTraverse(root, arrayM);
            NSLog(@"%@",arrayM);// 124536
            
            NSMutableArray *arrayM1 = [NSMutableArray array];
            midTraverse(root, arrayM1);
            NSLog(@"%@",arrayM1);//425163
            
            NSMutableArray *arrayM2 = [NSMutableArray array];
            postorderTraversal(root, arrayM2);
            NSLog(@"%@",arrayM2);// 452631

正文完
 0