Question

数据结构C语言题目，求详细代码，大神你好厉害的，求你帮帮忙

给定一个二叉树，对于这个二叉树结点的值，同一个边上的值不能同时选取(即两个结点的关系为双亲和孩子的关系, 则两个结点在同一个边上, 那么这两个结点至多只能选取一个)，将选取的结点的值相加, 求这个二叉树所能选取出的结点值的和的最大值。输入的严格按照二叉树的先序遍历构造二叉树。

如：输入序列 3 2 0 3 00 3 0 1 0 0，（0代表空节点）画出如下二叉树，最大值为3+3+1=7。

3

/ \

2 3

\ \

3 1

3
/ \
4 5
/ \ \
1 3 1

二叉树节点参考定义为如下形式。
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/

输入：
3 2 0 3 0 0 3 0 1 0 0
3 4 1 0 0 3 0 0 5 0 1 0 0

输出：
7
9

Answer 1

#include<stdio.h>
#include<malloc.h>

struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
};

#define size sizeof(struct TreeNode)

struct TreeNode * createTree() {
	int val;
	struct TreeNode *tree;
	scanf("%d",&val);
	if(val) {
		tree = (struct TreeNode *)malloc(size);
		tree->val = val;
		tree->left = createTree();
		tree->right = createTree();
	} else {
		tree = NULL;
	}
	return tree;
}

void visit(struct TreeNode *tree) {
	printf("%d ",tree->val);
}

int preorder_recursive(struct TreeNode *tree) {
	if (tree) {
		visit(tree);
		return 1 + preorder_recursive(tree->left) + preorder_recursive(tree->right);
	}
	return 0;
}

int searchSum(struct TreeNode *tree,struct TreeNode *treePath[],int length,int sum) {
	if(tree == NULL) return 0;
	int flag = 1;
	for(int i=0; i<length; i++) {
		if(treePath[i]!=NULL) {
			if(treePath[i] == tree->left || treePath[i] == tree->right || treePath[i]->left == tree || treePath[i]->right == tree) {
				flag = 0;
			}
		}
	}
	if(flag) {
		treePath[length] = tree;
		int sum1 = sum + tree->val + searchSum(tree->left,treePath,length+1,sum) + searchSum(tree->right,treePath,length+1,sum);
		treePath[length] = NULL;
		int sum2 = sum + searchSum(tree->left,treePath,length,sum) + searchSum(tree->right,treePath,length,sum);
		if(sum1 > sum2) sum = sum1;
		else sum = sum2;
	} else {
		sum += searchSum(tree->left,treePath,length,sum) + searchSum(tree->right,treePath,length,sum);
	}
	return sum;
}

int main() {
	struct TreeNode *tree = createTree();
	printf("二叉树：\n");
	int count = preorder_recursive(tree);
	struct TreeNode *treePath[count];
	for(int i=0; i<count; i++) {
		treePath[i]=NULL;
	}
	printf("\n和：\n%d", searchSum(tree,treePath,0,0));
}

追问

谢谢，谢谢，大神谢谢你

Answer 2

wget，基本每个带网络功能的Linux系统都会有，-c选项。/art/201109/291204.htm