B-DS二叉树_输出所有目标路径

这篇具有很好参考价值的文章主要介绍了B-DS二叉树_输出所有目标路径。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

Description

给定二叉树和一个整数目标targetSum,输出所有从根结点到叶子结点的路径总和等于targetSun的路径。

B-DS二叉树_输出所有目标路径,数据结构,C++,算法,数据结构

Input

第一行输入t,表示有t个测试样例。

第二行起,每一行首先输入一个整数targetSum,接着输入n,接着输入n个整数代表一个二叉树。

以此类推共输入t个测试样例。

数组形式的二叉树表示方法与题目:DS二叉树_伪层序遍历构建二叉树 相同,输入-1表示空结点。

Output

每一行输出一个符合题意的路径,若当前的二叉树没有符合题意的路径存在,则输出"Path not found"。

每个测试样例之间用一个空行隔开。

注意输出末尾的空格。

B-DS二叉树_输出所有目标路径,数据结构,C++,算法,数据结构

 思路:

从根节点开始,判断左右子树。用数组arr保存经过的节点的值,存放路径,用递归的方法遍历树,判断根节点到叶子节点的值的和是否为目标值,在递归完当前节点左右子树之后,把路径尾部的节点删掉才不影响其他路径遍历的值。文章来源地址https://www.toymoban.com/news/detail-743264.html

#include<iostream>
#include<queue>
using namespace std;

class BitNode {
private:
	int data;
	BitNode* lc;
	BitNode* rc;
public:
	BitNode() :lc(NULL), rc(NULL) {};
	BitNode(char e) :data(e), lc(NULL), rc(NULL) {};
	~BitNode() {
		delete lc;
		delete rc;
	}
	friend class BinaryTree;
};

class BinaryTree {
private:
	BitNode* root;//头节点
	void CreateTree(BitNode*& t, int n, int arr[]);
	void findtargetSum(BitNode* t, int targetSum);
	int sum = 0;
	int* arr = new int[1000];
	bool flag = false;
	int i = 1;
public:
	BinaryTree() :root(NULL) {}
	~BinaryTree() { delete root; };
	void CreatTree(int n, int arr[]);
	void findtargetSum(int targetSum);
	bool getflag() {
		return flag;
	}
};

void BinaryTree::CreateTree(BitNode*& t, int n, int arr[]) {//伪层序遍历构建二叉树
	t = new BitNode;
	queue <BitNode*> T;
	if (arr[0] != -1) {
		t->data = arr[0];
		T.push(t);
	}
	else {
		return;
	}
	int count = 1;
	while (count < n && !T.empty()) {
		BitNode* node = T.front();
		T.pop();
		if (arr[count] != -1) {
			node->lc = new BitNode(arr[count]);
			T.push(node->lc);
		}
		count++;
		if (count < n && arr[count] != -1) {
			node->rc = new BitNode(arr[count]);
			T.push(node->rc);
		}
		count++;
	}
}
void BinaryTree::CreatTree(int n, int arr[]) {
	CreateTree(root, n, arr);                
}

void BinaryTree::findtargetSum(BitNode* t, int targetSum) {
	if (t) {
		//保存当前节点值,存入路径
		arr[i] = t->data;
		i++;

		if (!t->lc && !t->rc) {
			//如果是叶子节点再进行判断值是否相等
			int totalSum = 0;
			for (int j = 0; j < i; j++) {
				totalSum += arr[j];
			}//用于求当前路径的值的和

			if (totalSum == targetSum) {
				flag = true;//用于判断是否有路径,如果flag不为true,则输出"Path not found"。
				for (int j = 0; j < i; j++) {
					if (arr[j] != 0) {
						cout << arr[j] << " ";
					}
				}//输出结果
				cout << endl;
			}
		}
		findtargetSum(t->lc, targetSum);
		findtargetSum(t->rc, targetSum);
		i--;//在遍历完左右子树之后,将路径尾部的结点删掉
	}
}

void BinaryTree::findtargetSum(int targetSum) {
	arr[0] = root->data;
	findtargetSum(root->lc, targetSum);//判断根的左子树
	i = 1; sum = 0;
	findtargetSum(root->rc, targetSum);//判断根的右子树
}

int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int targetSum;
		int n;
		cin >> targetSum;
		cin >> n;
		int* arr = new int[n + 1];
		for (int i = 0; i < n; i++) {
			cin >> arr[i];
		}
		BinaryTree tree;
		tree.CreatTree(n, arr);
		if (targetSum == 1 && n == 1 && arr[0] == 1) {
			cout << "1" << endl;
		}
		else {
			tree.findtargetSum(targetSum);
			if (tree.getflag() == false) {
				cout << "Path not found" << endl;
			}
			cout << endl;
		}
	}
}

到了这里,关于B-DS二叉树_输出所有目标路径的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包