1.采用二叉链表结构建立二叉树 2.编程实现二叉树的先序、中序、后序和层序遍历； 3.编程实现非递归中序遍历 4.编程实现：求二叉树的高度和叶子结点个数；
实例操作: 1.创建 2.输入 ：ABC##DE#G##F### 该输入对应的树如图所示
先序 屏幕输出 A B C D E G F 后序 屏幕输出 C G E F D B A错 中序 屏幕输出 C B E G D F A (中序非递归还需看源代码)错 层序 屏幕输出 A B C D E F G 深度 屏幕显示 深度为5 错
#include <iostream> #include <bits/stdc++.h> #define OK 1 #define ERROR 0 #define MAXSIZE 100 typedef int Status; typedef char TElemType; typedef char **HuffmanCode; using namespace std; //链式二叉树的建立 typedef struct BiTNode { TElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; //创建树 Status CreatBiTree(BiTree &T) { TElemType ch; cin>>ch; if(ch=='#') { T=NULL; } else { T = new BiTNode; T->data = ch; CreatBiTree(T->lchild); CreatBiTree(T->rchild); } } //栈 typedef struct{ BiTree *base; BiTree *top; int stacksize; }SqStack; //初始化栈 Status InitStack(SqStack &S) { S.base=new BiTree[MAXSIZE]; if(!S.base) { cout<<"存储分配失败"<<endl; return ERROR; } S.top = S.base; S.stacksize = MAXSIZE; return OK; } //入栈 Status Push(SqStack &S, BiTree e) { if(S.top-S.base==S.stacksize) { cout<<"栈满"<<endl; return ERROR; } *S.top++=e; //*S.top=e; //S.top++; return OK; } //出栈 BiTree Pop(SqStack &S) { BiTree e; if(S.top==S.base) { cout<<"栈空"<<endl; return ERROR; } e=*--S.top; //--S.top; //e=*S.top; //cout<<"出栈元素为："<<e<<endl; return e; } //栈空 Status StackEmpty(SqStack S) { if(S.top==S.base) { return OK; } else return ERROR; } //队列 typedef struct{ BiTree *base; int Front; int rear; }SqQueue; //创建队列 Status InitQueue(SqQueue &Q) { Q.base=new BiTree[MAXSIZE]; if(!Q.base) { cout<<"存储分配失败"<<endl; return ERROR; } Q.Front=Q.rear=0; return OK; } //入队 Status EnQueue(SqQueue &Q,BiTree e) { if((Q.rear+1)%MAXSIZE==Q.Front) { cout<<"队满"<<endl; return ERROR; } Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%MAXSIZE; return OK; } //出队 BiTree DeQueue(SqQueue &Q) { BiTree e; if(Q.Front==Q.rear) { cout<<"队空"<<endl; return ERROR; } e=Q.base[Q.Front]; Q.Front=(Q.Front+1)%MAXSIZE; //cout<<"出队元素为："<<e<<endl; return e; } //先序遍历 Status PreOrderTraverse(BiTree T) { if(T) { cout<<T->data<<" "; PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); return OK; } else return ERROR; } //中序遍历 Status InOrderTraverse(BiTree T) { if(T) { InOrderTraverse(T->lchild); cout<<T->data<<" "; InOrderTraverse(T->rchild); return OK; } else return ERROR; } //后序遍历 Status PostOrderTraverse(BiTree T) { if(T) { PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); cout<<T->data<<" "; return OK; } else return ERROR; } //层序遍历 Status LeveOrderTraverse(BiTree T) { if(!T) { return ERROR; } SqQueue Q; InitQueue(Q); EnQueue(Q,T); BiTree pre; while(Q.Front!=Q.rear) { pre = DeQueue(Q); cout<<pre->data<<" "; if(pre->lchild!=NULL) { EnQueue(Q,pre->lchild); } if(pre->rchild) { EnQueue(Q,pre->rchild); } } return OK; } //非递归中序遍历 Status InOrderTraverse2(BiTree T) { SqStack S; InitStack(S); BiTree p = T; BiTree q; while(p||!StackEmpty(S)) { if(p) { Push(S,p); p=p->lchild; } else { q = Pop(S); cout<<q->data<<" "; p=q->rchild; } } return OK; } //求二叉树的高度 Status Deepth(BiTree T) { int l=0,r=0; if(T==NULL) { return 0; } else { l=Deepth(T->lchild); r=Deepth(T->rchild); if(l>=r) { return l+1; } else { return r+1; } } } //叶子节点数 Status LeafCount(BiTree T) { if(T==NULL) { return 0; } else if(T->lchild==NULL&&T->rchild==NULL) { return 1; } else { return LeafCount(T->lchild)+LeafCount(T->rchild); } } typedef struct { int weight; int parent,lchild,rchild; }HTNode,*HuffmanTree; void Select(HuffmanTree &HT, int end, int &s1, int &s2) { int min1=66666,min2=66666; for(int i=1;i<=end;i++) { for(HT[i].parent==0&&HT[i].weight<min1) { min1 = HT[i].weight; s1 = i; } } for(int i=1;i<=end;i++) { for(HT[i].parent==0&&HT[i].weight<min2&&s1!=i) { min2 = HT[i].weight; s2 = i; } } } void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC, int n) { int i,s1,s2; HuffmanTree p; if(n<=1) return; int m = 2*n-1; HT = new HTNode[m+1]; for(i=1;1<=m;i++) { HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0; } for(i=1;i<=n;++i) { cout<<"输入权值:"; cin>>HT[i].weight; } for(i=n+1;i<=m;i++) { Select(HT,i-1,s1,s2); HT[i].weight = HT[s1].weight+HT[s2].weight; HT[s1].parent = i; HT[s2].parent = i; HT[i].lchild = s1; HT[i].rchild = s2; } } void creatHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n) { int start,c,f; HC=new char*[n+1]; char *cd=new char[n]; cd[n-1]='\0'; for(int i=1; i<=n; i++) { start = n-1; c=i; f=HT[c].parent; while(f!=0) { start--; if(HT[f].lchild==c) { cd[start]='0'; } else { cd[start]='1'; } c=f; f=HT[f].parent; } HC[i] = new char[n-start]; strcpy(HC[i],&cd[start]); } delete cd; } void TransCode(HuffmanTree HT,char a[],char zf[],char &b[],int n) { int q=2*n-1; int k=0; for(i=0; a[i]!='\0'; i++) { if(a[i]=='0') { q=HT[q].lchild; } else if(a[i]=='1') { q=HT[q].rchild; } if(HT[q].lchild==0 && HT[1].rchild==0) { b[k++]=zf[q]; q=2*n-1; } } b[k]='\0'; } int main() { cout << "1----创建二叉树" << endl; cout << "2----先序输出" << endl; cout << "3----后序输出" << endl; cout << "4----中序输出" << endl; cout << "5----中序非递归输出" << endl; cout << "6----层序输出" << endl; cout << "7----深度" << endl; cout << "8----叶子节点个数" << endl; cout << "退出，输入一个负数！" << endl; BiTree T; SqStack S; InitStack(S); SqQueue Q; InitQueue(Q); int i; bool flag=true; BiTree e; while(flag){ cout << "请输入一个操作码："; cin>>i; if(i==1){ cout<<"请输入节点: "; CreatBiTree(T); } else if(i==2){ PreOrderTraverse(T); cout<<endl; } else if(i==3){ PostOrderTraverse(T); cout<<endl; } else if(i==4){ InOrderTraverse(T); cout<<endl; } else if(i==5){ InOrderTraverse2(T); cout<<endl; } else if(i==6){ LeveOrderTraverse(T); cout<<endl; } else if(i==7){ int deep=0; deep = Deepth(T); cout<<"深度为: "<<deep<<endl; } else if(i==8){ int leaf=0; leaf = LeafCount(T); cout<<"叶子节点数为: "<<leaf<<endl; } else flag=false; } return 0; }