二叉树的常见算法【黑马java培训】

更新时间:2021年03月18日 08时58分23秒来源:黑马程序员论坛

1.二叉树的遍历算法 二叉树的遍历主要分为三种：先序遍历，中序遍历和后序遍历。还有一种就是按照层次遍历。
按照惯例，左孩子优先于右孩子，那么：
先序遍历指的就是先访问本节点，再访问该节点的左孩子和右孩子；
中序遍历指的就是：先访问左孩子，再访问本节点，最后访问右孩子；
后序遍历指的就是：先访问左右孩子，最后访问本节点。
层次遍历：按照树的每一层(高度)进行遍历。
树的节点的数据结构常声明为：

[Java] 纯文本查看 复制代码

struct TreeNode {
    int val;
    TreeNode *left;     //左孩子节点
    TreeNode *right;    //右孩子节点
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
}

约定给出根节点，分别使用三种遍历方式得到二叉树的序列：得益于递归的简洁性，三种遍历方式的递归算法也是非常简洁和易懂的。
(1). 先序遍历

[Java] 纯文本查看 复制代码

//递归版本
void preOrderTraversal(vector<int> &store, TreeNode *root) {
    if(!root) return;
    store.push_back(root->val);
    preOrderTraversal(store, root->left);   //左孩子优先
    preOrderTraversal(store, root->right);
}

先序遍历的理解：沿着最左侧通路自顶而下访问各个节点，自底而上遍历对应的右子树。迭代版本需要用到栈这种数据结构。

[Java] 纯文本查看 复制代码

//递归版本
void preOrderTraversal(vector<int> &store, TreeNode *root) {
    stack<TreeNode *> S;
    S.push(root);
    while(!S.empty()) {
        TreeNode *curr_node = S.top();
        S.pop();
        if(curr_node) {
            store.push_back(curr_node->val);
            S.push(curr_node->right);   //左孩子优先，所以右孩子先入栈
            S.push(curr_node->left);
        }
    }
    return;
}

(2). 中序遍历

[Java] 纯文本查看 复制代码

//递归版本
void inOrderTraversal(vector<int> &store, TreeNode *root) {
    if(!root) return;
    inOrderTraversal(store, root->left);
    store.push_back(root->val);
    inOrderTraversal(store, root->right);
    return;
}

中序遍历的迭代版本需要借用一个数据结构：栈，使用一个栈来保存，根节点沿着左通路一直往下访问的节点。

[Java] 纯文本查看 复制代码

void inorderTraversal(vector<int> &store, TreeNode* root) {
    strack<TreeNode *> S;
    while(root || !S.empty()) {
        while(root) {
            S.push(root);
            root = root->left;
        }
        TreeNode *curr_node = S.top();
        S.pop();
        store.push_back(curr_node->val);
        root = curr_node->right;
    }
    return;
}

(3). 后序遍历

[Java] 纯文本查看 复制代码

//递归版本
void postOrderTraversal(vector<int> &store, TreeNode *root) {
    if(!root) return;
    postOrderTraversal(store, root->left);  //右孩子优先
    postOrderTraversal(store, root->right);
    store.push_back(root->val);
}

后序遍历的迭代版本和前序遍历类似：
可以证明，右孩子优先的先序遍历序列的逆序列就是左孩子优先的后序遍历序列。
假设根节点的值为a，L1和R1分别是左子树和右子树在右孩子优先的先序遍历序列，L2和R2分别是左子树和右子树在左孩子优先的后序遍历序列，所以只需要证明:序列"a,R1,L1"是序列"L2,R2,a"的逆序列即可。
从序列的组成来看，只需要证明R1是R2的逆序列且L1是L2的逆序列，显然这就将问题分解，平凡的情况下是显然成立的，因此可以归纳证明出这个结论。

[Java] 纯文本查看 复制代码

//迭代版本
void postOrderTraversal(vector<int> &store, TreeNode *root) {
    stack<TreeNode *> S;
    S.push(root);
    while(!S.empty()) {
        TreeNode *curr_node = S.top();
        S.pop();
        if(curr_node) {
            store.push_back(curr_node->val);
            S.push(curr_node->left);    //右孩子优先，所以左孩子先入栈
            S.push(curr_node->right);
        }
    }
    std::reverse(store.begin(), store.end());   //逆序列即为所求
    return;
}

