判断一棵树是否为满二叉树的算法c语言判断一棵树是否为满二叉树的算法（C语言）满二叉树是一种特殊的二叉树，每个节点要么没有子节点，要么有两个子节点。
判断一棵树是否为满二叉树的算法可以通过以下步骤实现：1. 定义二叉树的数据结构在C语言中，可以使用结构体定义二叉树的节点。
每个节点包含一个数据域和两个指针域，分别指向左子节点和右子节点。
```cstruct TreeNode {int data;struct TreeNode* left;struct TreeNode* right;};```2. 实现判断函数编写一个递归函数，用于判断给定二叉树是否为满二叉树。
函数的输入参数为根节点指针，返回值为布尔类型。
```cint isFullBinaryTree(struct TreeNode* root) {// 如果根节点为空，则返回真if (root == NULL) {return 1;}// 如果只有一个子节点或没有子节点，则返回假if ((root->left == NULL && root->right != NULL) ||(root->left != NULL && root->right == NULL)) {return 0;}// 递归判断左子树和右子树return isFullBinaryTree(root->left) && isFullBinaryTree(root->right);}```3. 测试样例可以编写一些测试样例来验证判断函数的正确性。
例如，下面是一个满二叉树和一个非满二叉树的示例：```cint main() {// 满二叉树struct TreeNode* root1 = (struct TreeNode*)malloc(sizeof(struct TreeNode));root1->data = 1;root1->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));root1->left->data = 2;root1->left->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));root1->left->left->data = 4;root1->left->left->left = NULL;root1->left->left->right = NULL;root1->left->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));root1->left->right->data = 5;root1->left->right->left = NULL;root1->left->right->right = NULL;root1->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));root1->right->data = 3;root1->right->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));root1->right->left->data = 6;root1->right->left->left = NULL;root1->right->left->right = NULL;root1->right->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));root1->right->right->data = 7;root1->right->right->left = NULL;root1->right->right->right = NULL;// 非满二叉树struct TreeNode* root2 = (struct TreeNode*)malloc(sizeof(struct TreeNode));root2->data = 1;root2->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));root2->left->data = 2;root2->left->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));root2->left->left->data = 4;root2->left->left->left = NULL;root2->left->left->right = NULL;root2->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));root2->right->data = 3;root2->right->left = NULL;root2->right->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));root2->right->right->data = 7;root2->right->right->left = NULL;root2->right->right->right = NULL;// 判断是否为满二叉树if (isFullBinaryTree(root1)) {printf("root1是满二叉树\n");} else {printf("root1不是满二叉树\n");}if (isFullBinaryTree(root2)) {printf("root2是满二叉树\n");} else {printf("root2不是满二叉树\n");}return 0;}```运行上述代码，输出结果为：```root1是满二叉树root2不是满二叉树```根据以上算法和示例，我们可以判断一棵树是否为满二叉树。
题目:二叉排序树的实现1 内容和要求1）编程实现二叉排序树，包括生成、插入，删除；2）对二叉排序树进展先根、中根、和后根非递归遍历；3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。
4）分别用二叉排序树和数组去存储一个班(50 人以上)的成员信息(至少包括学号、姓名、成绩3 项),比照查找效率，并说明在什么情况下二叉排序树效率高,为什么?2 解决方案和关键代码2.1 解决方案：先实现二叉排序树的生成、插入、删除，编写DisplayBST函数把遍历结果用树的形状表示出来。
前中后根遍历需要用到栈的数据构造，分模块编写栈与遍历代码。
要求比照二叉排序树和数组的查找效率，首先建立一个数组存储一个班的成员信息，分别用二叉树和数组查找，利用clock〔〕函数记录查找时间来比照查找效率。
2.2关键代码树的根本构造定义及根本函数typedef struct{KeyType key;} ElemType;typedef struct BiTNode//定义链表{ElemType data;struct BiTNode *lchild, *rchild;}BiTNode, *BiTree, *SElemType;//销毁树int DestroyBiTree(BiTree &T){if (T != NULL)free(T);return 0;}//清空树int ClearBiTree(BiTree &T){if (T != NULL){T->lchild = NULL;T->rchild = NULL;T = NULL;}return 0;}//查找关键字,指针p返回int SearchBST(BiTree T, KeyType key, BiTree f, BiTree &p) {if (!T){p = f;return FALSE;}else if EQ(key, T->data.key){p = T;return TRUE;}else if LT(key, T->data.key)return SearchBST(T->lchild, key, T, p);elsereturn SearchBST(T->rchild, key, T, p);}二叉树的生成、插入，删除生成void CreateBST(BiTree &BT, BiTree p){int i;ElemType k;printf("请输入元素值以创立排序二叉树:\n");scanf_s("%d", &k.key);for (i = 0; k.key != NULL; i++){//判断是否重复if (!SearchBST(BT, k.key, NULL, p)){InsertBST(BT, k);scanf_s("%d", &k.key);}else{printf("输入数据重复！\n");return;}}}插入int InsertBST(BiTree &T, ElemType e){BiTree s, p;if (!SearchBST(T, e.key, NULL, p)){s = (BiTree)malloc(sizeof(BiTNode));s->data = e;s->lchild = s->rchild = NULL;if (!p)T = s;else if LT(e.key, p->data.key)p->lchild = s;elsep->rchild = s;return TRUE;}else return FALSE;}删除//某个节点元素的删除int DeleteEle(BiTree &p){BiTree q, s;if (!p->rchild) //右子树为空{q = p;p = p->lchild;free(q);}else if (!p->lchild) //左子树为空{q = p;p = p->rchild;free(q);}else{q = p;s = p->lchild;while (s->rchild){q = s;s = s->rchild;}p->data = s->data;if (q != p)q->rchild = s->lchild;elseq->lchild = s->lchild;delete s;}return TRUE;}//整棵树的删除int DeleteBST(BiTree &T, KeyType key) //实现二叉排序树的删除操作{if (!T){return FALSE;}else{if (EQ(key, T->data.key)) //是否相等return DeleteEle(T);else if (LT(key, T->data.key)) //是否小于return DeleteBST(T->lchild, key);elsereturn DeleteBST(T->rchild, key);}return 0;}二叉树的前中后根遍历栈的定义typedef struct{SElemType *base;SElemType *top;int stacksize;}SqStack;int InitStack(SqStack &S) //构造空栈{S.base = (SElemType*)malloc(STACK_INIT_SIZE *sizeof(SElemType));if (!S.base) exit(OVERFLOW);S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK;}//InitStackint Push(SqStack &S, SElemType e) //插入元素e为新栈顶{if (S.top - S.base >= S.stacksize){S.base = (SElemType*)realloc(S.base, (S.stacksize + STACKINCREMENT)*sizeof(SElemType));if (!S.base) exit(OVERFLOW);S.top = S.base + S.stacksize;S.stacksize += STACKINCREMENT;}*S.top++ = e;return OK;}//Pushint Pop(SqStack &S, SElemType &e) //删除栈顶,应用e返回其值{if (S.top == S.base) return ERROR;e = *--S.top;return OK;}//Popint StackEmpty(SqStack S) //判断是否为空栈{if (S.base == S.top) return TRUE;return FALSE;}先根遍历int PreOrderTraverse(BiTree T, int(*Visit)(ElemType e)) {SqStack S;BiTree p;InitStack(S);p = T;while (p || !StackEmpty(S)){if (p){Push(S, p);if (!Visit(p->data)) return ERROR;p = p->lchild;}else{Pop(S, p);p = p->rchild;}}return OK;}中根遍历int InOrderTraverse(BiTree T, int(*Visit)(ElemType e)) {SqStack S;BiTree p;InitStack(S);p = T;while (p || !StackEmpty(S)){if (p){Push(S, p);p = p->lchild;}else{Pop(S, p);if (!Visit(p->data)) return ERROR;p = p->rchild;}}return OK;}后根遍历int PostOrderTraverse(BiTree T, int(*Visit)(ElemType e)) {SqStack S, SS;BiTree p;InitStack(S);InitStack(SS);p = T;while (p || !StackEmpty(S)){if (p){Push(S, p);Push(SS, p);p = p->rchild;}else{if (!StackEmpty(S)){Pop(S, p);p = p->lchild;}}}while (!StackEmpty(SS)){Pop(SS, p);if (!Visit(p->data)) return ERROR;}return OK;}利用数组存储一个班学生信息ElemType a[] = { 51, "陈继真", 88,82, "黄景元", 89,53, "贾成", 88,44, "呼颜", 90,25, "鲁修德", 88,56, "须成", 88,47, "孙祥", 87, 38, "柏有患", 89, 9, " 革高", 89, 10, "考鬲", 87, 31, "李燧", 86, 12, "夏祥", 89, 53, "余惠", 84, 4, "鲁芝", 90, 75, "黄丙庆", 88, 16, "李应", 89, 87, "杨志", 86, 18, "李逵", 89, 9, "阮小五", 85, 20, "史进", 88, 21, "秦明", 88, 82, "杨雄", 89, 23, "刘唐", 85, 64, "武松", 88, 25, "李俊", 88, 86, "卢俊义", 88, 27, "华荣", 87, 28, "杨胜", 88, 29, "林冲", 89, 70, "李跃", 85, 31, "蓝虎", 90, 32, "宋禄", 84, 73, "鲁智深", 89, 34, "关斌", 90, 55, "龚成", 87, 36, "黄乌", 87, 57, "孔道灵", 87, 38, "张焕", 84, 59, "李信", 88, 30, "徐山", 83, 41, "秦祥", 85, 42, "葛公", 85, 23, "武衍公", 87, 94, "范斌", 83, 45, "黄乌", 60, 67, "叶景昌", 99, 7, "焦龙", 89, 78, "星姚烨", 85, 49, "孙吉", 90, 60, "陈梦庚", 95,};数组查询函数void ArraySearch(ElemType a[], int key, int length){int i;for (i = 0; i <= length; i++){if (key == a[i].key){cout << "学号：" << a[i].key << " 姓名：" << a[i].name << " 成绩：" << a[i].grade << endl;break;}}}二叉树查询函数上文二叉树根本函数中的SearchBST()即为二叉树查询函数。
c语言哈夫曼树的构造及编码一、哈夫曼树概述哈夫曼树是一种特殊的二叉树，它的构建基于贪心算法。
它的主要应用是在数据压缩和编码中，可以将频率高的字符用较短的编码表示，从而减小数据存储和传输时所需的空间和时间。
二、哈夫曼树的构造1. 哈夫曼树的定义哈夫曼树是一棵带权路径长度最短的二叉树。
带权路径长度是指所有叶子节点到根节点之间路径长度与其权值乘积之和。
2. 构造步骤(1) 将待编码字符按照出现频率从小到大排序。
(2) 取出两个权值最小的节点作为左右子节点，构建一棵新的二叉树。
(3) 将新构建的二叉树加入到原来排序后队列中。
(4) 重复上述步骤，直到队列只剩下一个节点，该节点即为哈夫曼树的根节点。
3. C语言代码实现以下代码实现了一个简单版哈夫曼树构造函数：```ctypedef struct TreeNode {int weight; // 权重值struct TreeNode *leftChild; // 左子节点指针struct TreeNode *rightChild; // 右子节点指针} TreeNode;// 构造哈夫曼树函数TreeNode* createHuffmanTree(int* weights, int n) {// 根据权值数组构建节点队列，每个节点都是一棵单独的二叉树TreeNode** nodes = (TreeNode**)malloc(sizeof(TreeNode*) * n);for (int i = 0; i < n; i++) {nodes[i] = (TreeNode*)malloc(sizeof(TreeNode));nodes[i]->weight = weights[i];nodes[i]->leftChild = NULL;nodes[i]->rightChild = NULL;}// 构建哈夫曼树while (n > 1) {int minIndex1 = -1, minIndex2 = -1;for (int i = 0; i < n; i++) {if (nodes[i] != NULL) {if (minIndex1 == -1 || nodes[i]->weight < nodes[minIndex1]->weight) {minIndex2 = minIndex1;minIndex1 = i;} else if (minIndex2 == -1 || nodes[i]->weight < nodes[minIndex2]->weight) {minIndex2 = i;}}}TreeNode* newNode =(TreeNode*)malloc(sizeof(TreeNode));newNode->weight = nodes[minIndex1]->weight + nodes[minIndex2]->weight;newNode->leftChild = nodes[minIndex1];newNode->rightChild = nodes[minIndex2];// 将新构建的二叉树加入到原来排序后队列中nodes[minIndex1] = newNode;nodes[minIndex2] = NULL;n--;}return nodes[minIndex1];}```三、哈夫曼编码1. 哈夫曼编码的定义哈夫曼编码是一种前缀编码方式，它将每个字符的编码表示为二进制串。
