在二叉树中找出和为某一值的所有路径 对给定的任意一颗单向二叉树，所有节点数据域存放的是不同的且
发布网友
发布时间：2022-05-29 20:28
我来回答
共1个回答
热心网友
时间：2023-11-22 19:03
#include<stdio.h>
#include<malloc.h>
typedef struct
{
int data;
struct Node*left;
struct Node*right;
}Node;
int s(int *a,int len)//求和函数
{
int i=0,sum=0;
for(;i<len;i++)
sum+=a[i];
return sum;
}
int search(Node*node,int sum,int *now,int len)//递归搜索
{
int i=0,t1=0,t2=0;
if(node->left==NULL&&node->right==NULL)
{
now[len++]=node->data;
if(s(now,len)==sum)
{
FILE*fout=fopen("output.txt","a+");
for(i=0;i<len;i++)
fprintf(fout,"%d ",now[i]);
fprintf(fout,"\n");
fclose(fout);
return 1;
}
else return 0;
}
else {
now[len]=node->data;
if(node->left!=NULL)t1=search(node->left,sum,now,len+1);
if(node->right!=NULL)t2=search(node->right,sum,now,len+1);
return t1||t2;
}
}
int main()
{
int sum,num_node,root,lchild,rchild,front=0,back=0,temp,len=0;
Node*node;
int*now;
FILE*fin=fopen("input.txt","r");
FILE*fout;
fscanf(fin,"%d%d",&sum,&num_node);
now=malloc(sizeof(int)*num_node);
node=(Node*)malloc(sizeof(Node)*num_node);
while(fscanf(fin,"%d%d%d",&root,&lchild,&rchild)!=EOF)
{
if(front==0)
node[back++].data=root;
if(node[front].data!=root)
{
fout=fopen("output.txt","w");
fprintf(fout,"ERROR\n");
return 1;
}
else
{
temp=front;
if(lchild==-1)node[temp].left=NULL;
else {
node[back].data=lchild;
node[temp].left=&node[back];
back++;
}
if(rchild==-1)node[temp].right=NULL;
else {
node[back].data=rchild;
node[temp].right=&node[back];
back++;
}
front++;
}
}//建树
if(search(node,sum,now,len)==0)
{
fout=fopen("output.txt","w");
fprintf(fout,"NULL\n");
fclose(fout);
}
fclose(fin);
return 0;
}来自：求助得到的回答
2008年9月计算机2级C语言
经过对部分考生的调查以及对近年真题的总结分析,笔试部分经常考查的是算法复杂度、数据结构的概念、栈、二叉树的遍历、二分法查找,读者应对此部分进行重点学习。 详细重点学习知识点: 1.算法的概念、算法时间复杂度及空间复杂度的概念 2.数据结构的定义、数据逻辑结构及物理结构的定义 3.栈的定义及其运算、线性链表的...
4. 设二叉树的存储结构为二叉链表,试写出算法(C函数):将所有结点的左右...
若结点 x是根结点或不在 BT中或是其双亲的左 /右子树根 ,则函树值 为 “空 ”。(6)CRT_BT(x,LBT,RBT) 建树操作。生成一棵以结点 x为根，二叉树 LBT和 RBT分别为左， 右子树的二叉树。(7)INS_LCHILD(BT,y,x) 和 INS_RCHILD(BT,x) 插入子树操作。将以结点 x为根且右子树为空的...
数据结构问题
A、高度等于其结点数B、任一结点无左孩子C、任一结点无右孩子D、空或只有一个结点第2题 (2.0) 分 关于哈夫曼树,下列叙述正确的是( )。A、可能有度为1的结点B、总是完全二叉树C、有可能是满二叉树D、WPL是深度最大叶子的带权路径长度第3题 (2.0) 分 给定整数集合{3,5,6,9,12},与之对应的哈夫曼...
决策树(Decision Tree)
显然从所有可能的决策树中选取最优决策树是NP完全问题,所以在实际中通常采用启发式的方法,近似求解这一最优化问题: 通过递归的选择最优特征,根据该特征对训练数据进行划分直到使得各个子数据集有一个最好的分类,最终生成特征树 。当然,这样得到的决策树实际上是次最优(sub-optimal)的。进一步的,由于决策树的算法特...
最优二叉树
．最优二叉树或哈夫曼树 在权为wl w … wn的n个叶子所构成的所有二叉树中 带权路径长度最小(即代价最小)的二叉树称为最优二叉树或哈夫曼树 【例】给定 个叶子结点a b c和d 分别带权 和 构造如下图所示的三棵二叉树(还有许多棵) 它们的带权路径长度分别为 (a)WPL= * + * + *...
这该怎么做?高数求解
所以,以随机二叉树为例,具体的方法是:从一个空的根节点开始,在每一步中确定下一个内部节点在空节点中的位置。重复进行直到所有内部节点都被分配为止。不过,在通常情况下,数学表达式树不一定是二叉树,内部节点可能只有1个子节点。如此,就要考虑根节点和下一内部节点参数数量的二维概率分布,记作 L(e,n)。接下来...
二叉树最小权路径长度算法?
方法1：具体算法如下。举例说明。首先构造哈夫曼树。哈夫曼树的构建顺序无需特定规则，但按照某种规律绘制可以更清晰地展示思路。这里我们以左节点作为顺序。接着，依次累加所有叶子节点的带权路径长度。从构造的哈夫曼树中可以得知所有节点的路径长度，如“16”节点的路径长度为2。因此，WPL=(16+21+30)...
计算机二级ms office高级应用基础知识
其中指针用于指向该结点的前一个或后一个结点(即前件或后件)。 1.6树和二叉树 1.树的基本概念 树是简单的非线性结构,树中有且仅有一个没有前驱的节点称为“根”,其余节点分成m个互不相交的有限集合T1,T2,…,T}mm,每个集合又是一棵树,称T1,T2,…,T}mm为根结点的子树。 父节点:每一个节点只有一...
数据结构中,满二叉树,结点,叶子节点,是什么?
满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树。国内教程定义：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。节点：就是一个图中的0、1、2~...
什么是二叉树?
在计算机科学中,二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。 二叉树的每个结点至多只有二棵子树(不存在度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。二叉树的第i层至多有2^{i-1}个结点...
