佛山专业网站制作公司,徐州建站费用,长沙网站制作哪里好,微信服务号怎么做商城文章目录 1.原题2.算法思想3.关键代码4.完整代码5.运行结果 1.原题
二叉树采用二叉链表存储结构#xff0c;设计算法#xff0c;判断二叉树是否为满二叉树。叙述算法思想并给出算法实现。
2.算法思想
通过一次遍历#xff0c;得到结点个数和树的高度。用结点个数和树的高… 文章目录 1.原题2.算法思想3.关键代码4.完整代码5.运行结果 1.原题
二叉树采用二叉链表存储结构设计算法判断二叉树是否为满二叉树。叙述算法思想并给出算法实现。
2.算法思想
通过一次遍历得到结点个数和树的高度。用结点个数和树的高度的关系来判断是否为满二叉树。
3.关键代码
/*** struct treeNode* brief 二叉树节点结构体。*/
struct treeNode {int data; /** 节点中存储的数据 */struct treeNode *lchild; /** 指向左子节点的指针 */struct treeNode *rchild; /** 指向右子节点的指针 */
};/*** brief 计算二叉树的高度** 递归计算二叉树的高度并记录节点数。** param root 二叉树根节点指针* param n 指向节点数的指针记录二叉树的节点数* return int 二叉树高度*/
int treeHeight(struct treeNode *root, int *n) {// 若根节点为空则高度为0if (root NULL) {return 0;} else {// 递归计算左子树高度int leftTreeHeight treeHeight(root-lchild, n);// 若左子树不为空则节点数加1if (leftTreeHeight) {(*n);}// 递归计算右子树高度int rightTreeHeight treeHeight(root-rchild, n);// 若右子树不为空则节点数加1if (rightTreeHeight) {(*n);}// 返回左右子树中的最大高度并加上根节点的高度return (leftTreeHeight rightTreeHeight ? leftTreeHeight : rightTreeHeight) 1;}
}/*** brief 判断二叉树是否为满二叉树** 验证二叉树是否为满二叉树并输出节点数及高度信息。** param root 二叉树根节点指针*/
void isTreeFull(struct treeNode *root) {// 若根节点为空则是空树if (root NULL) {printf(This is an empty tree.\n);return;}int n 1;int height treeHeight(root, n); // 获取树的高度和节点数printf(number of the tree: %d\n, n); // 输出节点数printf(height of the tree: %d\n, height); // 输出树的高度// 判断是否为满二叉树if (n ((int) pow(2, height) - 1)) {printf(This is a full tree.\n); // 是满二叉树} else {printf(This is not a full tree.\n); // 不是满二叉树}
}4.完整代码
/*** file main.c* brief 实现了二叉树及其相关操作。*/#include stdio.h
#include stdlib.h
#include tgmath.h/*** struct treeNode* brief 二叉树节点结构体。*/
struct treeNode {int data; /** 节点中存储的数据 */struct treeNode *lchild; /** 指向左子节点的指针 */struct treeNode *rchild; /** 指向右子节点的指针 */
};/*** brief 计算二叉树的高度** 递归计算二叉树的高度并记录节点数。** param root 二叉树根节点指针* param n 指向节点数的指针记录二叉树的节点数* return int 二叉树高度*/
int treeHeight(struct treeNode *root, int *n) {// 若根节点为空则高度为0if (root NULL) {return 0;} else {// 递归计算左子树高度int leftTreeHeight treeHeight(root-lchild, n);// 若左子树不为空则节点数加1if (leftTreeHeight) {(*n);}// 递归计算右子树高度int rightTreeHeight treeHeight(root-rchild, n);// 若右子树不为空则节点数加1if (rightTreeHeight) {(*n);}// 返回左右子树中的最大高度并加上根节点的高度return (leftTreeHeight rightTreeHeight ? leftTreeHeight : rightTreeHeight) 1;}
}/*** brief 判断二叉树是否为满二叉树** 验证二叉树是否为满二叉树并输出节点数及高度信息。** param root 二叉树根节点指针*/
void isTreeFull(struct treeNode *root) {// 若根节点为空则是空树if (root NULL) {printf(This is an empty tree.\n);return;}int n 1;int height treeHeight(root, n); // 获取树的高度和节点数printf(number of the tree: %d\n, n); // 输出节点数printf(height of the tree: %d\n, height); // 输出树的高度// 判断是否为满二叉树if (n ((int) pow(2, height) - 1)) {printf(This is a full tree.\n); // 是满二叉树} else {printf(This is not a full tree.\n); // 不是满二叉树}
}/*** brief 创建新节点。* param data 节点数据。* return 新节点指针。*/
struct treeNode *createNode(int data) {struct treeNode *newNode (struct treeNode *) malloc(sizeof(struct treeNode));newNode-data data;newNode-lchild NULL;newNode-rchild NULL;return newNode;
}/*** brief 输出二叉树的括号表示法结构。* param root 二叉树根节点指针。*/
void printTree(struct treeNode *root) {if (root NULL) {return;}printf((%d, root-data);if (root-lchild ! NULL || root-rchild ! NULL) {printf( );if (root-lchild NULL) {printf(( ));} else {printTree(root-lchild);}printf( );if (root-rchild NULL) {printf(( ));} else {printTree(root-rchild);}}printf());
}/*** brief 主函数展示二叉树操作。* return 程序退出状态。*/
int main() {struct treeNode *root createNode(1); // 根节点为1root-lchild createNode(2);root-rchild createNode(3);root-lchild-lchild createNode(4);root-lchild-rchild createNode(5);root-rchild-lchild createNode(6);root-rchild-rchild createNode(7);printf(Binary Tree in Parenthesis Representation: );printTree(root);printf(\n);isTreeFull(root);return 0;
}5.运行结果
