实验五、二叉树操作及应用
一、 实验目的
掌握二叉树的定义、结构特征，以及各种存储结构的特点及使用范围，各种遍历算法。掌握用指针类型描述、访问和处理二叉树的运算。掌握前序或中序的非递归遍历算法。
二、 实验要求
有如下二叉树：
程序代码给出了该二叉树的链式存储结构的建立、前序、中序、后序遍历的算法，同时也给出了查询“E”是否在二叉树里的代码。代码有三处错误，有标识，属于逻辑错误，对照书中的代码仔细分析后，请修改了在电脑里运行。
#include <stdlib.h> #include <stdio.h> typedef char DataType; typedef struct Node { DataType data;/数据域/ struct Node *leftChild;/左子树指针/ struct Node *rightChild;/右子树指针/ }BiTreeNode;/结点的结构体定义/ /初始化创建二叉树的头结点/ void Initiate(BiTreeNode **root) { *root = (BiTreeNode *)malloc(sizeof(BiTreeNode)); (*root)->leftChild = NULL; (*root)->rightChild = NULL; } void Destroy(BiTreeNode **root) { if((*root) != NULL && (*root)->leftChild != NULL) Destroy(&(*root)->leftChild); if((*root) != NULL && (*root)->rightChild != NULL) Destroy(&(*root)->rightChild); free(*root); } /若当前结点curr非空，在curr的左子树插入元素值为x的新结点/ /原curr所指结点的左子树成为新插入结点的左子树/ /若插入成功返回新插入结点的指针，否则返回空指针/ BiTreeNode *InsertLeftNode(BiTreeNode *curr, DataType x) { BiTreeNode *s, *t; if(curr == NULL) return NULL; t = curr->leftChild;/保存原curr所指结点的左子树指针/ s = (BiTreeNode *)malloc(sizeof(BiTreeNode)); s->data = x; s->leftChild = t;/新插入结点的左子树为原curr的左子树/ s->rightChild = NULL; curr->leftChild = s;/新结点成为curr的左子树/ return curr->leftChild;/返回新插入结点的指针/ } /若当前结点curr非空，在curr的右子树插入元素值为x的新结点/ /原curr所指结点的右子树成为新插入结点的右子树/ /若插入成功返回新插入结点的指针，否则返回空指针/ BiTreeNode *InsertRightNode(BiTreeNode *curr, DataType x) { BiTreeNode *s, *t; if(curr == NULL) return NULL; t = curr->rightChild;/保存原curr所指结点的右子树指针/ s = (BiTreeNode *)malloc(sizeof(BiTreeNode)); s->data = x; s->rightChild = t;/新插入结点的右子树为原curr的右子树/ s->leftChild = NULL; curr->rightChild = s;/新结点成为curr的右子树/ return curr->rightChild;/返回新插入结点的指针/ } void PreOrder(BiTreeNode *t, void visit(DataType item)) //使用visit(item)函数前序遍历二叉树t { if(t != NULL) {//此小段有一处错误 visit(t->data); PreOrder(t-> rightChild, visit); PreOrder(t-> leftChild, visit); } } void InOrder(BiTreeNode *t, void visit(DataType item)) //使用visit(item)函数中序遍历二叉树t { if(t != NULL) {//此小段有一处错误 InOrder(t->leftChild, visit); InOrder(t->rightChild, visit); visit(t->data); } } void PostOrder(BiTreeNode *t, void visit(DataType item)) //使用visit(item)函数后序遍历二叉树t { if(t != NULL) {//此小段有一处错误 visit(t->data); PostOrder(t->leftChild, visit); PostOrder(t->rightChild, visit); } } void Visit(DataType item) { printf("%c ", item); } BiTreeNode *Search(BiTreeNode *root, DataType x)//需找元素x是否在二叉树中 { BiTreeNode *find=NULL; if(root!=NULL) { if(root->data == x) find=root; else { find=Search(root->leftChild,x); if(find==NULL) find=Search(root->rightChild,x); } } return find; } void main(void) { BiTreeNode *root, *p, *pp,*find; char x=‘E’; Initiate(&root); p = InsertLeftNode(root, ‘A’); p = InsertLeftNode(p, ‘B’); p = InsertLeftNode(p, ‘D’); p = InsertRightNode(p, ‘G’); p = InsertRightNode(root->leftChild, ‘C’); pp = p; InsertLeftNode(p, ‘E’); InsertRightNode(pp, ‘F’); printf(“前序遍历：”); PreOrder(root->leftChild, Visit); printf("\n中序遍历："); InOrder(root->leftChild, Visit); printf("\n后序遍历："); PostOrder(root->leftChild, Visit); find=Search(root,x); if(find!=NULL) printf("\n数据元素%c在二叉树中 \n",x); else printf("\n数据元素%c不在二叉树中 \n",x); Destroy(&root); }
三、 实验任务：
1.改正程序错误。
2.编写二叉树的前序（或中序）的非递归遍历算法并进行测试。
#include using namespace std; stack s; BiTreeNode *p; s.push§; s.top(); s.pop(); s.empty()_
3.完成实验报告的撰写。
代码如下
#include <stdlib.h> #include <stdio.h> typedef char DataType; typedef struct Node { DataType data;/*数据域*/ struct Node *leftChild;/*左子树指针*/ struct Node *rightChild;/*右子树指针*/ } BiTreeNode; /*结点的结构体定义*/ /*初始化创建二叉树的头结点*/ void Initiate(BiTreeNode **root) { *root = (BiTreeNode *)malloc(sizeof(BiTreeNode)); (*root)->leftChild = NULL; (*root)->rightChild = NULL; } void Destroy(BiTreeNode **root) { if((*root) != NULL && (*root)->leftChild != NULL) Destroy(&(*root)->leftChild); if((*root) != NULL && (*root)->rightChild != NULL) Destroy(&(*root)->rightChild); free(*root); } /*若当前结点curr非空，在curr的左子树插入元素值为x的新结点*/ /*原curr所指结点的左子树成为新插入结点的左子树*/ /*若插入成功返回新插入结点的指针，否则返回空指针*/ BiTreeNode *InsertLeftNode(BiTreeNode *curr, DataType x) { BiTreeNode *s, *t; if(curr == NULL) return NULL; t = curr->leftChild;/*保存原curr所指结点的左子树指针*/ s = (BiTreeNode *)malloc(sizeof(BiTreeNode)); s->data = x; s->leftChild = t;/*新插入结点的左子树为原curr的左子树*/ s->rightChild = NULL; curr->leftChild = s;/*新结点成为curr的左子树*/ return curr->leftChild;/*返回新插入结点的指针*/ } /*若当前结点curr非空，在curr的右子树插入元素值为x的新结点*/ /*原curr所指结点的右子树成为新插入结点的右子树*/ /*若插入成功返回新插入结点的指针，否则返回空指针*/ BiTreeNode *InsertRightNode(BiTreeNode *curr, DataType x) { BiTreeNode *s, *t; if(curr == NULL) return NULL; t = curr->rightChild;/*保存原curr所指结点的右子树指针*/ s = (BiTreeNode *)malloc(sizeof(BiTreeNode)); s->data = x; s->rightChild = t;/*新插入结点的右子树为原curr的右子树*/ s->leftChild = NULL; curr->rightChild = s;/*新结点成为curr的右子树*/ return curr->rightChild;/*返回新插入结点的指针*/ } void PreOrder(BiTreeNode *t, void visit(DataType item)) //使用visit(item)函数前序遍历二叉树t { if(t != NULL) { //此小段有一处错误 已改 visit(t->data); PreOrder(t-> leftChild, visit); PreOrder(t-> rightChild, visit); } } void InOrder(BiTreeNode *t, void visit(DataType item)) //使用visit(item)函数中序遍历二叉树t { if(t != NULL) { //此小段有一处错误 已改 InOrder(t->leftChild, visit); visit(t->data); InOrder(t->rightChild, visit); } } void PostOrder(BiTreeNode *t, void visit(DataType item)) //使用visit(item)函数后序遍历二叉树t { if(t != NULL) { //此小段有一处错误 已改 PostOrder(t->leftChild, visit); PostOrder(t->rightChild, visit); visit(t->data); } } void Visit(DataType item) { printf("%c ", item); } BiTreeNode *Search(BiTreeNode *root, DataType x)//需找元素x是否在二叉树中 { BiTreeNode *find=NULL; if(root!=NULL) { if(root->data==x) find=root; else { find=Search(root->leftChild,x); if(find==NULL) find=Search(root->rightChild,x); } } return find; } int main() { BiTreeNode *root, *p, *pp,*find; char x='E'; Initiate(&root); p = InsertLeftNode(root, 'A'); p = InsertLeftNode(p, 'B'); p = InsertLeftNode(p, 'D'); p = InsertRightNode(p, 'G'); p = InsertRightNode(root->leftChild, 'C'); pp = p; InsertLeftNode(p, 'E'); InsertRightNode(pp, 'F'); printf("前序遍历："); PreOrder(root->leftChild, Visit); printf("\n中序遍历："); InOrder(root->leftChild, Visit); printf("\n后序遍历："); PostOrder(root->leftChild, Visit); find=Search(root,x); if(find!=NULL) printf("\n数据元素%c在二叉树中 \n",x); else printf("\n数据元素%c不在二叉树中 \n",x); Destroy(&root); }
第二题
#include <stdlib.h> #include <stdio.h> #define MAX 100 typedef char DataType; typedef struct Node { DataType data;/*数据域*/ struct Node *leftChild;/*左子树指针*/ struct Node *rightChild;/*右子树指针*/ } BiTreeNode; /*结点的结构体定义*/ /*初始化创建二叉树的头结点*/ void Initiate(BiTreeNode **root) { *root = (BiTreeNode *)malloc(sizeof(BiTreeNode)); (*root)->leftChild = NULL; (*root)->rightChild = NULL; } void Destroy(BiTreeNode **root) { if((*root) != NULL && (*root)->leftChild != NULL) Destroy(&(*root)->leftChild); if((*root) != NULL && (*root)->rightChild != NULL) Destroy(&(*root)->rightChild); free(*root); } /*若当前结点curr非空，在curr的左子树插入元素值为x的新结点*/ /*原curr所指结点的左子树成为新插入结点的左子树*/ /*若插入成功返回新插入结点的指针，否则返回空指针*/ BiTreeNode *InsertLeftNode(BiTreeNode *curr, DataType x) { BiTreeNode *s, *t; if(curr == NULL) return NULL; t = curr->leftChild;/*保存原curr所指结点的左子树指针*/ s = (BiTreeNode *)malloc(sizeof(BiTreeNode)); s->data = x; s->leftChild = t;/*新插入结点的左子树为原curr的左子树*/ s->rightChild = NULL; curr->leftChild = s;/*新结点成为curr的左子树*/ return curr->leftChild;/*返回新插入结点的指针*/ } /*若当前结点curr非空，在curr的右子树插入元素值为x的新结点*/ /*原curr所指结点的右子树成为新插入结点的右子树*/ /*若插入成功返回新插入结点的指针，否则返回空指针*/ BiTreeNode *InsertRightNode(BiTreeNode *curr, DataType x) { BiTreeNode *s, *t; if(curr == NULL) return NULL; t = curr->rightChild;/*保存原curr所指结点的右子树指针*/ s = (BiTreeNode *)malloc(sizeof(BiTreeNode)); s->data = x; s->rightChild = t;/*新插入结点的右子树为原curr的右子树*/ s->leftChild = NULL; curr->rightChild = s;/*新结点成为curr的右子树*/ return curr->rightChild;/*返回新插入结点的指针*/ } //前序遍历非递归算法 void Prev(Node *root) { Node *p,*node[MAX]; int top=0; p=root; do { while(p!=NULL) { printf("%c",p->data); node[top]=p; top++; p=p->leftChild; } if(top>0) { top--; p=node[top]; p=p->rightChild; } } while(top>0||p!=NULL); } //中序遍历非递归算法 void min(Node *root) { Node *p,*node[MAX]; int top=0; p=root; do { while(p!=NULL) { node[top]=p; top++; p=p->leftChild; } if(top>0) { top--; p=node[top]; printf("%c",p->data); p=p->rightChild; } } while(top>0||p!=NULL); } BiTreeNode *Search(BiTreeNode *root, DataType x)//需找元素x是否在二叉树中 { BiTreeNode *find=NULL; if(root!=NULL) { if(root->data==x) find=root; else { find=Search(root->leftChild,x); if(find==NULL) find=Search(root->rightChild,x); } } return find; } int main(void) { BiTreeNode *root, *p, *pp,*find; char x='E'; Initiate(&root); p = InsertLeftNode(root, 'A'); p = InsertLeftNode(p, 'B'); p = InsertLeftNode(p, 'D'); p = InsertRightNode(p, 'G'); p = InsertRightNode(root->leftChild, 'C'); pp = p; InsertLeftNode(p, 'E'); InsertRightNode(pp, 'F'); printf("前序遍历："); Prev(root->leftChild); printf("\n中序遍历："); min(root->leftChild); find=Search(root,x); if(find!=NULL) printf("\n数据元素%c在二叉树中 \n",x); else printf("\n数据元素%c不在二叉树中 \n",x); Destroy(&root); }
