数据结构树和二叉树.doc
实验5 二叉排序树的建立和遍历实验目的：1、 了解二叉排序树的概念2、 建立二叉排序树3、 对二叉排序树进行前序、中序和后序遍历实验内容：1、 建立二叉排序树。从键盘中随机输入一串无序数据，生成二叉排序树。#include<stdio.h>#include<malloc.h>#include<conio.h>#define MAX 100typedef struct tnodeint data;struct tnode *lchild,*rchild;TNODE;void create();void insert(int ); /*插入结点*/void inorder(TNODE *); /*中序遍历*/TNODE *root=NULL;main()create();inorder(root);void inorder(TNODE *ptr)if(ptr!=NULL) inorder(ptr->lchild); printf("%d ",ptr->data); inorder(ptr->rchild); void create()int n,i;int kMAX;printf("please input the node number:");scanf("%d",&n);for(i=0;i<n;i+) scanf("%d",&ki);for(i=0;i<n;i+) insert(ki);void insert(int m)TNODE *p1,*p2;if(root=NULL) root=(TNODE *)malloc(sizeof(TNODE); root->data=m; root->lchild=root->rchild=NULL; else p1=root; while(m!=p1->data) if(m<p1->data && p1->lchild!=NULL) /如果m小于根结点值且p1的左孩子不为空 p1=p1->lchild; else if(m>p1->data && p1->rchild!=NULL) /如果m大于根结点值且p1的右孩子不为空 p1=p1->rchild; else if(m<p1->data && p1->lchild=NULL) /如果m小于根结点值且p1的左孩子为空 p2=(TNODE *)malloc(sizeof(TNODE); p2->data= m; p2->lchild=NULL; p2->rchild=NULL; p1->lchild=p2; /把m值赋给新的结点数据域，新结点的左右指针域置空，并把新的结点赋给p1的左孩子指针域 return; else if(m>p1->data && p1->rchild=NULL) p2=(TNODE *)malloc(sizeof(TNODE); p2->data= m; p2->lchild=NULL; p2->rchild=NULL; p1->rchild=p2; /把m值赋给新的结点数据域，新结点的左右指针域置空，并把新的结点赋给p1的右孩子指针域 return; 2、 编一程序，实现二叉树左右子树交换。二叉树采用二叉链表存储方式。这个二叉树由键盘输入建立也可在程序中预先建立。#include <stdio.h>#include <malloc.h>typedef struct node1 DATATYPE2 data; struct node1 *lchild, *rchild;BTCHINALR;BTCHINALR * createbt( )BTCHINALR *q;struct node1 *s50;int j,i,x;printf("建立二叉树，输入结点对应的编号和值nn");printf("i,x = ");scanf("%d,%c",&i,&x);while(i != 0 && x != '$') q = (BTCHINALR*)malloc(sizeof(BTCHINALR); /*建立一个新结点q*/ q->data = x; q->lchild = NULL; q->rchild = NULL; si = q; /*q新结点地址存入s指针数组中*/ if(i != 1) /*i = 1，q结点是根结点*/ j = i / 2; /*否则求q结点的双亲结点的编号j*/ if(i % 2 = 0) sj->lchild = q; /*q结点编号为偶数则挂在双亲结点j的左边*/ else sj->rchild = q; /*q结点编号为奇数则挂在双亲结点j的右边*/ printf("i,x = "); scanf("%d,%c",&i,&x);return s1; /*返回根结点地址*/BTCHINALR *change(BTCHINALR *bt)/*二叉树左右子树交换递归算法*/ BTCHINALR *p; if(q!=NULL) /如果树不为空 if(bt->lchild!=NULL && bt->rchild!=NULL) /如果这棵树的左子树不为空或右子树不为空 p=(BTCHINALR*)malloc(sizeof(BTCHINALR); p->data=bt->data; p->lchild=bt->lchild; p->rchild=NULL;/以上语句实现建立一个新的结点，作为左右子树交换的中间结点 bt->lchild=bt->rchild; bt->rchild=p->lchild;/以上两句实现左右子树交换 bt->lchild=change(bt->lchild); /实现以左子树为根结点的左右子树交换 bt->rchild=change(bt->rchild); /实现以右子树为根结点的左右子树交换 return bt;void inorder(BTCHINALR *bt)/*中序遍历二叉树(递归算法)*/if(bt != NULL)inorder(bt->lchild);printf("%c ",bt->data);inorder(bt->rchild);main() BTCHINALR *bt; bt=createbt(); printf("n 二叉树左右子树交换前中序遍历: "); inorder(bt); printf("n"); bt=change(bt); printf("n 二叉树左右子树交换后中序遍历: "); inorder(bt); printf("n");
