交换二叉树中每个结点的左孩子和右孩子C++语言

Question

交换二叉树中每个结点的左孩子和右孩子
以二叉链表作为二叉树的存储结构，交换二叉树中每个结点的左孩子和右孩子。
输入格式:

输入二叉树的先序序列。
提示：一棵二叉树的先序序列是一个字符串，若字符是‘#’,表示该二叉树是空树，否则该字符是相应结点的数据元素。
输出格式:

输出有两行：
第一行是原二叉树的中序遍历序列；
第二行是交换后的二叉树的中序遍历序列。
输入样例:

ABC##DE#G##F###
输出样例:

CBEGDFA
AFDGEBC

Answer 1

 /*以二叉链表作为二叉树的存储结构:
   完成   1:统计二叉树的叶结点个数.
   完成   2:判别两棵树是否相等
   完成   3:交换二叉树每个节点的左孩子和右孩子
    4:设计二叉树的双序遍历(双序遍历就是指对于二叉树的每个节点，先访问这个节点
        ，再按双序遍历她的左子树，然后在访问这个节点，然后在按双序遍历它右子树 )
    5:计算二叉树的最大宽度(就是所有层中结点个数最大值)
    6:用按层次遍历二叉树的方法，统计树中度为1的节点数目
    7:求二叉树第一条最长路径的长度，并输出次路径上个节点值
   完成   8:输出二叉树中从每个叶子节点到根节点的路径
*/
#include <iostream>
using namespace std;

#define MAXSIZE 100              //栈和队列中需要的长度
//***********节点类**************
class Tree;
class Node
{
private:
 int Data;
 Node* Lchild;
 Node* Rchild;
public:
 Node()
 {
  Lchild = NULL;
  Rchild = NULL;
 }
 int Return_Data(){return Data;}               //返回数据域
 Node* Return_Lchild(){return Lchild;}         //返回做孩子
 Node* Return_Rchild(){return Rchild;}         //返回右孩子
 friend class Tree;                    //声明Node类为Tree的友元类
};

