weixin_41107720
2018-05-02 05:11
采纳率: 50%
浏览 5.9k

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

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

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

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

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

CBEGDFA
AFDGEBC

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

5条回答 默认 最新

  • blownewbee 2018-05-02 05:14
    已采纳
     /*以二叉链表作为二叉树的存储结构:
       完成   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;
    }
    
    
    点赞 打赏 评论
  • blownewbee 2018-05-02 05:14
    点赞 打赏 评论
  • weixin_41673226 2018-05-03 00:51

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

    点赞 打赏 评论
  • ft_linyee 2018-05-03 07:16

    void Exchange(BiTree &bt)

    /* Exchange the left and right leaves of /

    /
    bitree whose root node is bt */

    {

    BiTree temp;

    if(bt){

    temp = bt -> lchild;

    bt -> lchild = bt -> rchild;

    bt -> rchild = temp;

    Exchange(bt -> lchild);

    Exchange(bt -> rchild);

    }

    }

    点赞 打赏 评论
  • weixin_46478938 2020-04-08 13:22

    #include
    #include
    #define TElemType char

    typedef struct BiTNode{
    TElemType data;//数据域
    struct BiTNode *lchild,*rchild;//左右孩子指针
    }BiTNode,*BiTree;

    //创建一颗二叉树 ,以前序遍历
    void CreateBiTree(BiTree T)
    {
    char n;
    scanf("%c",&n);
    if(n=='#')
    *T=NULL;
    else
    {
    *T=(BiTNode
    )malloc(sizeof(BiTNode));
    (*T)->data=n;
    CreateBiTree(&(*T)->lchild);
    CreateBiTree(&(*T)->rchild);
    }
    }
    //交换二叉树的左右结点
    void ChangeLeftAndRight(BiTree T)
    {
    if(T != NULL)
    {
    //交换左右节点
    BiTNode *p = T->lchild;
    T->lchild = T->rchild;
    T->rchild = p;

        ChangeLeftAndRight(T->lchild);
        ChangeLeftAndRight(T->rchild);
    }
    //else
       // return;
    

    }

    void preOrderTtaverse(BiTree T)//遍历二叉树
    {
    if(T)
    {
    preOrderTtaverse(T->lchild);
    printf("%c",T->data);
    preOrderTtaverse(T->rchild);
    }
    }
    int main() {
    BiTree Tree=NULL;
    CreateBiTree(&Tree);
    preOrderTtaverse(Tree);//交换前中序遍历
    ChangeLeftAndRight(Tree);//左右交换
    printf("\n");
    preOrderTtaverse(Tree);//交换后
    return 0;
    }

    点赞 打赏 评论

相关推荐 更多相似问题