(4). 层次遍历
二叉树的按照层次遍历，需要使用数据结构队列queue，每次出队列的元素，将其左右孩子入队列。

[Java] 纯文本查看 复制代码

//迭代版本
void levelOrderTraversal(vector<int> &store, TreeNode *root) {
    queue<TreeNode *> Q;
    Q.push(root);
    while(!Q.empty()) {
        TreeNode *curr_node = Q.front();
        if(curr_node) {
            store.push(curr_node->val);
            Q.push(curr_node->left);
            Q.push(curr_node->right);
        }
    }
    return;
}

2. 二叉树的其它算法
(1). 二叉树的深度
递归版本非常简洁，也非常易懂；迭代版本则需要利用我们之前介绍的按照层次遍历，层数就是二叉树的深度。

[Java] 纯文本查看 复制代码

//递归版本
int TreeDepth(TreeNode *pRoot) {
    return pRoot ? 1 + max(TreeDepth(pRoot->left),
                           TreeDepth(pRoot->right)) : 0;
}
//迭代版本
int TreeDepth2(TreeNode *pRoot) {
    queue<TreeNode *> Q;
    Q.push(pRoot);
    int depth = 0;
    while(!Q.empty()) {
        int len = Q.size();
        ++depth;
        while(len--) {
            TreeNode *curr_node = Q.front();
            Q.pop();
            if(curr_node) {
                Q.push(curr_node->left);
                Q.push(curr_node->right);
            }
        }
    }
    return depth - 1;   //将叶节点的空孩子节点也算作一层了，所以减1
}

(2). 二叉树的镜像
操作给定的二叉树，将其变换为源二叉树的镜像。使用递归，当节点存在至少一个孩子时，交换左右孩子，再递归处理。

[Java] 纯文本查看 复制代码

//二叉树的镜像
void Mirror(TreeNode *pRoot) {
        if (pRoot && (pRoot->left || pRoot->right)) {
        std::swap(pRoot->left, pRoot->right);
                Mirror(pRoot->left);
        Mirror(pRoot->right);
        }
        return;
}

(3). 平衡二叉树
输入一棵二叉树，判断该二叉树是否是平衡二叉树。
平衡二叉树指的是：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树，见百度百科。关键点：子树的高度差不超过1且子树也是平衡树。构造一个递归函数IsBalanced来判断这两个条件。

[Java] 纯文本查看 复制代码

//平衡二叉树
bool IsBalanced(TreeNode *pRoot, int &pDepth) {
        if (!pRoot) {
                pDepth = 0;
                return true;
        }
        int left_depth, right_depth;    //记录左右子树的高度
        if (IsBalanced(pRoot->left, left_depth) &&
            IsBalanced(pRoot->right, right_depth)) {
                int diff = left_depth - right_depth;
                if (diff <= 1 && diff >= -1) {
                        pDepth = 1 + (left_depth > right_depth ? left_depth : right_depth);
                        return true;
                }
        }
        return false;
}
bool IsBalanced_Solution(TreeNode *pRoot) {
        int pDepth = 0;
        return IsBalanced(pRoot, pDepth);
}

(4). 对称的二叉树
请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

[Java] 纯文本查看 复制代码

//对称的二叉树
bool isSymmetrical(TreeNode *leftChild, TreeNode *rightChild) {
        if (!leftChild && !rightChild) {
                //左右子树同时为空
                return true;
        }
        else if (leftChild && rightChild) {
                //左右子树都不为空
                return leftChild->val == rightChild->val &&
                           isSymmetrical(leftChild->left, rightChild->right) &&
                           isSymmetrical(leftChild->right, rightChild->left);
        }
        else {
                return false;
        }
}
bool isSymmetrical(TreeNode *pRoot) {
        if (!pRoot) return true; 
        return isSymmetrical(pRoot->left, pRoot->right);
}

(5). 把二叉树打印成多行
从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
在求二叉树的深度的时候，迭代解法起始我们已经做了这个事情，只是没有按照多行输出，所以只需要记录每一行的val即可。

[Java] 纯文本查看 复制代码