//**********Tree类***************
class Tree
{
private:
 int Leaf_Numbers;
 Node* Root;
 int Front;            //栈顶指针
 int Rear;             //栈底指针
 Node* NodeStack[MAXSIZE];
public:
 Tree()
 {
  Leaf_Numbers = 0;
  Root = NULL;
  Front = -1;
  Rear = 0;
  for(int i = 0; i < MAXSIZE; i++)
  {
   NodeStack[i] = NULL;
  }
 }
 //************函数**************
 void CreatTree(Node* &);                     //先序递归创建节点
 void TheCreatTree();
 void TraveFront(Node* );                         //先序遍历
 void TheTraveFront();
 void Numbers_Leafs(Node*);                       //计算叶子节点数
 void TheNumbers_Leafs();
 int Return_LeafNums();
 Node* Return_Root(){return Root;}             //返回树的头结点
 void ExchangeLR(Node*);                           //交换二叉树的左右子树
 void TheExchangeLR();
 void Leaf_Root(Node*);                       //叶子到根节点的路径
 /*算法：1.申请一个对象指针数组用于存储节点的地址 用于栈的先进后出
         2.从根节点先把左子树进栈，在右子树进栈
         3.在节点进站后，当它左子树为空判断右子树是否为空，为空把它只有兄弟进站
           否则吧它右子树进站
         4.当节点左右子树都为空，把它进站，从栈顶退栈，把吧剩余的战中元素遍历但不退栈
           然后检查它右兄弟
         5.重复3 4*/
 void TheLeaf_Root();
};
void Tree::CreatTree(Node* &p)
{
 int x;
 cin>>x;
 if(x != -1)
 {
  p = new Node();
  p->Data = x;
  CreatTree(p->Lchild);
  CreatTree(p->Rchild);
 }
}
void Tree::TheCreatTree()
{

 CreatTree(Root);
}
void Tree::TraveFront(Node* p)
{
 if(p != NULL)
 {
  cout<<p->Data<<" ";
  TraveFront(p->Lchild);
  TraveFront(p->Rchild);
 }
}
void Tree::TheTraveFront()
{
 TraveFront(Root);
}
void Tree::Numbers_Leafs(Node* p)
{
 if(p != NULL)
 {
  if(p->Lchild == NULL && p->Rchild == NULL)    //俺的垃圾算法
  {
   cout<<p->Data<<" ";
   Leaf_Numbers = Leaf_Numbers + 1;
  }
  else
  {
   Numbers_Leafs(p->Lchild);
   Numbers_Leafs(p->Rchild);
  }
 }
 /*if(p != NULL)                                    //优化算法
 {
  Numbers_Leafs(p->Lchild);
  if(p->Lchild == NULL && p->Rchild == NULL)
  {
   Leaf_Numbers = Leaf_Numbers + 1;
   cout<<p->Data<<" ";
  }
  Numbers_Leafs(p->Rchild);
 }*/
 /*if(p->Lchild == NULL && p->Rchild == NULL)    //俺的垃圾算法
 {
  cout<<p->Data<<" ";
  Leaf_Numbers = Leaf_Numbers + 1;
 }
 else
 {
  if(p->Lchild != NULL && p->Rchild != NULL)
  {
   Numbers_Leafs(p->Lchild);
   Numbers_Leafs(p->Rchild);
  }

  if(p->Lchild != NULL && p->Rchild == NULL)
   Numbers_Leafs(p->Lchild);
  if(p->Lchild == NULL && p->Rchild != NULL)
   Numbers_Leafs(p->Rchild);
 }*/
}
void Tree::TheNumbers_Leafs()
{
 Numbers_Leafs(Root);
}
int Tree::Return_LeafNums()
{
 return Leaf_Numbers;
}
/*
比较两个二叉树是否相等，所以函数不能属于类当中
应声明为类外函数
*/
bool Compare(Node* p1,Node* p2)
{
 if(p1 == NULL && p2 == NULL)
 return true;
 else
 if((p1 == NULL && p2 != NULL) || (p1 != NULL && p2 == NULL))
  return false;
 else
  if(p1->Return_Data() != p2->Return_Data())
   return false;
  else
  /*{
   bool Is_Left = Compare(p1->Return_Lchild(),p2->Return_Lchild());
   bool Is_Right = Compare(p1->Return_Rchild(),p2->Return_Rchild());
   if(Is_Left && Is_Right)
    return true;
   else
    return false;

  }*/
   return (Compare(p1->Return_Lchild(),p2->Return_Lchild()) && Compare(p1->Return_Rchild(),p2->Return_Rchild()));
}
bool TheCompare(Tree &tree1,Tree &tree2)
{
 Node* p1 = tree1.Return_Root();
 Node* p2 = tree2.Return_Root();
 return Compare(p1,p2);
}
void Tree::ExchangeLR(Node* p)
{
 if(p->Lchild != NULL && p->Rchild != NULL)
 {
  Node* temp;
  temp = p->Lchild;
  p->Lchild = p->Rchild;
  p->Rchild = temp;
  ExchangeLR(p->Lchild);
  ExchangeLR(p->Rchild);
 }
 else
 {
  return;
 }
}
void Tree::TheExchangeLR()
{
 ExchangeLR(Root);
}
void Tree::Leaf_Root(Node* p)
{
 if(p != NULL)
 {
  Front = Front + 1;                  //栈顶指针加1
  NodeStack[Front] = p;               //进栈

  Leaf_Root(p->Lchild);
  Leaf_Root(p->Rchild);
 }
 if(NodeStack[Front]->Lchild == NULL && NodeStack[Front]->Rchild == NULL)     //左右子树都为空，开始遍历
 {
  while(NodeStack[Front]->Rchild == NULL)                                  //当栈顶元素的右孩子为空则它是叶子，输出
  {

   cout<<NodeStack[Front]->Data<<"->";
   Front = Front - 1;
  }
        while(NodeStack[Front]->Rchild == NodeStack[Front+1] && Front != 0)       //当Front = -1是程序错误
  {                  //从右叶子到根节点，如果利用上面的while循环，要是
   cout<<NodeStack[Front]->Data<<"->";            //第一个叶子是右叶子则会重复输出，用这用判断
   Front = Front - 1;
  }

  int temp = Front;
  while(temp != Rear - 1)             //把剩余的有右孩子的节点输出，栈顶指针不变
  {

   if(temp == 0)
    cout<<NodeStack[temp]->Data;
   else
    cout<<NodeStack[temp]->Data<<"->";
   temp = temp - 1;
  }
  cout<<"  路径输出完毕!"<<endl;
 }
}
void Tree::TheLeaf_Root()
{
 Leaf_Root(Root);
}
int main()     //1 2 3 -1 -1 4 5 -1 -1 6 -1 -1 7 8 -1 -1 9 10 -1 -1 -1             
{
 Tree Root1;
 cout<<"输入二叉树节点,(空点-1) :";
 Root1.TheCreatTree();
 cout<<"~~~~~~~~~~~~~~~~~~~~~~~~~"<<endl;
 cout<<"先序遍历二叉树 :";
 /*
               1
          /        \
      2          7
      /     \     /    \
     3       4   8      9
            / \        /
           5   6      10
 */
 Root1.TheTraveFront();cout<<endl;
 cout<<"~~~~~~~~~~~~~~~~"<<endl;
 cout<<"此树的叶子节为 :";
 Root1.TheNumbers_Leafs();
 cout<<" ,叶节点个数为:";
 cout<<Root1.Return_LeafNums()<<endl;
 cout<<"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"<<endl;
 cout<<"请输入待比较的第二棵树的节点:";
 Tree Root2;
 Root2.TheCreatTree();
 bool flag = TheCompare(Root1,Root2);
 flag ? cout<<"∨∨这两棵树相等"<<endl : cout<<"××这两棵树不相等"<<endl;
 cout<<"~~~~~~~~~~~~~~~~~~~~~~~~~"<<endl;
 cout<<"Root1交换左右子树前:";
 Root1.TheTraveFront();cout<<endl;

 cout<<"Root1交换左右子树后:";
 Root1.TheExchangeLR();
 Root1.TheTraveFront();cout<<endl;
 /*
               1
          /        \
      7          2
      /     \     /    \
     9       8   4      3
      \         / \
       10      6   5
 1 7 9 10 8 2 4 6 5 3           这是交换后的先序遍历*/
 cout<<"~~~~~~~~~~~~~~~~~~~~~~~~~"<<endl;
 cout<<"Root2的叶子路径:"<<endl;
 cout<<"                        "<<endl;
 cout<<"            1           "<<endl;
 cout<<"        /        \\      "<<endl;
 cout<<"       2          7     "<<endl;
 cout<<"    /     \\     /    \\  "<<endl;
 cout<<"   3       4   8      9 "<<endl;
 cout<<"          / \\        /  "<<endl;
    cout<<"     5   6      10  "<<endl;
 Root2.TheLeaf_Root();
 return 0;
}