C++ 环境codeblocks17 通过
/* 二叉树 使用了自定义的 栈 和 队列 @CGQ 2018/10/29 */ #include <iostream> #include <stdio.h> #include <stdlib.h> #include <stack> using namespace std; #define ElemType char typedef struct BiTNode { ElemType data; struct BiTNode *lchild, *rchild; }BiTNode, *BiTree; #define QElemType BiTree #define SElemType BiTree #define MAXSIZE 1000 #define Status int typedef struct SNode { SElemType *base; SElemType *top; int stacksize; }SqStack; typedef struct QNode { QElemType *base; int front; int rear; }SqQueue; Status InitStack(SqStack &S) {// 初始化顺序栈 S.base = new SElemType[MAXSIZE]; if(!S.base) return -1; S.top = S.base; S.stacksize = MAXSIZE; return 1; } Status Push(SqStack &S, SElemType &e) { if(S.top-S.base == S.stacksize) return -1; *S.top = e; S.top++; return 1; } Status Pop(SqStack &S, SElemType &e) { if(S.top == S.base) return -1; e = *(--S.top); return 1; } Status EmptyStack(SqStack &S) { if(S.top-S.base == 0) return 1; else return 0; } Status InitQueue(SqQueue &Q) {// 初始化顺序队列 Q.base = new QElemType[MAXSIZE]; // 申请空间 if(!Q.base) return -1; // 申请失败 Q.front = Q.rear = 0; return 1; } QElemType QueueOut(SqQueue &Q) { if(Q.front == Q.rear) return NULL; QElemType e = Q.base[Q.front]; Q.front = (Q.front+1)%MAXSIZE; return e; } Status QueueIn(SqQueue &Q, QElemType &e) { if((Q.rear+1)%MAXSIZE == Q.front) return -1; Q.base[Q.rear] = e; Q.rear = (Q.rear+1)%MAXSIZE; return 1; } Status EmptyQueue(SqQueue &Q) { if(Q.rear==Q.front) return 1; else return 0; } //----------------------------------<end 栈和队列> void CreateBiTree(BiTree &T) {// 先序创建二叉树 char ch; cin>>ch; if(ch == '#') T = NULL; else { T = new BiTNode; T->data = ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); } } void PreOrderTraverse(BiTree T) {// 先序递归遍历 if(T) { cout<<T->data; PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); } } void InOrderTraverse(BiTree T) {// 中序递归遍历 if(T) { InOrderTraverse(T->lchild); cout<<T->data; InOrderTraverse(T->rchild); } } void PostOrderTraverse(BiTree T) {// 后序递归遍历 if(T) { PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); cout<<T->data; } } void HierarchicalOrder_TraverseBiTree(BiTree T) {// 层次遍历二叉树 if(T==NULL) return; // 空树 BiTree p; SqQueue Q; InitQueue(Q); QueueIn(Q,T); while(!EmptyQueue(Q)) { p = QueueOut(Q); cout<<p->data; // 访问 if(p->lchild) QueueIn(Q,p->lchild); if(p->rchild) QueueIn(Q,p->rchild); } //<end while> } void InOrderTraverse_noRecursive(BiTree T) {// 非递归中序遍历二叉树 if(T==NULL) return ; SqStack s; BiTree p = T; InitStack(s); while(p||!EmptyStack(s)) { if(p) // p非空 { // 可以在此处统计节点 Push(s,p); p = p->lchild; } else // p为空 { Pop(s,p); cout<<p->data; p = p->rchild; } } //<end while> } /* // 标准stack头文件 void InOrderTraverse_noRecursive(BiTree T) {// 非递归中序遍历二叉树 if(T==NULL) return ; stack<BiTree> s; BiTree p = T; while(p||!s.empty()) { if(p) // p非空 { // 可以在此处统计节点 s.push(p); p = p->lchild; } else // p为空 { p = s.top(); s.pop(); cout<<p->data; p = p->rchild; } } //<end while> } */ void PreOrderTraverse_noRecursive(BiTree T) {// 非递归前序遍历二叉树 if(T==NULL) return ; SqStack s; BiTree p; InitStack(s); p = T; while(p||!EmptyStack(s)) { if(p) // p非空 { cout<<p->data; Push(s,p); p = p->lchild; } else // p为空 { Pop(s,p); p = p->rchild; } } //<end while> } void Count(BiTree T, int &leafCount, int &oneCount, int &twoCount) {// 遍历二叉树统计节点个数--非递归中序遍历 leafCount=oneCount=twoCount=0; SqStack s; InitStack(s); BiTree p = T; while(p||!EmptyStack(s)) // p非空或者栈非空 { if(p) // p非空 { if(p->lchild==NULL&&p->rchild==NULL) // 叶子节点 leafCount++; else if(p->lchild!=NULL&&p->rchild!=NULL) // 二度节点 twoCount++; else // 一度节点 oneCount++; Push(s,p); p = p->lchild; } else // p为空 { Pop(s,p); p = p->rchild; } } // <end while> } int NodeCount(BiTree T) {// 统计二叉树T结点个数 if(T == NULL) return 0; else return NodeCount(T->lchild)+NodeCount(T->rchild)+1; } void CopyBiTree(BiTree T, BiTree & T2) {// 复制一棵完全一样的二叉树 if(T == NULL) // 空树，则递归结束 { T2 = NULL; return ; } else { T2 = new BiTNode; T2->data = T->data; CopyBiTree(T->lchild,T2->lchild); // 递归复制 CopyBiTree(T->rchild,T2->rchild); // 递归复制 }// <end else> } void HierarchicalOrder_TraverseBiTree_Count(BiTree T, int &leafCount, int &oneCount, int &twoCount) {// 层次遍历二叉树统计节点个数 leafCount=oneCount=twoCount=0; if(T==NULL) return; // 空树 BiTree p; SqQueue Q; InitQueue(Q); QueueIn(Q,T); while(!EmptyQueue(Q)) { p = QueueOut(Q); // 统计节点 if(p->lchild==NULL&&p->rchild==NULL) // 叶子节点 leafCount++; else if(p->lchild!=NULL&&p->rchild!=NULL) // 二度节点 twoCount++; else // 一度节点 oneCount++; if(p->lchild) QueueIn(Q,p->lchild); if(p->rchild) QueueIn(Q,p->rchild); } //<end while> } int Width(BiTree T) {// 层序遍历统计二叉树宽度 if(T==NULL) return 0; // 空树宽度为0 BiTree Q[1000], p; // Q 是队列 存 放二叉树节点指针，需要容量足够大 int front=1, rear=1, last=1; // front rear 是队列的头和尾，last存放某层最右边的节点在Q中的位置 int temp=0, maxw=0; // temp记录同层节点个数 Q[rear] = T; // 根节点入队 while(front<=last) { p = Q[front++]; temp++; if(p->lchild) Q[++rear] = p->lchild; if(p->rchild) Q[++rear] = p->rchild; if(front>last) { last = rear; // 将下一行的最右节点的位置赋给last if(temp>maxw) maxw = temp; temp = 0; } } //<end while> return maxw; } int Depth(BiTree &T) {// 后序遍历求二叉树深度 if(T==NULL) return 0; // 空树返回0 else { int m = Depth(T->lchild); // 递归计算左子树深度 int n = Depth(T->rchild); // 递归计算右子树深度 if(m>n) return (m+1); else return (n+1); } } int main() { BiTree T; printf("先序创建二叉树，请输入：\n"); CreateBiTree(T); printf("\nInOrderTraverse--递归中序遍历\n"); InOrderTraverse(T); printf("\nnOrderTraverse_noRecursive--非递归中序遍历\n"); InOrderTraverse_noRecursive(T); printf("\nPreOrderTraverse--递归先序遍历\n"); PreOrderTraverse(T); printf("\nPreOrderTraverse_noRecursive--非递归先序遍历\n"); PreOrderTraverse_noRecursive(T); printf("\nPostOrderTraverse--递归后序遍历\n"); PostOrderTraverse(T); printf("\nHierarchicalOrder_TraverseBiTree--层序遍历\n"); HierarchicalOrder_TraverseBiTree(T); int leafnum=0,onenum=0,twonum=0; HierarchicalOrder_TraverseBiTree_Count(T,leafnum,onenum,twonum); printf("\n层序遍历统计节点：leafnum=%d,onenum=%d,twonum=%d\n",leafnum,onenum,twonum); leafnum=onenum=twonum=0; Count(T,leafnum,onenum,twonum); printf("\n非递归中序遍历统计节点：leafnum=%d,onenum=%d,twonum=%d\n",leafnum,onenum,twonum); int width = Width(T); printf("\n层序遍历统计二叉树最大宽度：width=%d\n",width); int depth = Depth(T); printf("\n后序遍历统计二叉树深度：depth=%d\n",depth); int nodenum = NodeCount(T); printf("\n该二叉树的节点个数为： nodenum=%d\n",nodenum); BiTree NewT; CopyBiTree(T,NewT); printf("\n复制后的二叉树的中序遍历：\n"); InOrderTraverse(NewT); } /* 测试数据： AB#CD###EF##HI##G## A / \ B E \ /\ C F H / /\ D I G ABD##E##CF##G## A / \ B C /\ /\ D E F G */
