C语言

C++二叉树的镜像实例

时间:2024-09-02 15:54:11 C语言 我要投稿
  • 相关推荐

C++二叉树的镜像实例

  在计算机科学中,二叉树是每个节点最多有两个子树的树结构。二叉树常被用于实现二叉查找树和二叉堆。下面是小编分享的C++二叉树的镜像实例,一起来看一下吧。


  递归的思想是:

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

  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栈,然后交换左右子树的结点,若根节点的左右子树不为空,即压入栈中,直到栈为空则停止。

  下面是非递归实现代码:

  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);

  }

  }


《C++二叉树的镜像实例.doc》
将本文的Word文档下载到电脑,方便收藏和打印
推荐度:
点击下载文档

【C++二叉树的镜像实例】相关文章:

C与C++之间相互调用的实例07-07

《镜像对称》教学设计10-23

C++类的转换10-17

php画图实例07-16

Javasocket应用实例08-17

C++函数考点归纳09-30

C/C++内存管理09-20

c++快速排序详解10-18

Java与C/C++的区别06-18

C语言中计算二叉树宽度的方式06-12

C++二叉树的镜像实例

  在计算机科学中,二叉树是每个节点最多有两个子树的树结构。二叉树常被用于实现二叉查找树和二叉堆。下面是小编分享的C++二叉树的镜像实例,一起来看一下吧。


  递归的思想是:

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

  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栈,然后交换左右子树的结点,若根节点的左右子树不为空,即压入栈中,直到栈为空则停止。

  下面是非递归实现代码:

  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);

  }

  }