#include<bits/stdc++.h> using namespace std; typedef char BElemType; typedef struct Node { BElemType data; struct Node *LChild; struct Node *RChild; } BinNode,*BinTree; typedef BinTree SElemType; typedef struct LNode ///栈 { SElemType data; struct LNode *next; } LNode,*LinkList; ///队列 typedef BinTree QElemType; typedef struct QNode { QElemType data; struct QNode *next; } Qnode,*Queueptr; typedef struct { Queueptr Front; Queueptr Rear; } LinkQueue; ///队列 void InitQueue(LinkQueue &Q) { Q.Front=Q.Rear=(Queueptr)malloc(sizeof(QNode)); if(!Q.Front) return ; Q.Front->next=NULL; } int isEmptyQueue(LinkQueue Q) { if(Q.Front==Q.Rear) return 1; return 0; } void EnQueue(LinkQueue &Q,QElemType e) { Queueptr s=(Queueptr)malloc(sizeof(QNode)); s->data=e; s->next=NULL; Q.Rear->next=s; Q.Rear=s; } void DeQueue(LinkQueue &Q,QElemType &e) { Queueptr s=(Queueptr)malloc(sizeof(QNode)); if(Q.Front==Q.Rear) return ; s=Q.Front->next; Q.Front->next=s->next; e=s->data; if(Q.Rear==s) Q.Rear=Q.Front; free(s); } ///栈 void INitStack(LinkList &L) { L=NULL; } bool isEmptyStack(LinkList L) { if(L==NULL) return 1; return 0; } void PushStack(LinkList &L,SElemType e) ///先进后出 { LNode* s; s=(LinkList)malloc(sizeof(LNode)); s->data=e; s->next=L; L=s; } void PopStack(LinkList &L,SElemType &e) { LNode* s; if(L==NULL) return ; e=L->data; s=L; L=L->next; free(s); } ///二叉树 BinTree PreCreateTree(BinTree bt) ///先序建树 { char ch; scanf("%c",&ch); if(ch=='#') return NULL;///为空 else { bt=(BinNode*)malloc(sizeof(BinNode)); bt->data=ch;///根节点 bt->LChild=PreCreateTree(bt->LChild);///创建左子树 bt->RChild=PreCreateTree(bt->RChild);///创建右子树 return bt; } } BinTree InCreateTree(BinTree bt) ///中序序列建树 { char ch; scanf("%c",&ch); if(ch=='#') return NULL;///为空 else { bt=(BinNode*)malloc(sizeof(BinNode)); bt->LChild=InCreateTree(bt->LChild);///创建左子树 bt->data=ch;///根节点 bt->RChild=InCreateTree(bt->RChild);///创建右子树 return bt; } } BinTree PostCreateTree(BinTree bt) ///后序序列建树 { char ch; scanf("%c",&ch); if(ch=='#') return NULL;///为空 else { bt=(BinNode*)malloc(sizeof(BinNode)); bt->LChild=PostCreateTree(bt->LChild);///创建左子树 bt->RChild=PostCreateTree(bt->RChild);///创建右子树 bt->data=ch;///根节点 return bt; } } void PreOrder(BinTree bt) ///先序递归遍历 { if(bt) { printf("%c",bt->data);///输出根节点 PreOrder(bt->LChild);///遍历左子树 PreOrder(bt->RChild);///遍历右子树 } } void InOrder(BinTree bt) ///中序递归遍历 { if(bt) { InOrder(bt->LChild);///遍历左子树 printf("%c",bt->data);///输出根节点 InOrder(bt->RChild);///遍历右子树 } } void PostOrder(BinTree bt) ///后序递归遍历 { if(bt) { PostOrder(bt->LChild);///遍历左子树 PostOrder(bt->RChild);///遍历右子树 printf("%c",bt->data);///输出根节点 } } int CountCnt(BinTree bt) ///计算节点个数 { if(bt==NULL) return 0; else return CountCnt(bt->LChild)+CountCnt(bt->RChild)+1; } int LeafCnt(BinTree bt) ///计算叶子节点个数 { if(bt==NULL) return 0; else if(bt->LChild==NULL&&bt->RChild==NULL) return 1; else return LeafCnt(bt->LChild)+LeafCnt(bt->RChild); } int BintreeDep(BinTree bt) ///计算二叉树的深度 { int depl,depr; if(bt==NULL) return 0; else { return max(BintreeDep(bt->LChild),BintreeDep(bt->RChild))+1; } } int LevelOrderTraverse(BinTree bt) ///层次遍历 { LinkQueue Q; int sum=0; BinTree p; if(bt) { InitQueue(Q); EnQueue(Q,bt); while(!isEmptyQueue(Q)) { DeQueue(Q,p); printf("%c",p->data); if(p->LChild) EnQueue(Q,p->LChild); if(p->RChild) EnQueue(Q,p->RChild); } } } bool isCheckCBT(BinTree bt) ///判断以bt为根节点的二叉树是否为完全二叉树 { if(bt==NULL) return 1;///空树一定是完全二叉树 bool flag=0; /*leaf变量用来标记一个状态是否发生 (只要当前节点的左孩子和右孩子都为空或者左孩子不为空, 右孩子为空时,这个状态就发生,只要发生了这个状态,以后访问到的节点必须都是叶节点) */ LinkQueue Q; InitQueue(Q); EnQueue(Q,bt); while(!isEmptyQueue(Q)) { BinTree p; DeQueue(Q,p); if(p!=NULL) { if(flag) return 0; EnQueue(Q,p->LChild); EnQueue(Q,p->RChild); } else flag=1; } return 1; } void InOrderTraverse(BinTree bt) ///非递归遍历方法三 中序遍历 { if(bt==NULL) return ; BinTree p=bt; LNode* Q; INitStack(Q); while(!isEmptyStack(Q)||p) { ///一直遍历到左子树的最下边 边遍历边保存根节点到栈里 while(p) { PushStack(Q,p); p=p->LChild; } ///p为空时 说明已经到了左子树的最下边 此时应该出栈 if(!isEmptyStack(Q)) { PopStack(Q,p); printf("%c",p->data); p=p->RChild;///左边和根节点都遍历完了该遍历右子树了 } } } void PreOrderTraverse(BinTree bt) ///非递归遍历方法三 先序遍历 { if(bt==NULL) return ; BinTree p=bt; LNode* Q; INitStack(Q); while(!isEmptyStack(Q)||p) { ///一直遍历到左子树的最下边 边遍历边保存根节点到栈里 while(p) { printf("%c",p->data); PushStack(Q,p); p=p->LChild; } ///p为空时 说明已经到了左子树的最下边 此时应该出栈 if(!isEmptyStack(Q)) { PopStack(Q,p); p=p->RChild;///左边和根节点都遍历完了该遍历右子树了 } } } /** 待补:二叉树的线索化 **/ int main() { BinTree bt; printf("一、先序输入结点元素(#表示空)如:ABD###CE##F##\n"); bt=PreCreateTree(bt); printf("二、先序遍历二叉树:\n"); PreOrder(bt); printf("\n"); printf("三、中序遍历二叉树:\n"); InOrder(bt); printf("\n"); printf("四、后序遍历二叉树:\n"); PostOrder(bt); printf("\n"); printf("五、层次遍历二叉树\n"); LevelOrderTraverse(bt); printf("\n"); printf("六、二叉树结点数: %d\n",CountCnt(bt)); printf("七、叶子节点的个数:%d \n",LeafCnt(bt)); printf("八、二叉树的深度:%d \n",BintreeDep(bt)); printf("九:判断一个二叉树是否为完全二叉树\n"); if(isCheckCBT(bt)) puts("is a CBT"); else puts("is not a CBT"); printf("十:求二叉树的中序序列(非递归)\n"); InOrderTraverse(bt); puts(""); printf("十一:求二叉树的先序序列(非递归)\n"); PreOrderTraverse(bt); puts(""); return 0; }