数据结构二叉树程序.doc

#include#include#define QueueMaxSize 20#define StackMaxSize 10typedef char ElemType;struct BTreeNodeElemType 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);/*中序遍历*/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);/*按层遍历*/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-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;int k ;int i=0;*BT=NULL;while (ai)switch (ai) case :break ;case (:if (top=StackMaxSize-1) printf (栈空间太小，需要增加StackMaxSize!n);exit (1);top+ ; stop=p; k=1;break ;case ):if (top=-1) printf (二叉树广义表字符串错！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)if (BT=NULL) return 1 ;else return 0 ;/* 求二叉树深度 */int BTreeDepth(struct BTreeNode* BT)if(BT=NULL)return 0;else int dep1=BTreeDepth(BT-left);int dep2=BTreeDepth(BT-right);if(dep1dep2)return dep1+1;elsereturn 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 ; /*输出二叉树*/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) ClearBTree(&(*BT)-left); ClearBTree(&(*BT)-right);free(*BT);*BT=NULL;/*假定采用如下程序调试上述对二叉树操作的各种算法*/*#include 二叉树操作.c */ /*该程序文件保存有对二叉树运算的各种算法*/void main ()struct BTreeNode* bt;char b50;ElemType 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