当前位置：首页 > news >正文

针对考研的C语言学习（2014二叉树大题代码实战）

news 2025/6/30 20:02:54

题目描述

解析

1.递归思想遍历节点，若是叶子结点就累加计算的wpl，反之继续遍历

2.代码如下

//树
typedef struct trees {ElemType data;struct trees* lc;struct trees* rc;
}treeNode, * Tree;

3.算法设计

//deep路径长度也叫做深度，0开始
void getWPL(Tree& t, int deep,int &sum)
{//判断左子树if (t->lc){getWPL(t->lc, deep + 1, sum);}if (t->rc){getWPL(t->rc, deep + 1, sum);}if (!t->lc && !t->rc){//叶子结点sum += deep * t->data;return;}
}

【注】递归一定要有终止条件，否则会死循环。

可运行代码

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
typedef char ElemType;//树
typedef struct trees {ElemType data;struct trees* lc;struct trees* rc;
}treeNode, * Tree;//链表
typedef struct Links {Tree tree;struct Links* next;
}LNode, * LinkList;//队列
typedef struct {LinkList front;LinkList rear;
}LinkQue;void init_que(LinkQue& q)
{q.front = q.rear = (LinkList)calloc(1, sizeof(LNode));q.front = q.rear;
}bool isEmpty(LinkQue& q)
{return q.front == q.rear;
}//入队
void push_que(LinkQue& q, Tree tree)
{//新建链表节点LinkList newList = (LinkList)calloc(1, sizeof(LNode));newList->next = NULL;newList->tree = tree;q.rear->next = newList;q.rear = q.rear->next;
}
bool pop_que(LinkQue& q, Tree& tree)
{if (isEmpty(q)){return false;}LinkList del = q.front->next;//头结点不存数据，第一个节点才是真的数据起始位置q.front->next = del->next;//断链tree = del->tree;if (q.rear == del)//只剩下尾节点的数据{q.rear = q.front;//置空}free(del);return true;
}void build_tree(Tree& tree)
{LinkQue q;init_que(q);LinkList cur = NULL;ElemType data;while (scanf("%c", &data) && data != '\n'){Tree newTree = (Tree)calloc(1, sizeof(treeNode));//申请新的树的节点newTree->data = data;if (tree == NULL){tree = newTree;push_que(q, tree);//入队cur = q.rear;}else{if (cur->tree->lc == NULL){cur->tree->lc = newTree;push_que(q, newTree);}else{cur->tree->rc = newTree;push_que(q, newTree);//改变当前父亲节点cur = cur->next;}}}
}void getWPL(Tree& t, int deep,int &sum)
{//判断左子树if (t->lc){getWPL(t->lc, deep + 1, sum);}if (t->rc){getWPL(t->rc, deep + 1, sum);}if (!t->lc && !t->rc){//叶子结点sum += deep * t->data;return;}
}int main()
{Tree tree = NULL;build_tree(tree);int sum = 0;getWPL(tree, 0, sum);printf("%d\n", sum);return 0;
}