#include<stdio.h>
#include<stdlib.h>#define OK 1#define ERROR 0#define OVERFLOW 0#define INCREASESIZE 10#define INITSTACKSIZE 100#define STACK_INIT_SIZE 100typedef int Status;
typedef char ElemType;typedef struct treenode{ ElemType data; struct treenode *lchild,*rchild;}treenode,*treelink;typedef struct {
treelink* base; treelink* top; int stacksize; } SqStack;//堆栈结构体Status createtree(treelink &T);
Status visit(ElemType e);Status Preorder(treelink T);//递归先序遍历函数 Status Midorder(treelink T);//递归中序遍历函数Status Lastorder(treelink T);//递归后序遍历函数,注意函数指针的使用int getdepth(treelink T);Status singlenode(treelink T,int &singlenum);Status doublenode(treelink T,int &doublenum);Status leafnode(treelink T,int &leafnum);Status change(treelink &T);Status Lastorder2(treelink T);//递归后序遍历函数,注意函数指针的使用void NPostOrder(treelink T);int Count_Sigle(treelink T) ;Status search_x(treelink &T,ElemType x);
void CreateBiTree(treelink &root);void insert(treelink &T,ElemType x);Status InitStack (SqStack &s);//建立堆栈结构Status GetTop(SqStack s, treelink &e);
//得到堆栈头Status Pop (SqStack &s, treelink &e);
//出堆栈Status Push (SqStack &s, treelink e);
//入堆栈Status StackEmpty(SqStack s);
//判断堆栈是否为空
#ifndef CCCCCCCCCCCC_C
#define CCCCCCCCCCCC_CStatus InitStack (SqStack &s);
//建立堆栈结构Status GetTop(SqStack s, BiTree &e);
//得到堆栈头Status Pop (SqStack &s, BiTree &e);
//出堆栈Status Push (SqStack &s, BiTree e);
//入堆栈Status StackEmpty(SqStack s);
//判断堆栈是否为空#endif
#include "head.h"
Status InitStack (SqStack &s){ s.base=(treelink *)malloc(STACK_INIT_SIZE * sizeof (treelink)); if (!s.base) return ERROR;//存储分配失败 s.top = s.base; s.stacksize = STACK_INIT_SIZE; return OK;}Status GetTop(SqStack s, treelink &e)
{ //if (s.top == s.base)return ERROR; e = *(s.top-1); return OK;} /* GetTop */Status Pop (SqStack &s, treelink &e) {
// 若栈不空，则删除S的栈顶元素， // 用e返回其值，并返回OK； // 否则返回ERROR // if (s.top == s.base) return ERROR; --s.top; e = *(s.top); //- -S.top;e=*S.top; return OK;}Status Push (SqStack &s, treelink e) {
/* if (s.top - s.base >= s.stacksize) {//栈满，追加存储空间 s.base = (BiTree *) realloc ( s.base, (s.stacksize + STACKINCREMENT) * sizeof (BiTNode)); if (!s.base) return (OVERFLOW); //存储分配失败 s.top = s.base + s.stacksize; s.stacksize += STACKINCREMENT; } */ *s.top = e; //*S.top=e;S.top++; s.top++; return OK;}Status StackEmpty(SqStack s)
{ if (s.base == s.top) return OK; return ERROR;}
#include "head.h"
/******************************/
/*利用先序递归的思想建立一个二叉树*//******************************/Status createtree(treelink &T)
{ char c; c=getchar(); if(c=='#') T=NULL; else { if(!(T=(treelink)malloc(sizeof(treenode)))) exit(OVERFLOW); T->data=c; createtree(T->lchild); createtree(T->rchild); } return OK;}/******************************/
/*二叉排序树的创建算法*//******************************/void CreateBiTree(treelink &root){ ElemType x; root=NULL; getchar(); scanf("%c",&x); while (x!='#'){ insert(root,x); scanf("%c",&x); }//while}//CreateBiTree/******************************/
/*二叉排序树的插入算法*//******************************/void insert(treelink &T,ElemType x){
if (T==NULL){ T=(treelink)malloc(sizeof(treenode)); T->data=x; T->lchild=T->rchild=NULL; } else{ if (x<T->data) insert(T->lchild,x); if (x>T->data) insert(T->rchild,x); }}//insert/******************************/
/*查询是否有值为x的结点*//******************************/ Status search_x(treelink &T,ElemType x) { if(!T) return 0; else { if(T->data ==x) return OK; else { if(x<T->data ) search_x(T->lchild ,x); else search_x(T->rchild ,x); } }}
/******************************//*输出节点函数*//******************************/Status visit(ElemType e){ printf("%c ",e); return OK;}/******************************//*递归实现的先序遍历*//******************************/Status Preorder(treelink T)//递归先序遍历函数{ if(T) { visit(T->data); Preorder(T->lchild); Preorder(T->rchild); }return OK;
}/******************************//*递归实现的中序遍历*//******************************/ Status Midorder(treelink T)//递归中序遍历函数{ if(T) { Midorder(T->lchild); visit(T->data); Midorder(T->rchild); }return OK;
}/******************************//*递归实现的后序遍历*//******************************/Status Lastorder(treelink T)//递归后序遍历函数,注意函数指针的使用{ if(T) { Lastorder(T->lchild); Lastorder(T->rchild); visit(T->data); }return OK;
}/******************************/
/*求树的深度(后序递归思想)*//******************************/int getdepth(treelink T){ int lh,rh,h; if(T==NULL) h=0; else { lh=getdepth(T->lchild); rh=getdepth(T->rchild); if(lh>=rh) h=lh+1; else h=rh+1; } return h;}/******************************//*输出树的单分支节点(先序递归思想)*//******************************/Status singlenode(treelink T,int &singlenum){ if((T->lchild!=NULL&&T->rchild==NULL)||(T->lchild==NULL&&T->rchild!=NULL)) { visit(T->data); singlenum++; } if(T->lchild!=NULL) singlenode(T->lchild,singlenum); if(T->rchild!=NULL) singlenode(T->rchild,singlenum); return OK;}int Count_Sigle(treelink T) {
//统计单分支结点的数目 int num; if (T==NULL) return 0; //空树else{
if (!T->lchild || !T->rchild) //只有左单分支 {num=1; num+=Count_Sigle(T->lchild); num+=Count_Sigle(T->rchild); } else num=Count_Sigle(T->lchild)+Count_Sigle(T->rchild);//双分支结点 return num; } }/******************************//*输出树的双分支节点(先序递归思想)*//******************************/Status doublenode(treelink T,int &doublenum){ if(T->lchild!=NULL&&T->rchild!=NULL) { visit(T->data); doublenum++; } if(T->lchild!=NULL) doublenode(T->lchild,doublenum); if(T->rchild!=NULL) doublenode(T->rchild,doublenum); return OK;}/******************************//*统计二叉树的叶子结点数(先序递归思想)*//******************************/Status leafnode(treelink T,int &leafnum){ if((T->lchild==NULL&&T->rchild==NULL)) { visit(T->data); leafnum++; } if(T->lchild!=NULL) leafnode(T->lchild,leafnum); if(T->rchild!=NULL) leafnode(T->rchild,leafnum); return OK;}/******************************//*交换左右子树(后序递归)*//******************************/Status change(treelink &T){ treelink temp; if(T) { change(T->lchild); change(T->rchild); temp=T->lchild;T->lchild=T->rchild;T->rchild=temp; } return OK;}/******************************//*非递归实现的后序遍历*//******************************/Status Lastorder2(treelink T)//递归后序遍历函数,注意函数指针的使用{ SqStack S; InitStack(S); Push(S,T); treelink P=NULL; while(!StackEmpty(S)) { if(T&&T!=P) //T!=P的意思为T是刚刚访问的根节点，证明T无右子树 {Push(S,T);T=T->lchild;} else { Pop(S,T); if(!StackEmpty(S)) if(T->rchild&&T->rchild!=P)//T->rchild!=P意思为右子树不为刚才的根节点 {Push(S,T);T=T->rchild;} else {visit(T->data);P=T;} }}
return OK;}void NPostOrder(treelink T)
{//后序遍历非递归算法,s为存储二叉树结点指针栈 SqStack S; InitStack(S); treelink p = T; treelink pnow = T; //pnow当前访问的结点 while (p||!StackEmpty(S)) { while (p != NULL) { Push(S,p); p = p->lchild; } if (!StackEmpty(S)) { treelink temp; GetTop(S,temp); temp = temp->rchild; if (temp == NULL || temp == pnow) //temp==pnow的意思即当前结点为刚刚访问的结点，即其右孩子已//经访问过了，则不往右分支走，弹栈操作
{ Pop(S,p); visit(p->data); pnow = p; //每访问一个结点，将指针pnow指向它 p = NULL; //每访问一个结点，将p置为NULL，即P的左分支已经走完，下一次不会//向左分支走 while(p!=NULL)
} else { p = temp; } } }//while}
#include"head.h"
void main(){ int leafnum=0,singlenum=0,doublenum=0; int x;char c; treelink T; printf("What do you want to do?\n"); printf("Press 1 to creat a piece of tree.\n"); printf("Press 2 to traverse in preview.\n"); printf("Press 3 to traverse in order.\n"); printf("Press 4 to traverse in last.\n"); printf("Press 5 to get the length of this tree.\n"); printf("Press 6 to get the node which has only a node.\n"); printf("Press 7 to get the node which has two nodes.\n"); printf("Press 8 to get the node which has no nodes.\n"); printf("Press 9 to change lchild and rchild.\n"); printf("Press 10 to 后序非递归遍历.\n"); printf("Press 11 to search x\n"); printf("Press 12 to 创建二叉排序树 \n");
printf("Press 0 to exit this program.\n\n");
printf("Please choose one:"); scanf("%d",&x); while(x!=0) { switch(x) { case 1: c=getchar(); printf("%c",c); createtree(T); break; case 2: Preorder(T); printf("\n"); break; case 3: Midorder(T); printf("\n"); break; case 4: Lastorder(T); printf("\n"); break; case 5: printf("The depth is %d",getdepth(T)); printf("\n"); break; case 6: //singlenode(T,singlenum); printf("\nThe single number is: %d", Count_Sigle( T)); printf("\n"); break; case 7: doublenode(T,doublenum); printf("\nThe double number is: %d",doublenum); printf("\n"); break; case 8: leafnode(T,leafnum); printf("\nThe leaf number is: %d",leafnum); printf("\n"); break; case 9: change(T); break; case 10: NPostOrder(T); printf("\n"); break; case 11: getchar(); printf("\n input search x:"); scanf("%c",&x); printf("\n%d",search_x(T,x)); break; case 12: CreateBiTree(T); break;}
printf("Please choose one:"); scanf("%d",&x); } printf("\n Thank you for viewing this program.\n");}