服务器之家

服务器之家 > 正文

C++ 二叉树的镜像实例详解

时间:2021-05-14 14:20     来源/作者:he_shuai20

二叉树的镜像:将一个二叉树的左右子树,调换位置。即下图的形式:

C++ 二叉树的镜像实例详解

递归的思想是:

从根节点的左右子树进行交换,然后以根节点的左子树为根节点,而后以根节点的右结点为根节点,进行左右子树交换。遇到空节点或叶节点直接返回。下面求二叉树镜像的函数代码实现:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template<class T>
void MirroTree(TreeNode<T> * root)
{
  if (root == NULL)
    return;
  if (root->_left == NULL && root->_right == NULL)
    return;
  else
  {
    TreeNode<T>* temp = root->_left;
    root->_left = root->_right;
    root->_right = temp;
  }
  MirroTree(root->_left);
  MirroTree(root->_right);
}

非递归实现思想:

利用stack栈的FILO,即先进后出原则,将根节点先行压入栈中,然后进入栈同时取栈顶结点并pop栈,然后交换左右子树的结点,若根节点的左右子树不为空,即压入栈中,直到栈为空则停止。

下面是非递归实现代码:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template<class T>
void MirroTree_NoR(TreeNode<T>* root)
{
  stack<TreeNode<T>*> s;
  s.push(root);
  while (s.size())
  {
    TreeNode<T>* Top = s.top();
    if (Top->_left != NULL || Top->_right != NULL)
    {
      TreeNode<T>* temp = Top->_left;
      Top->_left = Top->_right;
      Top->_right = temp;
    }
    if (Top->_left != NULL)
      s.push(Top->_left);
    if (Top->_right != NULL)
      s.push(Top->_right);
  }
}

感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

原文链接:http://blog.csdn.net/he_shuai20/article/details/72670136

标签:

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
2021德云社封箱演出完整版 2021年德云社封箱演出在线看
2021德云社封箱演出完整版 2021年德云社封箱演出在线看 2021-03-15
返回顶部