交换二叉树的所有节点的左右子树算法（C语言）

灰姑娘的霸气 · 2018-4-30 01:55:55

#include
#include
typedef struct binode{
int data;
struct binode *lchild,*rchild;
}binode,*bitree;
typedef struct{
bitree elem[100];
int top;
}stack;
bitree creat_bt(){ //按扩展前序建二叉树
bitree t;int x;
scanf("%d",&x);
if (x==0) t=NULL;
else { t=(bitree)malloc(sizeof(binode));
   t->data=x;
   t->lchild=creat_bt();
   t->rchild=creat_bt();
   }
return t;
}
void exchange(bitree t) //左、右子树交换
{bitree p;
if(t!=NULL)
{ p=t->lchild;t->lchild=t->rchild;
   t->rchild=p;
   exchange(t->lchild);
   exchange(t->rchild);
}
}
void inorder(bitree bt) //递归的中序遍历
{ if (bt){
   inorder(bt->lchild);
   printf("% d",bt->data);
   inorder(bt->rchild);
}
}
main()
{bitree root;
printf("\n");
printf("建二叉树，输入元素：");
root=creat_bt(); /*create tree of useing preorder*/
printf("交换前的中序序列是：");
inorder(root);
exchange(root);
printf("\n交换后的中序序列是：");
inorder(root);
printf("\n");
}

liubird · 2018-4-30 01:55:56

递归的交换就可以了。
struct  Node
   {
      int value;
      Node * left;
      Node * right;
   };

void exchange(Node * node)
{
if(node == NULL) return;
Node * temp = node->left;
node->left = node->right;
node->right = temp;

exchange(node->left);
exchange(node->right);
}

Lion1942 · 2018-4-30 01:55:57

二叉树最好使用递归的算法，假设二叉树节点定义如下：
typedef struct node{
      int a;
      node* left;
      node* right;
};
可以定义交换左右子树的函数如下：
void changeleaf(node* anode)
{
      if(anode!=0)
      {
            node* tnode=anode->left;
            anode->left=anode->right;
            anode->right=tnode;
            changeleaf(anode->left);
            changeleaf(anode->right);
      }
};

交换二叉树的所有节点的左右子树算法（C语言）

3 个回复