c语言 二叉树应用:创建、递归非递归遍历、计算结点、分支、交换子树

#include "stdio.h" #include "stdlib.h" #include "Head.h" #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef int TElemType ; typedef int Status ; typedef struct BiTNode { TElemType data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; BiTree T; typedef BiTree SElemType ; typedef BiTree QElemType ; //*****************栈的相关定义*************************** typedef struct { SElemType *base; SElemType *top; int stacksize; } SqStack; SqStack S; SElemType e,p,q; Status InitStack ( SqStack &S) { S.base = (SElemType*) malloc (STACK_INIT_SIZE * sizeof(SElemType)); if (!S.base) exit(OVERFLOW); S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK; }; //构造一个空栈S Status StackEmpty ( SqStack S) { if (S.top == S.base) return TRUE; return FALSE; }; //判断栈是否为空，若为空则返回TURE，若不为空则返回FALSE Status Push ( SqStack &S, SElemType e) { if (S.top - S.base >= S.stacksize) { S.base = (SElemType*)realloc(S.base,(S.stacksize + STACKINCREMENT) * sizeof (SElemType)); if (!S.base) exit (OVERFLOW); S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; } *S.top++ = e; return OK; }; //插入元素e为新的栈顶元素 Status Pop ( SqStack &S, SElemType &e) { if ( S.top == S.base ) return ERROR; e = * --S.top; return OK; }; //若栈不空，删除S的栈顶元素，并用e返回 Status DestroyStack ( SqStack &S) { S.stacksize = 0; S.top = NULL; free (S.base); return OK; }; //销毁栈S,S不再存在 Status GetTop ( SqStack S, SElemType &e) { if(S.top == S.base) return ERROR; e = *(S.top - 1); return OK; }; //若栈不为空，用e返回S的栈顶元素 //*********************队列的相关定义********************** #define MAXQSIZE 100 typedef struct { QElemType *base; int front; int rear; }SqQueue; SqQueue Q; int i,f; //QElemType e; Status InitQueue ( SqQueue &Q) { Q.base = ( QElemType *) malloc ( MAXQSIZE *sizeof ( QElemType)); if ( !Q.base) exit (OVERFLOW); Q.front = Q.rear = 0; return OK; }; //构造一个空队列 Status QueueLength ( SqQueue Q) { return ( Q.rear - Q.front + MAXQSIZE) % MAXQSIZE; }; //返回队列的长度 Status EnQueue ( SqQueue &Q, QElemType e) { if( ( Q.rear + 1) % MAXQSIZE == Q.front) return ERROR; Q.base[Q.rear] = e; Q.rear = ( Q.rear + 1) % MAXQSIZE; return OK; }; //插入元素e到队列的队尾 Status DeQueue ( SqQueue &Q, QElemType &e) { if( Q.front == Q.rear) return ERROR; e = Q.base[Q.front]; Q.front = ( Q.front + 1) % MAXQSIZE; return OK; }; //队列不空时删除队头元素，用e返回，并返回OK，若不为空，返回ERROR Status DestroyQueue ( SqQueue &Q ) { Q.front = Q.rear = 0; free ( Q.base); return OK; }; //销毁队列 Status ClearQueue (SqQueue &Q) { Q.rear = Q.front = 0; return OK; }; //清空队列 Status QueueEmpty ( SqQueue Q) { if ( Q.front == Q.rear ) return TRUE; return FALSE; }; //判断队列是否为空，若为空，返回TRUE，若不为空，返回FALSE //*********************二叉树的函数********************** Status CreateBiTree ( BiTree &T) { char ch; scanf("%c",&ch); if (ch == '#') T = NULL; else { if(!(T = (BiTNode *)malloc(sizeof(BiTNode)))) exit(OVERFLOW); T -> data = ch; CreateBiTree(T -> lchild); CreateBiTree(T -> rchild); } return OK; }; //用先序创建二叉树 Status FPreOrderTraverse( BiTree T) { int l = 0; if(T) { printf("%c ", T -> data); l = 1; } if(T) { if(l) if (FPreOrderTraverse(T -> lchild)) if(FPreOrderTraverse(T -> rchild)) return OK; return ERROR; } else return OK; }; //先序遍历递归算法 Status FInOrderTraverse( BiTree T) { if(T) { if (FInOrderTraverse(T -> lchild)) if(T) { printf("%c ", T -> data); } if(FInOrderTraverse(T -> rchild)) return OK; return ERROR; } else return OK; }; //中序遍历递归算法 Status FPostOrderTraverse( BiTree T) { if(T) { if (FPostOrderTraverse(T -> lchild)) if(FPostOrderTraverse(T -> rchild)) if(T) { printf("%c ", T -> data); } return OK; } else return OK; }; //后序遍历递归算法 Status PreOrderTraverse(BiTree T) { InitStack(S); p = T; while (p||!StackEmpty(S)) { if(p) { printf("%c ",p -> data); Push (S,p); p = p -> lchild; } else{ Pop(S,p); p = p -> rchild; } } DestroyStack ( S); return OK; }; //先序遍历非递归函数 Status InOrderTraverse(BiTree T) { InitStack(S); p = T; while (p||!StackEmpty(S)) { if(p) {Push (S,p); p = p -> lchild;} else{ Pop(S,p); printf("%c ",p -> data); p = p -> rchild; } } DestroyStack ( S); return OK; }; //中序遍历非递归函数 Status PostOrderTraverse(BiTree T) { InitStack(S); p = T; q = T; while (p||!StackEmpty(S)) { if(p) { Push (S,p); q = p; p = p -> lchild; if(p) if(p -> rchild == NULL || q == p -> rchild) printf("%c ",p -> data); } else{ Pop(S,p); if(p -> rchild == NULL || q == p -> rchild) printf("%c ",p -> data); q = p; p = p -> rchild; } } DestroyStack ( S); return OK; }; //后序遍历非递归函数 Status TInOrderTraverse(BiTree T) { InitStack( S); Push ( S, T); while (!StackEmpty(S)) { while (GetTop(S, p) && p ) Push(S, p -> lchild); Pop(S,p); if( !StackEmpty(S)) { Pop(S,p); printf("%c ", p -> data); Push(S, p -> rchild); } } DestroyStack ( S); return OK; }; //中序遍历非递归函数2 Status LevelOrderTraverse(BiTree T) { //BiTree p; InitQueue (Q); if (T != NULL) { EnQueue(Q, T); while ( !QueueEmpty(Q)) { DeQueue(Q, p); printf("%c ", p -> data); if (p -> lchild != NULL) EnQueue(Q, p -> lchild); if (p -> rchild != NULL) EnQueue(Q, p -> rchild); } } DestroyQueue(Q); return OK; }; //用队列层次遍历二叉树 int count_n1 (BiTree T) { if (T == NULL) return ERROR; else if (T -> lchild ==NULL && T -> rchild == NULL ) return ERROR; else { if (!T -> lchild && T -> rchild) return count_n1 (T -> rchild) + 1; if (T -> lchild && !T -> rchild) return count_n1 (T -> lchild) + 1; if (T -> lchild && T -> rchild) return count_n1 (T -> lchild) + count_n1 (T -> rchild) + 1; } }; //计算单分支结点 int count_n2 (BiTree T) { if (T == NULL) return ERROR; else if (T -> lchild == NULL && T -> rchild ==NULL) return ERROR; else { if(!T -> lchild && T-> rchild) return count_n2 (T -> rchild); if(T -> lchild && !T-> rchild) return count_n2 (T -> lchild); if(T -> lchild && T-> rchild) return count_n2 (T -> lchild) + count_n2 (T -> rchild) + 1; } }; //计算双分支结点 int count (BiTree T) { if (T == NULL) return ERROR; else if (T -> lchild == NULL && T -> rchild ==NULL) return OK; else { if(!T -> lchild && T-> rchild) return count (T -> rchild); if(T -> lchild && !T-> rchild) return count (T -> lchild); if(T -> lchild && T-> rchild) return count (T -> lchild) + count (T -> rchild); if(!T -> lchild && !T-> rchild) return count (T -> lchild) + count (T -> rchild) + 1; } }; //计算叶子数 Status ExchangeLeft_Right(BiTree &T) { BiTree p = T,q; if (p ) { q = p -> lchild; p -> lchild = p -> rchild; p -> rchild = q; ExchangeLeft_Right(p -> lchild); ExchangeLeft_Right(p -> rchild); } return OK; }; //交换左右子树 int Depth (BiTree T ) { int depthval,depthLeft,depthRight; if ( !T ) depthval = 0; else { depthLeft = Depth( T->lchild ); depthRight= Depth( T->rchild ); depthval = 1 + (depthLeft > depthRight ? depthLeft : depthRight); } return depthval; }; // 返回二叉树的深度 void main() { printf("输入相应元素，用先序创建二叉树（无元素处用“#”代替）:\n"); CreateBiTree ( T); printf("\n递归先序遍历二叉树：\n"); FPreOrderTraverse( T); printf("\n递归中序遍历二叉树：\n"); FInOrderTraverse( T); printf("\n递归后序遍历二叉树：\n");