#include#include #include #define N 50using namespace std;typedef struct tree{ char ch; struct tree *lchild; struct tree *rchild;}BitTree; //键盘输入 BitTree *CreateTree(){ BitTree *bt; char str; scanf("%c", &str); if(str=='#') return NULL; else{ bt=(BitTree *)malloc(sizeof(BitTree)); bt->ch=str; bt->lchild=CreateTree(); bt->rchild=CreateTree(); return bt; }}//数组输入BitTree *CreateTree(int A[], int i, int n){ BitTree *bt; if(i>n) return NULL; else{ bt=(BitTree *)malloc(sizeof(BitTree)); if(A[i]=='#') return NULL; bt->ch=A[i]; bt->lchild=CreateTree(A, 2*i, n); bt->rchild=CreateTree(A, 2*i+1, n); return bt; }} //非递归先序 void PreOrder(BitTree *bt){ BitTree *STACK[N], *p = bt; int top = -1; while(top != -1 || p!=NULL){ while(p != NULL){ STACK[++top] = p; printf("%c ",p->ch);//和中序的不同之处 p = p->lchild; } p = STACK[top--]; p = p->rchild; }}//非递归中序 void InOrder(BitTree *bt){ BitTree *STACK[N], *p = bt; int top = -1; while(top != -1 || p!=NULL){ while(p != NULL){ STACK[++top] = p; p = p->lchild; } p = STACK[top--]; printf("%c ",p->ch);//和前序的不同之处 p = p->rchild; }}//非递归后序 void PostOrder(BitTree *bt){ BitTree *STACK1[N], *p = bt; int STACK2[N], top=-1, flag; while(top != -1 || p!=NULL){ while(p != NULL){ STACK1[++top] = p; STACK2[top] = 0; p = p->lchild; } p = STACK1[top]; flag = STACK2[top--]; if(flag == 1){ printf("%c ", p->ch); p = NULL; } else{ STACK1[++top] = p; STACK2[top] = 1; p = p->rchild; } }} //递归求二叉树深度int Depth_1(BitTree *bt){ int ldepth, rdepth; if(bt==NULL) return 0; else{ ldepth=Depth_1(bt->lchild); rdepth=Depth_1(bt->rchild); if(ldepth>rdepth) return ldepth+1; else return rdepth+1; }} //非递归求二叉树深度int Depth_2(BitTree *bt){ BitTree *STACK1[N], *p = bt; int STACK2[N]; int cur , max = 0, top = -1; if(bt != NULL){ cur = 1; while(top != -1 || p != NULL){ while(p != NULL){ STACK1[++top] = p; STACK2[top] = cur++; p = p->lchild; } p = STACK1[top]; cur = STACK2[top--]; if(p->lchild==NULL && p->rchild==NULL) if(cur > max) max = cur; p = p->rchild; cur++; } } return max;} int main(){ int A[N]={ '#','A','B','C','D','E','#','F','G','H'}; BitTree *bt=CreateTree(A,1,9); printf("前序遍历非递归实现：\n"); PreOrder(bt); printf("\n"); printf("中序遍历非递归实现：\n"); InOrder(bt); printf("\n"); printf("后序遍历非递归实现：\n"); PostOrder(bt); printf("\n"); printf("Depth_Recursive:%d",Depth_1(bt)); printf("\n"); printf("Depth_nonRecursive:%d",Depth_2(bt)); return 0; }
输入样例： A / \ B C / \ \ D E F / \ G H
