230问答网 > 跪求C语言代码！以二叉链表为存储结构,写一算法交换各结点的左右子树！大神你在哪里！

跪求C语言代码！以二叉链表为存储结构,写一算法交换各结点的左右子树！大神你在哪里！

2025-02-23 03:07:41

推荐回答（2个）

回答1：

算法：用层次遍历思想，交换左右子树即可，用队列来实现，程序测试正确。

d k

m p l q

a b

//输入序列如cdm##p##kl##qa##b##，创建如上的二叉树

#include "stdio.h"
#include "stdlib.h"

#define  MAX  512

typedef char Elem;

struct Tree
{
	Elem   data;

	struct Tree *left;
	struct Tree *right;
};

//////////////////////////////////////////////////////////////////////////
//自己构造的队列 begin
class CQueue
{
public:
	CQueue();
	~CQueue();
	int Empty();
    int InsertQueue(struct Tree *);
    struct Tree *DeleteQueue();
private:
    struct Tree *a[MAX];
    int front;
	int rear;
};

CQueue::CQueue()
{
	int i=0;
	for (i=0; i	{
		a[i] = NULL;
	}
	front = 0;
	rear = 0;

}
CQueue::~CQueue()
{

}

int CQueue::InsertQueue(struct Tree *t)
{
    if ( (rear+1)%MAX == front )
    {
		printf("The Queue is full!");
		return 0;
    }
	if(t == NULL)
	{
        return 0;
	}
	a[rear] = t;
	rear = (rear+1)%MAX;
	return 1;
}

struct Tree * CQueue::DeleteQueue()
{
    if ( front == rear )
    {
		printf("The Queue is Empty!");
        return NULL;
    }
    struct Tree *pTemp=NULL;
	pTemp = a[front];
	front = (front+1)%MAX;
    return pTemp;
}

int CQueue::Empty()
{
	if (front == rear)
	{
		return true;
	}
	return false;
}
//自己构造的队列 end
//////////////////////////////////////////////////////////////////////////

//先根遍历方式创建二叉树
void CreateTree(struct Tree **root)
{
	char ch = getchar();
    if (ch == '#')
    {
        *root =  NULL;
        return ;
	}
    *root = (struct Tree *)malloc(sizeof(struct Tree));
    (*root)->data = ch;
	CreateTree( &( (*root)->left) );
	CreateTree( &( (*root)->right) );

}

//递归方式先根遍历方式
void RootLeftRight_Traverse(struct Tree *root)
{
    if (root == NULL)
    {
		return ;
    }
	printf("%c ",root->data);
	RootLeftRight_Traverse(root->left);
    RootLeftRight_Traverse(root->right);
}

//层次遍历，在此用来测试队列的正确性
void LevelTraverse(struct Tree *root)
{
    CQueue Cque;
	Cque.InsertQueue(root);
	while ( !Cque.Empty() )
	{
		struct Tree *t = NULL;
		t = Cque.DeleteQueue();
		printf("%c ",t->data);
		if (t->left != NULL)
		{
            Cque.InsertQueue(t->left);
		}
		if(t->right != NULL)
		{
            Cque.InsertQueue(t->right);
		}
		
	}
}

//层次遍历方式，交换左右孩子节点
struct Tree *ExchangeLeftRight(struct Tree * root)
{
	CQueue Cque;
	Cque.InsertQueue(root);
	while ( !Cque.Empty() )
	{
        struct Tree *pNode=NULL,*pTemp = NULL;
		pNode = Cque.DeleteQueue();
        pTemp = pNode->left;
		pNode->left = pNode->right;
		pNode->right = pTemp;

        if (pNode->left != NULL)
        {
            Cque.InsertQueue(pNode->left);
        }
		if (pNode->right != NULL)
		{
            Cque.InsertQueue(pNode->right);
		}
		
	}
	return root;
}

int main(int argc, char* argv[])
{
	
	struct Tree *root=NULL;
	//输入序列如cdm##p##kl##qa##b##
	printf("input root_left_right sequence:\n");
	CreateTree(&root);
	printf("\nprintTree\n");
	RootLeftRight_Traverse(root);
    printf("\nprintTree level traverse\n");
	LevelTraverse(root);

	struct Tree *rootChanged=NULL;
	rootChanged = ExchangeLeftRight(root);
    printf("\nprintTree level traverse after change\n");
	LevelTraverse(rootChanged);

    printf("\n");

	return 0;
}

回答2：

下面这个转自网络，注释比较全，供参考

/*对任意一颗二叉树，是将其说有结点的左右子树交换，并将交换前后不同二叉树分别用层序、前序，中序三种不同的方法进行遍历。
算法描述：分四步 
（1） 创建二叉树
 用递归的方法创建树根结点，然后分别创建左右子树。在创建二叉树时结点可以提前确定，也可以不确定，有数据输入控制。
此方法中树的节点有输入端输入，然后再输入一个字符串，然后从字符串中读入数据创建二叉树。
（2）用三种不同的方法遍历交换前的二叉树。
层次遍历，先根遍历，中跟遍历。层次遍历用一个指针栈来实现。另外两种方法用递归即可。
（3）交换二叉树中所有的结点的左右子树。
交换过程中需要用一个指针站来实现。
（4）遍历二叉树。
实现过程跟第二步差不多。*/
#include
#include
#define max 20//定义树的结点数 
#define null 0
typedef struct btnode//定义二叉树结点类型
{
 char date;//结点数据类型 
 struct btnode *lc,*rc;//左右指针 
}bttree;
bttree  *createtree(char *str,int i,int m)//将字符串str中第i到第m个字符创建树 
{
 bttree *p; 
 if(i>=m)
  return null;
 p=(bttree*)malloc(sizeof(bttree));//生成新结点
 p->date=str[i];//将结点的第一个数据付给根 
 p->lc=createtree(str,2*i+1,m);//创建左子树
 p->rc=createtree(str,2*i+2,m);//创建右子树
 return (p); 
}
bttree *jiaohuan(bttree *p)//将p指针指向的二叉树的左右子树进行互换。 
{
 bttree *stack[max];//指针类型的堆栈
 int k;
 k=0;
 stack[k]=null;
 if(p!=null)//交换p结点的左右孩子 
 {
  k++;
  stack[k]=p->lc;
  p->lc=p->rc;
  p->rc=stack[k];
  p->lc=jiaohuan(p->lc);
  p->rc=jiaohuan(p->rc);
 }
 return (p); 
}
void xiangen(bttree *t)//先跟遍历 
{
 if(t!=null)
 {
  printf("%c",t->date);
  if(t->lc)
  {
   printf("->");
   xiangen(t->lc); 
  }
  if(t->rc)
  {
   printf("->");
   xiangen(t->rc); 
  } 
 } 
}
void zhonggen(bttree *p)//中根遍历即中序遍历 
{
 if(p!=null)
 {
  zhonggen(p->lc); 
  printf("%c",p->date);
  printf("->");
  zhonggen(p->rc);
 } 
}
void cengci(bttree *t,int m)//按层次遍历
{
 bttree *queue[max];
 bttree *p;
 int  front=0,rear=0,i;
 queue[rear++]=t;
 while(front!=rear)
 {
  p=queue[front];
  front=(front+1)%m;
  printf("%c->",p->date);//输出根结点 
  if(p->lc!=null)//遍历左子树 
  {
   if((rear+1)%m!=front)
   {
    queue[rear]=p->lc;
    rear=(rear+1)%m; 
   }
  }
  if(p->rc!=null)//遍历右子树 
  {
   if((rear+1)%m!=front)
   {
    queue[rear]=p->rc;
    rear=(rear+1)%m; 
   } 
  }
 }
}
int main()
{
 int i,n;
 char str[max];
 bttree *root;//二叉树根结点的指针 
 printf("请输入根结点数目n：");
 scanf("%d",&n);
 getchar();
 printf("请输入%d个结点：",n);
 for(i=0;i  str[i]=getchar();
 printf("\n\n");
 root=createtree(str,0,n);
 printf("层次遍历是：\n");
 cengci(root,n);
 printf("\n先根遍历是：\n");
 xiangen(root);
 printf("\n中根遍历是：\n");
 zhonggen(root);
 printf("\n\n");
 root=jiaohuan(root);//交换左右子树
 printf("左右子树交换后!\n");
 printf("层次遍历是：\n");
 cengci(root,n);
 printf("\n先根遍历是：\n");
 xiangen(root);
 printf("\n中根遍历是：\n");
 zhonggen(root);
 printf("\n\n");
 system("pause");
}

口袋妖怪金版怎么不能联机对战

请问泰山区现行的初中语文教材是哪个版本的，人教版还是鲁教版的？

大家帮我看下这条水晶手链是真的水晶么？这个照片看得清楚么？

怎么理解人民日益增长的美好生活需要和不平衡不充分的发展之间的矛盾

男人和女人头发有什么区别