把我的 C 作业贴出来 实验四 树——1

实验四 树

一、 实验目的

1．熟悉二叉树的链式存储结构

2．掌握二叉树的建立、深度优先递归遍历等算法

3．能够利用遍历算法实现一些应用

二、实验内容

1．已知二叉树采用二叉链表存储结构，编写一个算法交换二叉树所有左、右子树的位置，即结点的左子树变为结点的右子树，右子树变为左子树。（文件夹：习题12_14）

---

//二叉链表的结构类型定义.h

const int maxsize=1024;

typedef char datatype;

typedef struct node

{

datatype data;

struct node *lchild,*rchild;

}bitree;

//二叉树的建立.h

bitree * creattree()

{

char ch;

bitree*Q[maxsize];

int front,rear;

bitree*root,*s;

root=NULL;

front=1;rear=0;

while((ch=getchar())!='#')

{

s=NULL;

if(ch!='@')

{

s=new bitree;

s->data=ch;

s->lchild=NULL;

s->rchild=NULL;

}

rear++;

Q[rear]=s;

if(rear==1)root=s;

else

{

if(s&&Q[front])

if(rear%2==0)Q[front]->lchild=s;

else Q[front]->rchild=s;

if(rear%2==1)front++;

}

}

return root;

}

//二叉树的输出.h

//按照先序序列输出

using std::cout;

void preorder(bitree*p)

{

if(p!=NULL)

{

cout<<p->data;

if(p->lchild!=NULL||p->rchild!=NULL)

{

cout<<"(";

preorder(p->lchild);

if(p->rchild!=NULL)cout<<",";

preorder(p->rchild);

cout<<")";

}

}

}

//交换左右子树.h

void swap( bitree * R )

{

bitree * p;

if( R == NULL )return;

p = R->lchild;

R->lchild = R->rchild;

R->rchild = p;

swap( R->lchild );

swap( R->rchild );

return;

}

//交换左右子树的主程序文件.cpp

#include<iostream>

#include<stdio.h>

#include<stdlib.h>

#include"二叉链表的结构类型定义.h"

#include"二叉树的建立.h"

#include"二叉树的输出.h"

#include"交换左右子树.h"

using namespace std;

int main()

{

bitree*pb;

pb=creattree();

preorder(pb);

cout<<endl;

swap(pb);

preorder(pb);

cout<<endl;

system("PAUSE");

return 0;

}