黑马程序员技术交流社区
标题: 【成都校区】二叉树的常见算法 [打印本页]
作者: 小蜀哥哥 时间: 2019-8-1 17:37
标题: 【成都校区】二叉树的常见算法
本帖最后由 小蜀哥哥 于 2019-8-1 17:40 编辑
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;
}
}
}
}
| 欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) |
黑马程序员IT技术论坛 X3.2 |