河北沧为信息技术有限公司seo二级目录

【实验目的】

（1）进一步掌握指针变量的用途和程序设计方法。；

（2）掌握二叉树的结构特征，以及链式存储结构的特点及程序设计方法；

（3）掌握用指针类型描述、访问和处理二叉树的运算。

【实验准备】

（1）阅读二叉树各种基本运算算法的相关内容；

（2）熟悉二叉树各种基本运算的实现算法。

【实验要求】

（1）采用函数调用的方式完成；

（2）文件funp5-1.cpp的作用是完成二叉树的各种基本操作；

（3）实验提交必须有完整正确的程序，关键注释的细化以及程序运行结果的截图。

【实验内容】

编写一个程序，实现二叉树各种基本运算算法。

（1）输出二叉树B。

（2）输出二叉树B的深度。

（3）输出二叉树B的宽度。

（4）输出二叉树B的结点个数。

（5）输出二叉树B的叶子结点个数。

【部分功能程序见课本p167】

 

#include <stdio.h>
#include <malloc.h>
#define MaxSize 100
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 != '\0') {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;elsereturn 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;}elsereturn 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);}
}int main()
{BTNode* b, * p, * lp, * rp;;CreateBTNode(b, "A(B(D(,G)),C(E,F(H)))");printf("二叉树的基本运算如下:\n");printf("  (1)输出二叉树b:"); DispBTNode(b); printf("\n");printf("  (2)二叉树b的深度:%d\n", BTNodeDepth(b));printf("  (3)二叉树b的宽度:%d\n", BTWidth(b));printf("  (4)二叉树b的结点个数:%d\n", Nodes(b));printf("  (5)二叉树b的叶子节点个数:%d\n", LeafNodes(b));DestroyBTNode(b);return 0;
}