//把二叉树打印成多行
vector<vector<int>> Print(TreeNode *pRoot) {
        vector<vector<int>> store;
        queue<TreeNode *> Q;
        Q.push(pRoot);
        int index = 0;
        while (!Q.empty()) {
                int length = Q.size();
                store.push_back(vector<int>());
                while (length--) {
                        TreeNode *curr_node = Q.front();
                        Q.pop();
                        if (curr_node) {
                                store[index].push_back(curr_node->val);
                                Q.push(curr_node->left);
                                Q.push(curr_node->right);
                        }
                }
                ++index;
        }
        store.pop_back();   //将叶节点的空孩子节点也算作一层了，所以pop_back()
        return store;
}

(6). 二叉树的下一个结点
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
节点的数据结构表示为：

[Java] 纯文本查看 复制代码

struct TreeLinkNode {
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    struct TreeLinkNode *next;  //父节点
    TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {}
};

若允许一定的空间复杂度，可以直接中序遍历保存序列之后直接查找。这种方法就不介绍了，下面介绍常数空间的算法：
如果该节点有右孩子，必然下一个节点就是该节点的右孩子的沿着左侧链下的最后一个左孩子；
该节点没有右孩子，也没有父节点，说明这个节点是最后一个节点；
该节点没有右孩子，但是有父节点且是父节点的左孩子，必然下一个节点就是该节点的父节点；
该节点没有右孩子，且有父节点且是父节点的右孩子，要么该节点是最后一个节点，要么沿着父链上升，之后第一个节点的是其父节点的左孩子，这个父节点就是下一个节点。

[Java] 纯文本查看 复制代码

//二叉树的下一个结点
TreeLinkNode *GetNext(TreeLinkNode *pNode) {
        if (!pNode) return pNode;
        if (pNode->right) {                //有右孩子的情况
                pNode = pNode->right;
                while (pNode->left) {
                        pNode = pNode->left;
                }
                return pNode;
        } 
        else {                //没有右孩子的情况
                TreeLinkNode *parent = pNode->next;
                if (!parent) {
                        return parent;
                } 
                else {
                        if (pNode == parent->left) {        //该节点是其父节点的左孩子
                                return parent;
                        } 
                        else {        //该节点是其父节点的右孩子，沿左侧链上升
                                while (parent->next && parent == parent->next->right) {
                                        parent = parent->next;
                                }
                                return parent->next;
                        }
                }
        }
}

推荐了解热门学科

java培训	Python人工智能	Web前端培训	PHP培训
区块链培训	影视制作培训	C++培训	产品经理培训
UI设计培训	新媒体培训	产品经理培训	Linux运维
大数据培训	智能机器人软件开发

传智播客是一家致力于培养高素质软件开发人才的科技公司，“黑马程序员”是传智播客旗下高端IT教育品牌。自“黑马程序员”成立以来，教学研发团队一直致力于打造精品课程资源，不断在产、学、研3个层面创新自己的执教理念与教学方针，并集中“黑马程序员”的优势力量，针对性地出版了计算机系列教材50多册，制作教学视频数+套，发表各类技术文章数百篇。

传智播客从未停止思考

传智播客副总裁毕向东在2019IT培训行业变革大会提到，“传智播客意识到企业的用人需求已经从初级程序员升级到中高级程序员，具备多领域、多行业项目经验的人才成为企业用人的首选。”

中级程序员和初级程序员的差别在哪里?
项目经验。毕向东表示，“中级程序员和初级程序员最大的差别在于中级程序员比初级程序员多了三四年的工作经验，从而多出了更多的项目经验。“为此，传智播客研究院引进曾在知名IT企业如阿里、IBM就职的高级技术专家，集中研发面向中高级程序员的课程，用以满足企业用人需求，尽快补全IT行业所需的人才缺口。

何为中高级程序员课程?

传智播客进行了定义。中高级程序员课程，是在当前主流的初级程序员课程的基础上，增加多领域多行业的含金量项目，从技术的广度和深度上进行拓展。“我们希望用5年的时间，打造上百个高含金量的项目，覆盖主流的32个行业。”传智播客课程研发总监于洋表示。

黑马程序员热门视频教程【点击播放】

Python入门教程完整版（懂中文就能学会）	零起点打开Java世界的大门
C++\| 匠心之作从0到1入门学编程	PHP\|零基础入门开发者编程核心技术
Web前端入门教程_Web前端html+css+JavaScript	软件测试入门到精通

全国中心

二叉树的常见算法【黑马java培训】

最新资讯

相关阅读