【山大909算法题】2014-T2

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.完整代码

#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(")");
}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.运行结果