西安交大朱站立數(shù)據(jù)結(jié)構(gòu)

本文為二叉鏈存儲結(jié)構(gòu)的二叉樹操作實現(xiàn)，實現(xiàn)了二叉樹的定義、插入數(shù)據(jù)、刪除數(shù)據(jù)、撤銷以及二叉樹的打印、前序遍歷、中序遍歷、后序遍歷等。本項目工程包含2個頭文件(BiTree.h、BiTreeTraverse.h)和一個源文件(BiTree.cpp)。頭文件1BiTree.htypedefstructNode{DataTypedata; 〃數(shù)據(jù)域structNode*leftChild; 〃左子樹指針structNode*rightChild;〃右子樹指針}BiTreeNode; 〃結(jié)點的結(jié)構(gòu)體定義/*初始化創(chuàng)建二叉樹的頭結(jié)點*/voidInitiate(BiTreeNode**root){*root=(BiTreeNode*)malloc(sizeof(BiTreeNode));(*root)->leftChild=NULL;(*root)->rightChild=NULL;}/*若當(dāng)前結(jié)點curr非空，在curr的左子樹插入元素之為x的新結(jié)點*//*原curr所指結(jié)點的左子樹成為新插入結(jié)點的左子樹*//*插入成功則返回新插入結(jié)點的指針，否則返回空指針*/BiTreeNode*InsertLeftNode(BiTreeNode*curr,DataTypex){BiTreeNode*s,*t;if(curr==NULL)returnNULL;t=curr->leftChild; /*保留原curr所指結(jié)點的左子樹指針*/s=(BiTreeNode*)malloc(sizeof(BiTreeNode));s->data=x;s->leftChild=t; /*新插入結(jié)點的左子樹為原curr的左子樹*/s->rightChild=NULL;curr->leftChild=s; /*新結(jié)點成為curr的左子樹*/returncurr->leftChild;/*返回新插入結(jié)點的指針*/}/*若當(dāng)前結(jié)點curr非空，在curr的右子樹插入元素之為x的新結(jié)點*//*原curr所指結(jié)點的右子樹成為新插入結(jié)點的左子樹*//*插入成功則返回新插入結(jié)點的指針，否則返回空指針*/BiTreeNode*InsertRightNode(BiTreeNode*curr,DataTypex){BiTreeNode*s,*t;if(curr==NULL)returnNULL;t=curr->rightChild; /*保留原curr所指結(jié)點的右子樹指針*/s=(BiTreeNode*)malloc(sizeof(BiTreeNode));s->data=x;s->rightChild=t; /*新插入結(jié)點的右子樹為原curr的左子樹*/s->leftChild=NULL;curr->rightChild=s; /*新結(jié)點成為curr的右子樹*/returncurr->rightChild;/*返回新插入結(jié)點的指針*/}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所在結(jié)點的左子樹*//*刪除成功則返回刪除結(jié)點的雙親指針，否則返回空*/BiTreeNode*DeleteLeftTree(BiTreeNode*curr){if(curr==NULLIIcurr->leftChild==NULL)returnNULL;Destory(&curr->leftChild);curr->leftChild=NULL;returncurr;}/*若curr非空，刪除curr所在結(jié)點的右子樹*//*刪除成功則返回刪除結(jié)點的雙親指針，否則返回空*/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()函數(shù)if(t!=NULL){Visit(t->data);PreOrder(t->leftChild,Visit);PreOrder(t->rightChild,Visit);}}voidInOrder(BiTreeNode*t,voidVisit(DataTypeitem)){//中序遍歷二叉樹t,訪問操作為Visit()函數(shù)if(t!=NULL){PreOrder(t->leftChild,Visit);Visit(t->data);PreOrder(t->rightChild,Visit);}}voidPostOrder(BiTreeNode*t,voidVisit(DataTypeitem)){//后序遍歷二叉樹t,訪問操作為Visit()函數(shù)if(t!=NULL){PreOrder(t->leftChild,Visit);PreOrder(t->rightChild,Visit);Visit(t->data);}}測試主函數(shù)BiTree?cpp#include<stdlib.h>#include<stdio.h>typedefcharDataType;#include"BiTree.h"#include"BiTreeTraverse.h"voidVisit(DataTypeitem){//定義訪問函數(shù)printf("%c",item);}voidPrintBiTree(BiTreeNode*bt,intn){//定義打印函數(shù)，遞歸調(diào)用inti;if(bt==NULL)return; 〃遞歸出口PrintBiTree(bt->rightChild,n+l);〃遍歷打印右子樹〃訪問根結(jié)點for(i=0;ivn;i++)printf(” ");if(n>=0){printf("---");printf(”％c\n",bt->data);}PrintBiTree(bt->leftChild,n+1);〃遍歷打印左子樹}voidmain(void){//測試主函數(shù)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