软件开发定制顺序存储结构

交换左右子树实际上就是同层之间交换位置，在顺序存储结构下，先确定树的深度，再划分层，每个层内做交换即可。

链式存储结构

递归实现很简单，可以借助栈或队列辅助实现。

递归代码：

void ReChange(BiTree root){    if(root==NULL) return;    else    {        BiTree temp=root->lchild;        root->lchild=root->rchild;        root->rchild=temp;        ReChange(root->lchild);        ReChange(root->rchild);    }}
1
2
3
4
5
6
7
8
9
10
11
12

非递归代码：

void Change(BiTree root){    BiTree Queue[MAXSIZE];    int front=-1;    int rear=0;    Queue[rear]=root;    while(rear!=front)    {        BiTree p=Queue[++front];        BiTree temp=p->lchild;        p->lchild=p->rchild;        p->rchild=temp;        if(p->lchild) Queue[++rear]=p->lchild;        if(p->rchild) Queue[++rear]=p->rchild;    }}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

完整代码：

#include<stdio.h>#include<stdlib.h>#include<math.h>#include<iostream>using namespace std;typedef char DataType;#define MAXSIZE 100typedef struct node{    DataType data;    struct node *lchild;    struct node *rchild;}BiTreeNode,*BiTree;//先序建立二叉树void CreateBiTree(BiTree &root){    char c;    cin>>c;    if(c=='#')    {        root=NULL;    }    else    {        root=(BiTree)malloc(sizeof(BiTreeNode));        root->data=c;        CreateBiTree(root->lchild);        CreateBiTree(root->rchild);    }}//递归实现先序遍历void PreOrder(BiTree root){    if(root!=NULL)    {        cout<<root->data<<" ";        PreOrder(root->lchild);        PreOrder(root->rchild);    }}//递归实现交换左右子树void ReChange(BiTree root){    if(root==NULL) return;    else    {        BiTree temp=root->lchild;        root->lchild=root->rchild;        root->rchild=temp;        ReChange(root->lchild);        ReChange(root->rchild);    }}//非递归实现交换左右子树void Change(BiTree root){    BiTree Queue[MAXSIZE];    int front=-1;    int rear=0;    Queue[rear]=root;    while(rear!=front)    {        BiTree p=Queue[++front];        BiTree temp=p->lchild;        p->lchild=p->rchild;        p->rchild=temp;        if(p->lchild) Queue[++rear]=p->lchild;        if(p->rchild) Queue[++rear]=p->rchild;    }}//测试序列：ABDG###E##CF#H###int main(){    BiTree root;    CreateBiTree(root);    PreOrder(root);    cout<<endl;    ReChange(root);    PreOrder(root);    cout<<endl;    Change(root);    PreOrder(root);    cout<<endl;    system("pause");    return 0;}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100