2022年数据结构二叉树程序 .pdf

《2022年数据结构二叉树程序 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构二叉树程序 .pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、#include #include #define QueueMaxSize 20 #define StackMaxSize 10 typedef char ElemType; struct BTreeNode ElemType data; struct BTreeNode* left; struct BTreeNode* right; ; /*前序遍历 */ void Preorder(struct BTreeNode * BT) if(BT!=NULL) printf(%c ,BT-data); Preorder(BT-left); Preorder(BT-right); /*中序遍历 *

2、/ void Inorder(struct BTreeNode * BT) if(BT!=NULL) Inorder(BT-left); printf(%c ,BT-data); Inorder(BT-right); /*后序遍历 */ void Postorder(struct BTreeNode * BT) if(BT!=NULL) Postorder(BT-left); Postorder(BT-right); printf(%c ,BT-data); /*按层遍历 */ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名

3、师精心整理 - - - - - - - 第 1 页，共 5 页 - - - - - - - - - void Levelorder(struct BTreeNode * BT) struct BTreeNode * p; struct BTreeNode * qQueueMaxSize; int front=0,rear=0; if(BT!=NULL) rear=(rear+1)%QueueMaxSize; qrear=BT; while (front!=rear) front=(front+1)%QueueMaxSize; p=qfront; printf(%c ,p-data); if(p

4、-left!=NULL) rear=(rear+1)%QueueMaxSize; qrear=p-left; if(p-right!=NULL) rear=(rear+1)%QueueMaxSize; qrear=p-right; /*初始化二叉树 */ void InitBTree(struct BTreeNode* BT) *BT=NULL; /*建立二叉树 */ void CleateBTree(struct BTreeNode* BT,char* a) struct BTreeNode* p; struct BTreeNode* sStackMaxSize; int top=-1; i

5、nt k ; int i=0; *BT=NULL; while (ai) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 5 页 - - - - - - - - - switch (ai) case : break ; case (: if (top=StackMaxSize-1) printf ( 栈空间太小，需要增加StackMaxSize!n); exit (1); top+ ; stop=p; k=1; break ; case ): if (top=-1) pr

6、intf ( 二叉树广义表字符串错！n); exit (1); top- ; break ; case ,: k=2; break ; default: p=(struct BTreeNode *)malloc(sizeof(struct BTreeNode); p-data=ai; p-left=p-right=NULL; if (*BT=NULL) *BT=p; else if (k=1) stop-left=p; else stop-right=p; /*switch end*/ i+; /*检查二叉树是否为空*/ int BTreeEmpty(struct BTreeNode* BT)

7、 if (BT=NULL) return 1 ; else return 0 ; /* 求二叉树深度*/ int BTreeDepth(struct BTreeNode* BT) if(BT=NULL) return 0; else 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 5 页 - - - - - - - - - int dep1=BTreeDepth(BT-left); int dep2=BTreeDepth(BT-right); if(dep1dep2) r

8、eturn dep1+1; else return dep2+1; /*从二叉树中查找值为x 的结点，若存在则返回元素存储位置，否则返回控值*/ ElemType* FindBTree(struct BTreeNode* BT,ElemType x) if (BT=NULL) return NULL; else if (BT-data=x) return &(BT-data); else ElemType* p; if (p=FindBTree(BT-left,x) return p ; if (p=FindBTree(BT-right,x) return p ; return NULL ;

9、/*输出二叉树 */ void PrintBTree(struct BTreeNode* BT) if (BT!=NULL) printf (%c,BT-data); if(BT-left!=NULL | BT-right!=NULL) printf () ; PrintBTree (BT-left) ; if (BT-right!=NULL) printf (,); PrintBTree(BT-right); printf (); /*清除二叉树，使之变为一课空树*/ void ClearBTree(struct BTreeNode* BT) if (*BT!=NULL) ClearBTre

10、e(&(*BT)-left); ClearBTree(&(*BT)-right); free(*BT); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 5 页 - - - - - - - - - *BT=NULL; /*假定采用如下程序调试上述对二叉树操作的各种算法*/ /*#include 二叉树操作 .c */ /*该程序文件保存有对二叉树运算的各种算法*/ void main () struct BTreeNode* bt; char b50; ElemType

11、x ,*px; InitBTree(&bt) ; printf ( 输入二叉树广义表字符串：n); scanf (%s,b); CleateBTree(&bt,b); PrintBTree(bt); printf (n); printf ( 前序： ); Preorder(bt); printf (n); printf ( 中序： ); Inorder(bt); printf (n); printf ( 后序： ); Postorder(bt); printf (n); printf ( 按层： ); Levelorder(bt); printf (n); printf ( 输入一个待查的字符：n); scanf ( %c,&x); px=FindBTree(bt,x); if (px) printf ( 查找成功： %cn,*px); else printf ( 查找失败： %cn); printf ( 二叉树的深度为：); printf (%dn,BTreeDepth(bt); ClearBTree(&bt); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 5 页 - - - - - - - - -