数据结构二叉树程序

《数据结构二叉树程序》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、#include#include#defineQueueMaxSize20#defineStackMaxSize10typedefcharElemType;structBTreeNode{ElemTypedata;structBTreeNode*left;structBTreeNode*right;};/*前序遍历*/voidPreorder(structBTreeNode*BT){if(BT!=NULL){printf("%c",BT->data);Preorder(BT

2、->left);Preorder(BT->right);}}/*中序遍历*/voidInorder(structBTreeNode*BT){if(BT!=NULL){Inorder(BT->left);printf("%c",BT->data);Inorder(BT->right);}}/*后序遍历*/voidPostorder(structBTreeNode*BT){if(BT!=NULL){Postorder(BT->left);Postorder(BT->right);printf("%c",BT->da

3、ta);}}/*按层遍历*/voidLevelorder(structBTreeNode*BT){structBTreeNode*p;structBTreeNode*q[QueueMaxSize];intfront=0,rear=0;if(BT!=NULL){rear=(rear+1)%QueueMaxSize;q[rear]=BT;}while(front!=rear){front=(front+1)%QueueMaxSize;p=q[front];printf("%c",p->data);if(p->lef

4、t!=NULL){rear=(rear+1)%QueueMaxSize;q[rear]=p->left;}if(p->right!=NULL){rear=(rear+1)%QueueMaxSize;q[rear]=p->right;}}}/*初始化二叉树*/voidInitBTree(structBTreeNode**BT){*BT=NULL;}/*建立二叉树*/voidCleateBTree(structBTreeNode**BT,char*a){structBTreeNode*p;structBTreeNo

5、de*s[StackMaxSize];inttop=-1;intk;inti=0;*BT=NULL;while(a[i]){switch(a[i]){case'':break;case'(':if(top==StackMaxSize-1){printf("栈空间太小，需要增加StackMaxSize!");exit(1);}top++;s[top]=p;k=1;break;case')':if(top==-1){printf("二叉树广义表字符串错！");exit(1);}top--;break;cas

6、e',':k=2;break;default:p=(structBTreeNode*)malloc(sizeof(structBTreeNode));p->data=a[i];p->left=p->right=NULL;if(*BT==NULL)*BT=p;else{if(k==1)s[top]->left=p;elses[top]->right=p;}}/*switchend*/i++;}}/*检查二叉树是否为空*/intBTreeEmpty(structBTreeNode*BT){if(BT==NULL)r

7、eturn1;elsereturn0;}/*求二叉树深度*/intBTreeDepth(structBTreeNode*BT){if(BT==NULL)return0;else{intdep1=BTreeDepth(BT->left);intdep2=BTreeDepth(BT->right);if(dep1>dep2)returndep1+1;elsereturndep2+1;}}/*从二叉树中查找值为x的结点，若存在则返回元素存储位置，否则返回控值*/ElemType*FindBTree(structBTr

8、eeNode*BT,ElemTypex){if(BT==NULL)returnNULL;else{if(BT->data==x)return&(BT->data);else{ElemType*p;if(p=FindBTree(BT->left,x))returnp;if(p=FindBTree(BT->right,x))returnp;returnNULL;}}}/*输出二叉树*/vo