（1）加深对二叉树性质和各种存储结构的特点及适用范围广义表的理解；
（2）熟练掌握二叉树的遍历算法。
【实验要求】
（1）采用函数调用的方式完成；
（2）文件funp5-2tree.cpp的作用是完成二叉树的各种遍历操作；
（3）实验提交必须有完整正确的程序、注释的细化以及程序运行结果的截图。
【实验内容】
编写一个程序，实现以下二叉树各种遍历的递归算法：
（1）用括号表示法输入一棵二叉树，并创建二叉链bt
（2）求二叉树的高度
（3）求二叉树的叶子结点个数
（4）再以括号表示法或者凹入表示法输出该二叉树
（5）输出从每个叶子结点到根结点的路径
（6）输出三种遍历（先序，中序，后序）的结果。
#include#include #define MaxSize 100 #include using namespace std; typedef char ElemType; typedef struct node { ElemType data; struct node* lchild; struct node* rchild; } BTNode; void CreateBTNode(BTNode*& b, char* str) { BTNode* St[MaxSize], * p = NULL; int top = -1, k, j = 0; char ch; b = NULL; ch = str[j]; while (ch != ' ') { switch (ch) { case '(':top++; St[top] = p; k = 1; break; case ')':top--; break; case ',':k = 2; break; default:p = (BTNode*)malloc(sizeof(BTNode)); p->data = ch; p->lchild = p->rchild = NULL; if (b == NULL) b = p; else { switch (k) { case 1:St[top]->lchild = p; break; case 2:St[top]->rchild = p; break; } } } j++; ch = str[j]; } } BTNode* FindNode(BTNode* b, ElemType x) { BTNode* p; if (b == NULL) return NULL; else if (b->data == x) return b; else { p = FindNode(b->lchild, x); if (p != NULL) return p; else return FindNode(b->rchild, x); } } BTNode* LchildNode(BTNode* p) { return p->lchild; } BTNode* RchildNode(BTNode* p) { return p->rchild; } int BTNodeDepth(BTNode* b) { int lchilddep, rchilddep; if (b == NULL) return(0); else { lchilddep = BTNodeDepth(b->lchild); rchilddep = BTNodeDepth(b->rchild); return (lchilddep > rchilddep) ? (lchilddep + 1) : (rchilddep + 1); } } void DispBTNode(BTNode* b) { if (b != NULL) { printf("%c", b->data); if (b->lchild != NULL || b->rchild != NULL) { printf("("); DispBTNode(b->lchild); if (b->rchild != NULL) printf(","); DispBTNode(b->rchild); printf(")"); } } } int BTWidth(BTNode* b) { struct { int lno; BTNode* p; } Qu[MaxSize]; int front, rear; int lnum, max, i, n; front = rear = 0; if (b != NULL) { rear++; Qu[rear].p = b; Qu[rear].lno = 1; while (rear != front) { front++; b = Qu[front].p; lnum = Qu[front].lno; if (b->lchild != NULL) { rear++; Qu[rear].p = b->lchild; Qu[rear].lno = lnum + 1; } if (b->rchild != NULL) { rear++; Qu[rear].p = b->rchild; Qu[rear].lno = lnum + 1; } } max = 0; lnum = 1; i = 1; while (i <= rear) { n = 0; while (i <= rear && Qu[i].lno == lnum) { n++; i++; } lnum = Qu[i].lno; if (n > max) max = n; } return max; } else return 0; } int Nodes(BTNode* b) { int num1, num2; if (b == NULL) return 0; else if (b->lchild == NULL && b->rchild == NULL) return 1; else { num1 = Nodes(b->lchild); num2 = Nodes(b->rchild); return (num1 + num2 + 1); } } int LeafNodes(BTNode* b) { int num1, num2; if (b == NULL) return 0; else if (b->lchild == NULL && b->rchild == NULL) return 1; else { num1 = LeafNodes(b->lchild); num2 = LeafNodes(b->rchild); return (num1 + num2); } } void DestroyBTNode(BTNode*& b) { if (b != NULL) { DestroyBTNode(b->lchild); DestroyBTNode(b->rchild); free(b); } } void AllPath(BTNode* b) { struct snode { BTNode* node; int parent; } Qu[MaxSize]; int front, rear, p; front = rear = -1; rear++; Qu[rear].node = b; Qu[rear].parent = -1; while (front < rear) { front++; b = Qu[front].node; if (b->lchild == NULL && b->rchild == NULL) { printf("%c 到根节点路径：", b->data); p = front; while (Qu[p].parent != -1) { printf("%c ", Qu[p].node->data); p = Qu[p].parent; } printf("%cn", Qu[front].node->data); } if (b->lchild != NULL) { rear++; Qu[rear].node = b->lchild; Qu[rear].parent = front; } if (b->rchild != NULL) { rear++; Qu[rear].node = b->rchild; Qu[rear].parent = front; } } } void PreOrder_recursion(BTNode* b) { if (b != NULL) { cout << b->data; PreOrder_recursion(b->lchild); PreOrder_recursion(b->rchild); } } void InOrder_recursion(BTNode* b) { if (b != NULL) { InOrder_recursion(b->lchild); cout << b->data; InOrder_recursion(b->rchild); } } void PostOrder_recursion(BTNode* b) { if (b != NULL) { PostOrder_recursion(b->lchild); PostOrder_recursion(b->rchild); cout << b->data; } } int main() { BTNode* b, * p, * lp, * rp; char str[10]; printf("输入括号表示法的二叉树：n"); scanf("%s", str); CreateBTNode(b, str); printf("成功创建二叉树n"); printf("二叉树的括号表示法：n"); DispBTNode(b); printf("n"); printf("二叉树的高度:%dn", BTNodeDepth(b)); printf("二叉树的结点数:%dn", Nodes(b)); printf("二叉树b的叶子节点数:%dnn", LeafNodes(b)); printf("输出叶子结点到根结点的路径n"); AllPath(b); printf("n三种遍历:n"); cout << "先序遍历"; PreOrder_recursion(b); printf("n"); cout << "中序遍历"; InOrder_recursion(b); printf("n"); cout << "后序遍历"; PostOrder_recursion(b); printf("n"); DestroyBTNode(b); return 0; }
