二叉树实验报告 C++ 引用实现

#include <cstdlib> #include <cstdio> #define MAXL 100 typedef int Elemtype ; typedef struct { Elemtype e; } Elem; typedef struct BITree { Elem data; struct BITree * lchild,*rchild; } BITnode,*BTree; void Createtree(BTree &T) //创建二叉树 { Elemtype a; scanf("%d",&a); if (a == -1) { (T) = NULL; } else { (T) = (BTree)malloc(sizeof(BITnode)); if(!T) { exit(1); } (T)->data.e = a; Createtree((T)->lchild); Createtree((T)->rchild); } return ; } //前序遍历 void PreTravel(BTree T) { if(T) { printf(" %d",T->data.e); PreTravel(T->lchild); PreTravel(T->rchild); } } //中序遍历 void MidTravel(BTree T) { if(T) { MidTravel(T->lchild); printf(" %d",T->data.e); MidTravel(T->rchild); } } //后序遍历 void PostTravel(BTree T) { if(T) { PostTravel(T->lchild); PostTravel(T->rchild); printf(" %d",T->data.e); } } //递归计算叶子数 int Count_leaf(BTree T) { if (T == NULL) { return 0; } else if (T->lchild == NULL && T->rchild == NULL) { return 1; } else { return Count_leaf(T->lchild) + Count_leaf(T->rchild); } } ///非递归计算叶子结点个数 ///用栈存放节点 Not_Leaf_Count计算叶子结点个数 typedef struct { int top; BTree MAXSIZE[MAXL]; } *Stack, Le_Node; int Not_Count_Leaf(BTree T) { int Not_Leaf_Count = 0; Stack s; s = (Stack )malloc(sizeof(Le_Node)); s ->top =0; while (T != NULL || s->top != 0) { if (T != NULL) { s->MAXSIZE[s->top] = T; s->top ++; T = T->lchild; } else { s->top --; T = s->MAXSIZE[s->top]; if (T->lchild == NULL && T->rchild == NULL) { Not_Leaf_Count++; } T = T->rchild; } } return Not_Leaf_Count; } //计算二叉树的高度 int Height_Bitree(BTree T) { int h1,h2; if (T != NULL) { h1 = Height_Bitree(T->lchild); h2 = Height_Bitree(T->rchild); if (h1 > h2) { return h1+1; } else { return h2+1; } } else return 0; } //非递归计算二叉树高度 int Not_Height_Bitree(BTree T) { BTree Que[MAXL]; int hp = 0,dp = 0,rear = 0,tp = 1,lc = 1; BTree p; if (T != NULL) //根节点入队 { Que[rear++] = T; } while (rear != 0) { p = Que[--rear];//队头元素出队 hp ++; //为已访问的节点数 if (p->lchild != NULL) { Que[rear++] = p->lchild; tp ++; //记录历史入队的节点数 } if (p->rchild != NULL) { Que[rear++] = p->rchild; tp ++; } if(hp == lc) //当hp = lc时，表明本层节点均已访问完 { dp ++; lc = tp; } } return dp; } //按层次遍历 void Level_Travel(BTree T) { BTree Que[MAXL]; int front = 0,rear = 0; BTree p; if (T != NULL) //根节点入队 { Que[rear] = T; rear = (rear+1)%MAXL; } while (front != rear) { p = Que[front];//队头元素出队 front = (front +1)% MAXL; printf(" %d",p->data.e); if (p->lchild != NULL) { Que[rear] = p->lchild; rear = (rear + 1)%MAXL; } if (p->rchild != NULL) { Que[rear] = p->rchild; rear = (rear+1)%MAXL; } } return ; } //非递归先序遍历 void NPreTravel(BTree T) { BTree stack[MAXL]; BTree p; int top ; if (T != NULL) { top = 0; p = T; while (p != NULL || top > 0) { while (p != NULL) { printf(" %d",p->data.e); stack[top] = p; top ++; p = p->lchild; } if (top > 0) { top--; p = stack[top]; p = p->rchild; } } } } //非递归中序遍历 void NMidTravel(BTree T) { BTree stack[MAXL]; BTree p; int top; if (T != NULL) { top = 0; p = T; while (p != NULL || top > 0) { while (p != NULL) { stack[top] = p; top ++; p = p->lchild; } if (top > 0) { top--; p = stack[top]; printf(" %d",p->data.e); p = p->rchild; } } } } //非递归后续遍历 typedef struct { BTree ptr; int tag; } stacknode; void NPostTravel(BTree T) { stacknode s[MAXL]; stacknode x; BTree p = T; int top; if (T != NULL) { top = 0; p = T; do { while (p != NULL) //遍历左子树 { s[top].ptr = p; s[top].tag = 1; //标记为左子树 top ++; p = p->lchild; } while (top > 0 && s[top-1].tag == 2) { x = s[--top]; p = x.ptr; printf(" %d",p->data.e); //tag 为2 表示右子数访问完毕，故访问根节点 } if (top > 0) { s[top-1].tag = 2; //遍历右子树 p = s[top-1].ptr->rchild; } } while (top > 0); } } void menu() { printf("----------------------------------------------\n\n"); printf("0:退出\n"); printf("1:创建二叉树\n"); printf("2:递归前序遍历\n3:非递归前序遍历\n"); printf("4:递归中序遍历\n5:非递归中序遍历\n"); printf("6:递归后续遍历\n7:非递归后续遍历\n"); printf("8:递归计算叶子数\n9:非递归计算叶子数\n"); printf("10:递归计算高度 \n11:非递归计算高度\n"); printf("12:按层次遍历\n"); printf("-----------------------------------------------\n"); return ; } int main() { BTree T = NULL; int select ; menu(); do { printf("输入您的选择："); scanf("%d",&select); switch (select) { case 0: { printf("退出\n"); break ; } case 1: { printf("创建二叉树\n"); printf("输入数据，以-1结束\n"); Createtree(T); break; } case 2: { printf("递归前序遍历\n"); PreTravel(T); break; } case 3: { printf("非递归前序遍历\n"); NPreTravel(T); break; } case 4: { printf("递归中序遍历\n"); MidTravel(T); break; } case 5: { printf("非递归中序遍历\n"); NMidTravel(T); break; } case 6: { printf("递归后序遍历\n"); PostTravel(T); break; } case 7: { printf("非递归后序遍历\n"); NPostTravel(T); break ; } case 8: { printf("递归计算叶子数为：%d\n",Count_leaf(T)); break ; } case 9: { printf("非递归计算叶子数为：%d\n",Not_Count_Leaf(T)); break; } case 10: { printf("递归计算高度\n"); printf("高度为：%d\n",Height_Bitree(T)); break;