若用二叉链表作为二叉树的存储表示，试编写算法交换二叉树中各结点的左右子树

Question

如题所述

Answer 1

及层次顺序遍历二叉树的算法。
#define M 10
typedef int DataType;/*元素的数据类型*/
typedef struct node
{ DataType data;
struct node *lchild,*rchild;
}BitTNode,*BiTree;
int front=0,rear=0;
BitTNode *que[10];
BitTNode *creat()
{BitTNode *t;
DataType x;
scanf("%d",&x);
if(x==0) t=NULL;
else{ t=(BitTNode *)malloc(sizeof(BitTNode));
t->data=x;
t->lchild=creat();
t->rchild=creat();
}
return(t);
}/*creat*/

/* 前序遍历二叉树t */
void preorder(BiTree t)
{ if(t!=NULL)
{ printf("%4d",t->data);
preorder(t->lchild);
preorder(t->rchild);
}
}

/* 中序遍历二叉树t */
void inorder(BiTree t)
{ if(t!=NULL)
{ inorder(t->lchild);
printf("%4d",t->data);
inorder(t->rchild);
}
}

/* 后序遍历二叉树t */
void postorder(BiTree t)
{ if(t!=NULL)
{ postorder(t->lchild);
postorder(t->rchild);
printf("%4d",t->data);
}
}

void enqueue(BitTNode *t)
{if (front!=(rear+1)%M)
{ rear=(rear+1)%M;
que[rear]=t;
}
}/*enqueue*/

BitTNode * delqueue()
{ if(front==rear)return NULL;
{ front=(front+1)%M;
return (que[front]);
}
}/*delqueue*/

/* 按层次遍历二叉树t */
void levorder(BiTree t)
{ BitTNode *p;
if(t!=NULL)
{ enqueue(t);
while (front!=rear)
{ p=delqueue();
printf("%4d",p->data);
if(p->lchild!=NULL) enqueue(p->lchild);
if(p->rchild!=NULL) enqueue(p->rchild);
}
}
}/* levorder */
main()
{BitTNode *root;
root=creat();
printf("\n按先序遍历次序生成的二叉树");
printf("\n前序遍历二叉树");
preorder(root);
printf("\n中序遍历二叉树");
inorder(root);
printf("\n后序遍历二叉树");
postorder(root);
printf("\n层次顺序遍历二叉树");
levorder(root);
}

2、以二叉链表作存储结构，试编写计算二叉树深度、所有结点总数、叶子结点数、双孩子结点个数、单孩子结点个数的算法
#include <stdio.h>
#define MaxSize 100
typedef char ElemType;
typedef struct node
{
ElemType data;
struct node *left,*right;
} BTree;
BTree * createbt( )
{ BTree *q;
struct node1 *s[30];
int j,i,x;
printf("建立二叉树，输入结点对应的编号和值,编号和值之间用逗号隔开\n\n");
printf("i,x = ");
scanf("%d,%c",&i,&x);
while(i != 0 && x != '$')
{ q = (BTree*)malloc(sizeof(BTree)); /*建立一个新结点q*/
q->data = x; q->left = NULL; q->right = NULL;
s[i] = q; /*q新结点地址存入s指针数组中*/
if(i != 1) /*i = 1，对应的结点是根结点*/
{ j = i / 2; /*求双亲结点的编号j*/
if(i % 2 == 0)
s[j]->left = q; /*q结点编号为偶数则挂在双亲结点j的左边*/
else
s[j]->right = q; /*q结点编号为奇数则挂在双亲结点j的右边*/
}
printf("i,x = ");
scanf("%d,%c",&i,&x);
}
return s[1]; /*返回根结点地址*/
}

void preorder(BTree *BT)
/* 前序遍历二叉树t */
{ if(BT!=NULL)
{ printf("%4c", BT ->data);
preorder(BT ->left);
preorder(BT ->right);
}
}

