#include#include #define INIT_SIZE 30 typedef struct Bitnode { struct Bitnode *lchild,*rchild; char date; }Bitnode,*Bitree; //先序遍历创建一棵二叉树 void createtree(Bitree *T) { char ch; scanf("%c",&ch); if(ch == '#') *T = NULL; else { *T = (Bitree)malloc(sizeof(Bitnode)); (*T)->date = ch; createtree(&((*T)->lchild)); createtree(&((*T)->rchild)); } } //二叉树的先序遍历 void preorder(Bitree T) { if(T) { printf("%c",T->date); preorder(T->lchild); preorder(T->rchild); } } //二叉树的中序遍历 void inorder(Bitree T) { if(T) { inorder(T->lchild); printf("%c",T->date); inorder(T->rchild); } } //二叉树的后序遍历 void houorder(Bitree T) { if(T) { houorder(T->lchild); houorder(T->rchild); printf("%c",T->date); } } //求二叉树节点的个数 int nodenum(Bitree T) { if(T == NULL) { return 0; } return nodenum(T->lchild)+nodenum(T->rchild)+1; } //求二叉树叶子节点的个数 int leafnum(Bitree T) { if(T == NULL) return 0; if(T->lchild == NULL &&T->rchild == NULL) return 1; return leafnum(T->lchild)+leafnum(T->rchild); } //求二叉树的深度 int depth(Bitree T) { if(T == NULL) return 0; int m = depth(T->lchild); int n = depth(T->rchild); return m > n ? m+1:n+1; } //复制二叉树 void copytree(Bitree T,Bitree *newtree) { if(T == NULL) { *newtree = NULL; return; } *newtree = (Bitree)malloc(sizeof(Bitnode)); (*newtree)->date = T->date; copytree(T->lchild,&((*newtree)->lchild)); copytree(T->rchild,&((*newtree)->rchild)); } //二叉树的先序遍历非递归 //栈的结构 typedef struct { Bitree *top;//栈的里面存放的是根节点的指针，类比int *top; Bitree *base; int stacksize; }Sqstack; //栈的初始化 void Initstack(Sqstack *s) { s->base = (Bitree *)malloc(sizeof(Bitree)*INIT_SIZE); s->top = s->base; s->stacksize = INIT_SIZE; } //入栈 void push(Sqstack *s,Bitree p) { if(s->top - s->base == s->stacksize) { s->base = (Bitree *)realloc(s->base,sizeof(Bitree)*(s->stacksize + INIT_SIZE)); s->top = s->base + s->stacksize ; s->stacksize +=INIT_SIZE; } *(s->top++) = p; } //出栈 void pop(Sqstack *s,Bitree *q) { if(s->top == s->base) return; *q = *(--s->top); } //判断栈是否为空 int emptystack(Sqstack s) { if(s.base == s.top) return 1; return 0; } //非递归先序遍历 void prefeidigui(Bitree T) { Sqstack s; Initstack(&s); Bitree p = T; while(p||!emptystack(s)) { if(p) { printf("%c",p->date); push(&s,p); p = p->lchild; } else { pop(&s,&p); p = p->rchild;//弹出栈的那个元素的右孩子 } } } //非递归中序遍历 void infeidigui(Bitree T) { Sqstack s; Initstack(&s); Bitree p = T; while(p||!emptystack(s)) { if(p) { push(&s,p); p = p->lchild; } else { pop(&s,&p); printf("%c",p->date); p = p->rchild; } } } //非递归后序遍历 void houfeidigui(Bitree T) { Sqstack s1,s2; Initstack(&s1); Initstack(&s2); Bitree p = T; while(p||!emptystack(s1)) { if(p) { push(&s1,p); push(&s2,p); p = p->rchild;//右孩子要放在栈的中间，根节点在最下面 } else { pop(&s1,&p); p = p->lchild; } } while(!emptystack(s2)) { pop(&s2,&p); printf("%c",p->date); } } //二叉树的层序遍历 //队列的结构 typedef struct { int rear; int front; Bitree *base; }Queue; //队列的初始化 void Initqueue(Queue *q) { q->base = (Bitree *)malloc(sizeof(Bitree)*INIT_SIZE); q->front = q->rear = 0; } //入队 void pushqueue(Queue *q,Bitree p) { if((q->rear+1)%INIT_SIZE == q->front) return; q->base[q->rear] = p; q->rear = (q->rear + 1)%INIT_SIZE; } //出队 void popqueue(Queue *q,Bitree *p) { if(q->rear == q->front) return ; *p = q->base[q->front]; q->front = (q->front+1)%INIT_SIZE; } //判断队列是否为空 int emptyqueue(Queue q) { if(q.rear == q.front) return 1; return 0; } void cengxu(Bitree T) { Queue q; Initqueue(&q); Bitree p = T; pushqueue(&q,p); while(!emptyqueue(q)) { popqueue(&q,&p); printf("%c",p->date); if(p->lchild) { pushqueue(&q,p->lchild); } if(p->rchild) { pushqueue(&q,p->rchild); } } } int main() { Bitree T; printf("请输入二叉树的先序遍历"); createtree(&T); printf("该二叉树的先序遍历序列如下"); preorder(T); printf("n"); printf("该二叉树的中序遍历序列如下"); inorder(T); printf("n"); printf("该二叉树的后续遍历序列如下"); houorder(T); printf("n"); printf("该二叉树有%d个节点n",nodenum(T)); printf("该二叉树有%d个叶子节点n",leafnum(T)); printf("该二叉树的深度为%dn",depth(T)); printf("该二叉树的非递归遍历，先，中，后序遍历如下n"); prefeidigui(T) ; printf("n"); infeidigui(T); printf("n"); houfeidigui(T); printf("n"); printf("该二叉树的层序遍历序列如下n"); cengxu(T) ; Bitree newtree; copytree(T,&newtree); printf("n复制的二叉树的中序非递归序列为n"); infeidigui(newtree); return 0; }
