西安交大朱站立数据结构

本文为二叉链存储结构的二叉树操作实现，实现了二叉树的定义、插入数据、删除数据、撤销以及二叉树的打印、前序遍历、中序遍历、后序遍历等。本项目工程包含2个头文件(BiTree.h、BiTreeTraverse.h)和一个源文件(BiTree.cpp)。头文件1BiTree.htypedefstructNode{DataTypedata; 〃数据域structNode*leftChild; 〃左子树指针structNode*rightChild;〃右子树指针}BiTreeNode; 〃结点的结构体定义/*初始化创建二叉树的头结点*/voidInitiate(BiTreeNode**root){*root=(BiTreeNode*)malloc(sizeof(BiTreeNode));(*root)->leftChild=NULL;(*root)->rightChild=NULL;}/*若当前结点curr非空，在curr的左子树插入元素之为x的新结点*//*原curr所指结点的左子树成为新插入结点的左子树*//*插入成功则返回新插入结点的指针，否则返回空指针*/BiTreeNode*InsertLeftNode(BiTreeNode*curr,DataTypex){BiTreeNode*s,*t;if(curr==NULL)returnNULL;t=curr->leftChild; /*保留原curr所指结点的左子树指针*/s=(BiTreeNode*)malloc(sizeof(BiTreeNode));s->data=x;s->leftChild=t; /*新插入结点的左子树为原curr的左子树*/s->rightChild=NULL;curr->leftChild=s; /*新结点成为curr的左子树*/returncurr->leftChild;/*返回新插入结点的指针*/}/*若当前结点curr非空，在curr的右子树插入元素之为x的新结点*//*原curr所指结点的右子树成为新插入结点的左子树*//*插入成功则返回新插入结点的指针，否则返回空指针*/BiTreeNode*InsertRightNode(BiTreeNode*curr,DataTypex){BiTreeNode*s,*t;if(curr==NULL)returnNULL;t=curr->rightChild; /*保留原curr所指结点的右子树指针*/s=(BiTreeNode*)malloc(sizeof(BiTreeNode));s->data=x;s->rightChild=t; /*新插入结点的右子树为原curr的左子树*/s->leftChild=NULL;curr->rightChild=s; /*新结点成为curr的右子树*/returncurr->rightChild;/*返回新插入结点的指针*/}voidDestory(BiTreeNode**root){//二叉树撤销操作if((*root)!=NULL&&(*root)->leftChild!=NULL)Destory(&(*root)->leftChild);if((*root)!=NULL&&(*root)->rightChild!=NULL)Destory(&(*root)->rightChild);free(*root);}/*若curr非空，删除curr所在结点的左子树*//*删除成功则返回删除结点的双亲指针，否则返回空*/BiTreeNode*DeleteLeftTree(BiTreeNode*curr){if(curr==NULLIIcurr->leftChild==NULL)returnNULL;Destory(&curr->leftChild);curr->leftChild=NULL;returncurr;}/*若curr非空，删除curr所在结点的右子树*//*删除成功则返回删除结点的双亲指针，否则返回空*/BiTreeNode*DeleteRightTree(BiTreeNode*curr){if(curr==NULLIIcurr->rightChild==NULL)returnNULL;Destory(&curr->rightChild);curr->rightChild=NULL;returncurr;}头文件2BiTreeTraverse.hvoidPreOrder(BiTreeNode*t,voidVisit(DataTypeitem)){//前序遍历二叉树t,访问操作为Visit()函数if(t!=NULL){Visit(t->data);PreOrder(t->leftChild,Visit);PreOrder(t->rightChild,Visit);}}voidInOrder(BiTreeNode*t,voidVisit(DataTypeitem)){//中序遍历二叉树t,访问操作为Visit()函数if(t!=NULL){PreOrder(t->leftChild,Visit);Visit(t->data);PreOrder(t->rightChild,Visit);}}voidPostOrder(BiTreeNode*t,voidVisit(DataTypeitem)){//后序遍历二叉树t,访问操作为Visit()函数if(t!=NULL){PreOrder(t->leftChild,Visit);PreOrder(t->rightChild,Visit);Visit(t->data);}}测试主函数BiTree・cpp#include<stdlib.h>#include<stdio.h>typedefcharDataType;#include"BiTree.h"#include"BiTreeTraverse.h"voidVisit(DataTypeitem){//定义访问函数printf("%c",item);}voidPrintBiTree(BiTreeNode*bt,intn){//定义打印函数，递归调用inti;if(bt==NULL)return; 〃递归出口PrintBiTree(bt->rightChild,n+l);〃遍历打印右子树〃访问根结点for(i=0;ivn;i++)printf(” ");if(n>=0){printf("---");printf(”％c\n",bt->data);}PrintBiTree(bt->leftChild,n+1);〃遍历打印左子树}voidmain(void){//测试主函数BiTreeNode*root,*p,*pp;〃遍历二叉树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');PrintBiTree(root,0);printf（"前序遍历：”）;P