数据结构的二叉树

#include <stdio.h> #include <stdlib.h> #include "../header/bitree.h" #include "../header/queue.h" #include "../header/stack.h" #include "../header/expr.h" Status CreateBiTree( BiTree & T) //操作结果：构造二叉树T。 //先序输入二叉树 { char ch; scanf( "%c", &ch ); if( ch == ' ' ) T = NULL; else { if( ! ( T = ( BiTree )malloc( sizeof( BiTNode ) ) ) ) return ERROR; T->data = ch; CreateBiTree( T->lchild ); CreateBiTree( T->rchild ); } return OK; } Status ArrayCreate( BiTree &T, char *ch, int &i ) { //int i = 0; if( !ch[i] ) return OK; if( ch[i] == ' ' ) T = NULL; else { if( ! ( T = ( BiTree )malloc( sizeof( BiTNode ) ) ) ) return ERROR; T->data = ch[i]; //if( T->data == '+' || T->data == '-' || T->data == '*' || T->data == '/' || T->data == '^' ) ArrayCreate( T->lchild, ch, ++i ); ArrayCreate( T->rchild, ch, ++i ); } return OK; } Status Create( BiTree &T ) //操作结果：构造二叉树T。 //有文字说明先序输入二叉树 { printf("请以先序顺序输入您要建立的二叉树(空孩子用空格表示):\n"); if( CreateBiTree( T ) ) if( PreOrderTraverse( T, Visit ) )//前序遍历输出 { printf("\n"); return OK; } return FALSE; } Status InitBiTree(BiTree & T) //操作结果：构造空二叉树。 { T = NULL; return OK; } Status DestroyBiTree( BiTree &T ) //初始条件：二叉树T存在。 //操作结果：销毁二叉树T。 { if( T ) { if( DestroyBiTree( T->lchild ) ) if( DestroyBiTree( T->lchild ) ) { free( T ); return OK; } return ERROR; } else return OK; } Status ClearBiTree(BiTree &T)//把二叉树T清空 { if( T ) { ClearBiTree( T->lchild ); ClearBiTree( T->rchild ); T->lchild=NULL; T->rchild=NULL; T->data=0; return OK; } return ERROR; } Status BiTreeEmpty(BiTree & T ) //初始条件：二叉树T存在。 //操作结果：若T为空二叉树，则返回TRUE，否则FALSE。 { return T == NULL; } int BiTreeDepth( BiTree T ) //初始条件：二叉树T存在。 //操作结果：返回T的深度。 { int ldep,rdep; if( !T ) return 0; //空树的高度为0 else { ldep = BiTreeDepth( T->lchild ); //求左子树的高度 rdep = BiTreeDepth( T->rchild ); //求右子树的高度 return ( ldep > rdep ) ? ( ldep + 1 ) : ( rdep + 1 ); } } int Counter( BiTree T ) //初始条件：二叉树T存在。 //操作结果：返回T的结点的个数 { //int s; if( !T ) return 0; else return Counter( T->lchild ) + Counter( T->rchild ) + 1; } int NumLeaf( BiTree T ) //初始条件：二叉树T存在。 //操作结果：返回T的叶子个数 { if( !T ) return 0; else if( !T->lchild && !T->rchild ) return 1; else return NumLeaf( T->lchild ) + NumLeaf( T->rchild ); } void WriteExpr( BiTree T ) //用带括号的中序表示式输出 { if( T ) { printf("%c", T->data ); if( T->lchild || T->rchild ) { printf( "(" ); WriteExpr( T->lchild ); if( T->rchild ) printf( "," ); WriteExpr( T->rchild ); printf( ")" ); } } } int BiTreeWidth( BiTree T ) //初始条件：二叉树T存在。 //操作结果：返回T的的宽度 //宽度：具有结点数最多的那一层上的结点个数 { struct { int l; //结点层次编号 BiTree p; //结点指针 }Que[MAXSIZE]; int front = 0, rear = 0 ; int num ,max,i,n; if( T ) { rear++; Que[rear].p = T; Que[rear].l = 1; while(rear!=front) { front++; T = Que[front].p; num = Que[front].l; if( T->lchild ) { rear++; Que[rear].p = T->lchild; Que[rear].l = num +1; } if( T->rchild ) { rear++; Que[rear].p = T->rchild; Que[rear].l = num + 1; } } max = 0; num = 1; i = 1; while( i <= rear ) { n=0; while( i <= rear && Que[i].l == num ) { n++; i++; } num = Que[i].l; if( n > max ) max = n; } return max; } else return 0; } BiTree Root( BiTree T) //初始条件：二叉树T存在。 //操作结果：返回T的根。 { return T; } Status BTValue( BiTree T,TElemType & e )//????????????????????????????? //初始条件：二叉树T存在，e是T中某个结点。 //操作结果：返回e的值。 { if( T ) { e = T->data; return OK; } return FALSE; } Status Assign( BiTree &T, TElemType &e, TElemType value ) //初始条件：二叉树T存在，e是T中某个结点。 //操作结果：结点e赋值为value。 { if( T ) { if( T->data == e ) { T->data = value; return OK; //找到了 } if( !Assign( T->lchild, e, value ) ) //找不到 if( !Assign( T->rchild, e, value ) ) //找不到 return FALSE; return OK; } return FALSE;//是空树 } BiTree Parent( BiTree T, TElemType e ) //初始条件：二叉树T存在，e是T中某个结点。 //操作结果：若e是T的非根结点，则返回它的双亲，否则返回“空”。 { BiTree bt; if( T ) { if ( ( T->lchild )&& ( T->lchild->data == e ) || ( T->rchild ) && ( T->rchild->data == e ) ) return T; if( ! ( bt = Parent( T->lchild, e ) ) ) //找不到 if( ! ( bt = Parent( T->rchild, e ) ) ) //找不到 return NULL; return bt; } return NULL; } /*{ TElemType p = NULL; if (T -> data == e) return NULL; if (T -> rchild -> data == e || T -> lchild -> data == e) return T -> data; if (T -> lchild) p = Parent (T -> lchild, e); if (!p && T -> rchild) p = Parent (T -> rchild, e); return p; }*/ BiTree LeftChild( BiTree T, TElemType e ) //初始条件：二叉树T存在，e是T中某个结点。 //操作结果：返回e的左孩子。若e无左孩子，则返回“空”。 { BiTree bt; if( T ) { if ( T->data == e ) return T->lchild; if( !( bt = LeftChild( T->lchild, e ) ) ) //找不到 if( !( bt = LeftChild( T->rchild, e ) ) ) //找不到 return NULL; return bt; } return NULL; } BiTree RightChild( BiTree T, TElemType e ) //初始条件：二叉树T存在，e是T中某个结点。 //操作结果：返回e的右孩子。若e无左孩子，则返回“空”。 { BiTree bt; if( T ) { if ( T->data == e ) return T->rchild; if( !( bt = RightChild( T->lchild, e ) ) ) //找不到 if( !( bt = RightChild( T->rchild, e ) ) ) //找不到 return NULL; return bt; } return NULL; } BiTree LeftSibling( BiTree T, TElemType e ) //初始条件：二叉树T存在，e是T中某个结点。 //操作结果：返回e的左兄弟。若e 是T的左孩子或无左兄弟，则返回“空”。 { BiTree bt; if( T ) { if ( ( T->rchild ) && ( T->rchild->data == e ) ) return T->lchild; if( !( bt = LeftSibling( T->lchild, e ) ) ) //找不到 if( !( bt = LeftSibling( T->rchild, e ) ) ) //找不到 return NULL; return bt; } return NULL; } BiTree RightSibling( BiTree T, TElemType e ) //初始条件：二叉树T存在，e是T中某个结点。 //操作结果：返回e的右兄弟。若e是T的右孩子或无右兄弟，则返回“空”。 { BiTree bt; if( T ) { if ( ( T->lchild ) && ( T->lchild->data == e ) ) return T->rchild; if( !( bt = RightSibling( T->lchild, e ) ) ) //找不到 if( !( bt = RightSibling( T->rchild, e ) ) ) //找不到 return NULL; return bt; } return NULL; } Status InserChild( BiTree T, BiTree p, int LR, BiTree c) //初始条件：二叉树T存在，p指向T中某个结点，LR为0或1，非空二叉树c与T不相交且右子树为空。 //操作结果：根据LR为0或1，插入c为T中p所指结点的左或右子树。 // p所指结点的原有左或右子树则成为c的右子树。 { if( T ) if( p ) { if ( !LR ) { c->rchild = p->lchild; p->lchild = c; } else { c->rchild = p->rchild; p->rchild = c; } return OK; } return ERROR; } /* Status DeleteChild( BiTree T, BiTree p, int LR ) //初始条件：二叉树T存在，p指向T中某个结点，LR为0或1。 //操作结果：根据LR为0或1，删除T中p所指结点的左或右子树。 { if( T ) if ( p ) { if ( !LR ) { DestroyBiTree ( p->lchild ); p->lchild = NULL; } else { DestroyBiTree ( p->rchild ); p->rchild = NULL; } return OK; } return ERROR; } */ Status Visit( TElemType e ) //输出e { printf("%c ", e ); return OK; } BiTree Find