本文共 2384 字，大约阅读时间需要 7 分钟。
数据结构课程
百度笔试题目：
给出一个二叉树，和一个整型值，求出二叉树上所有从根到叶子的路径，并且此路径上各个节点的权值之和等于给出的整型值。
解题思路：
根据二叉树的先根遍历思想，通过一个栈保存从根到当前节点的路径，每遍历一个节点，都从sum值中减去此节点的权值，此点遍历结束后，再从栈中弹出此节点，并在sum中加上此节点的权值。当sum为零且当前节点为叶子节点时，打印栈中保存的路径。
#include
#include
#define STACK_MAX 100
int sum = 25;
typedef struct _node{
int data;
struct _node *lchild;
struct _node *rchild;
}TreeNode;
int stack[STACK_MAX + 1] =
{0};
int top = 0;
int bottom = 0;
int push(int m)
{
if (top+1 > STACK_MAX) {
printf("stack full!\n");
return 0;
} else {
printf("push %d\n",m);
stack[++top] = m;
return 1;
}
}
int pop(int *m)
{
if (top == 0) {
printf("stack empty!\n");
return 0;
} else {
*m = stack[top--];
printf("pop %d\n",*m);
return 1;
}
}
int print_stack()
{
int i;
if (top == 0) {
printf("stack empty!\n");
return 0;
} else {
i = 1;
while (i <= top) {
printf("%d ",stack[i++]);
}
printf("\n");
return 1;
}
}
void create_tree(TreeNode
**node_p,FILE *fp)
{
int m;
fscanf(fp,"%d",&m);
if (m >= 0) {
*node_p = (TreeNode *)malloc(sizeof(TreeNode));
if (!(*node_p)) {
printf("err!!");
exit(1);
}
(*node_p)->data = m;
create_tree(&((*node_p)->lchild),fp);
create_tree(&((*node_p)->rchild),fp);
} else {
*node_p = NULL;
}
}
void print_tree(TreeNode
*node_p)
{
if (node_p != NULL) {
printf("%d ", node_p->data);
print_tree(node_p->lchild);
print_tree(node_p->rchild);
}
}
void del_tree(TreeNode
*node_p)
{
if (node_p != NULL) {
del_tree(node_p->lchild);
del_tree(node_p->rchild);
free(node_p);
}
}
void check_sum(TreeNode
*node_p)
{
int m;
if (node_p != NULL) {
push(node_p->data);
sum -= node_p->data;
printf("check %d begin\n",node_p->data);
if (node_p->lchild == NULL
&& node_p->rchild ==
NULL && sum == 0) {
print_stack();
}
check_sum(node_p->lchild);
check_sum(node_p->rchild);
printf("check %d over\n",node_p->data);
pop(&m);
sum += m;
}
}
int main()
{
FILE *fp = NULL;
fp = fopen("tree_sum_input.data","r");
if (fp == NULL) {
printf("fopen err!");
return 0;
}
TreeNode *root_p = NULL;
create_tree(&root_p,fp);
print_tree(root_p);
check_sum(root_p);
del_tree(root_p);
fclose(fp);
return 0;
}
5
3
7
10
-1
-1
-1
8
-1
9
-1
-1
2
1
-1
-1
11
-1
-1
数据结构课程
http://hi.baidu.com/数据结构课程推荐文章:
1. 二叉树的建立与遍历
2. poj 2255 Tree Recovery 二叉树
3. 创建二叉树 并进行先序、中序、后序排列 求叶子节点数、总节点数和树的深度
4. 二叉树的中序、前序、后序的递归、非递归遍历算法，包含建树的实现(一)
5. 二叉树的后序遍历 pascal
6. A Binary Apple Tree 苹果二叉树
7. ds18b20二叉树搜索算法
8. 转：由二叉树的遍历还原二叉树
9. java jdk5.0 范类实现的 二叉树 对任何对象排序 BinaryTree
10. 数据结构之二叉树(C语言)实现文件
转载地址：https://blog.csdn.net/weixin_32467749/article/details/114621261 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！
发表评论
最新留言
关于作者
