二叉树树的基本操作（初始化、遍历、求深度等等）

#include<stdio.h> #include<stdlib.h> #include"data.h" #include"BTree.h" #define STACKSIZE 20 #define QUEUESIZE 20 //初始化二叉树 void InitBTree(BTree **bt) { *bt=NULL; } //用广义表的表示的二叉树建立对应的存储结构，假设要存储的为字符型 void CreateBTree(BTree **bt,char *a) { int i=0,k=0; BTree *p=NULL; BTree *s[STACKSIZE]={0}; //////////////// int top=-1; *bt=NULL; while(a[i]) { switch(a[i]) { case ' ': break; case '(': if(top>=STACKSIZE-1) { printf("栈空间不够!!!\n"); exit(0); } if(p==NULL) { printf("输入的字符串有错误!\n"); exit(0); } top++; s[top]=p; k=1; break; case ',': k=2; break; case ')': if(top==-1) { printf("输入的字符串有错误!!\n"); exit(0); } top--; break; default: p=malloc(sizeof(BTree)); p->data=a[i]; p->left=NULL; p->right=NULL; if(*bt==NULL) *bt=p; else { if(k==1) s[top]->left=p; else s[top]->right=p; } } i++; } } //判断二叉树是否为空 int IsEmptyBTree(BTree *bt) { return bt==NULL?1:0; } //遍历二叉树，四种方法 //先序的方法输出 void PreOrder(BTree *bt) { if(bt!=NULL) { printf("%c ",bt->data); PreOrder(bt->left); PreOrder(bt->right); } } //中序的方法输出 void MidOrder(BTree *bt) { if(bt!=NULL) { MidOrder(bt->left); printf("%c ",bt->data); MidOrder(bt->right); } } //后序的方法输出 void PostOrder(BTree *bt) { if(bt!=NULL) { PostOrder(bt->left); PostOrder(bt->right); printf("%c ",bt->data); } } //按层的顺序输出 void LevelOrder(BTree *bt) { BTree *p=NULL; BTree *q[QUEUESIZE]={0}; //////////////// int front=0,rear=0; if(bt) { rear=(rear+1)%QUEUESIZE; q[rear]=bt; } while(front!=rear) { front=(front+1)%QUEUESIZE; p=q[front]; printf("%c ",p->data); if(p->left) { rear=(rear+1)%QUEUESIZE; q[rear]=p->left; } if(p->right) { rear=(rear+1)%QUEUESIZE; q[rear]=p->right; } } } //查找对应结点位置 ElemType * SearchBTree(BTree *bt,ElemType e) { if(bt==NULL) return NULL; else { if(bt->data==e) return &(bt->data); else { ElemType *p; if(p=SearchBTree(bt->left,e)) return p; if(p=SearchBTree(bt->right,e)) return p; return NULL; } } } //求出一棵树的深度并返回 int DeepBTree(BTree *bt) { if(bt==NULL) return 0; else { int deep1=DeepBTree(bt->left)+1; int deep2=DeepBTree(bt->right)+1; return deep1>deep2?deep1:deep2; } } //求一棵二叉树的结点总数 int BTreeCount(BTree *bt) { if(bt==NULL) return 0; else return BTreeCount(bt->left)+BTreeCount(bt->right)+1; } //按照广义表的形式输出二叉树 void PrintBTree(BTree *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(BTree **bt) { if(*bt!=NULL) { ClearBTree(&((*bt)->left)); ClearBTree(&((*bt)->right)); free(*bt); *bt=NULL; } }