int BTreeDepth(BTree *BT)
{
int leftdep,rightdep;
if (BT==NULL)
return(0);
else
{
leftdep=BTreeDepth(BT->left);
rightdep=BTreeDepth(BT->right);
if (leftdep>rightdep)
return(leftdep+1);
else
return(rightdep+1);
}
}

int nodecount(BTree *BT)
{
if (BT==NULL)
return(0);
else
return(nodecount(BT->left)+nodecount(BT->right)+1);
}
int leafcount(BTree *BT)
{
if (BT==NULL)
return(0);
else if (BT->left==NULL && BT->right==NULL)
return(1);
else
return(leafcount(BT->left)+leafcount(BT->right));
}

int notleafcount(BTree *BT)
{
if (BT==NULL)
return(0);
else if (BT->left==NULL && BT->right==NULL)
return(0);
else
return(notleafcount(BT->left)+notleafcount(BT->right)+1);
}

int onesoncount(BTree *BT)
{
if (BT==NULL)
return(0);
else if ((BT->left==NULL && BT->right!=NULL) ||
(BT->left!=NULL && BT->right==NULL))
return(onesoncount(BT->left)+onesoncount(BT->right)+1);
else
return(onesoncount(BT->left)+onesoncount(BT->right));
}

int twosoncount(BTree *BT)
{
if (BT==NULL)
return(0);
else if (BT->left==NULL || BT->right==NULL)
return(twosoncount(BT->left)+twosoncount(BT->right));
else if (BT->left!=NULL && BT->right!=NULL)
return(twosoncount(BT->left)+twosoncount(BT->right)+1);
}

main()
{
BTree *B;
B=creatree();
printf("\n按先序遍历次序生成的二叉树");
preorder(B);
printf("\n二叉树深度:%d\n",BTreeDepth(B));
printf("总结点个数:%d\n",nodecount(B));
printf("叶子结点个数:%d\n",leafcount(B));
printf("非叶子结点个数:%d\n",notleafcount(B));
printf("具有双孩子结点个数:%d\n",twosoncount(B));
printf("具有单孩子结点个数:%d\n",onesoncount(B));
}
如果还没解决你的问题，可以加我百度HI账号。

Answer 2

递归:
void exchange(BTree *rt){
BTree *temp = NULL;
if(rt->lchild == NULL && rt->rchild == NULL)
return;
else{
temp = rt->lchild;
rt->lchild = rt->rchild;
rt->rchild = temp;
}
if(rt->lchild)
exchange(rt->lchild);
if(rt->rchild)
exchange(rt->rchild);
}

非递归:
Stack是一个定义好的通用堆栈类型,支持初始化/进站/出战等操作
int Exchange(BiTree *T)
{
Stack s;
BiTree *p;
InitStack(s);
p=T;
while(p||!StackEmpty(s)){
if(p){
push(s,p);
p->Lchild;
}
else{
pop(s,p);
t=p->Rchild;
p->Rchild=p->Lchild;
p->Lchild=t;
p-＝->Lchild;
}
}
return 1;
}本回答被提问者和网友采纳

Answer 3

递归:
void exchange(BTree *rt){
BTree *temp = NULL;
if(rt->lchild == NULL && rt->rchild == NULL)
return;
else{
temp = rt->lchild;
rt->lchild = rt->rchild;
rt->rchild = temp;
}
if(rt->lchild)
exchange(rt->lchild);
if(rt->rchild)
exchange(rt->rchild);
}

非递归:
Stack是一个定义好的通用堆栈类型,支持初始化/进站/出战等操作
int Exchange(BiTree *T)
{
Stack s;
BiTree *p;
InitStack(s);
p=T;
while(p||!StackEmpty(s)){
if(p){
push(s,p);
p->Lchild;
}
else{
pop(s,p);
t=p->Rchild;
p->Rchild=p->Lchild;
p->Lchild=t;
p-＝->Lchild;
}
}
return 1;
}