두 갈래 나무 중 어느 노드의 모든 조상 노드를 찾아내다

일반적인 두 갈래 나무와 한 노드 키에 대해 이 노드의 모든 조상 노드를 찾아라.
예를 들어 트리 구조는 다음과 같다. 주어진 키가 노드 7이면 4, 2, 1을 인쇄해야 한다.
       1        / \      2      3    / \  4     5  /7
귀속을 사용하면 쉽게 해결할 수 있습니다. 코드는 다음과 같습니다.
#include<iostream>

using namespace std;

struct Node
{
	int data;
	Node* lChild;
	Node* rChild;
	Node(int _data) { data = _data; lChild = rChild = nullptr; }
};

bool PrintAncestors(Node* _root, int target)
{
	if (!_root) return false;
	if (_root->data == target) return true;

	// , 
	if (PrintAncestors(_root->lChild, target) || PrintAncestors(_root->rChild, target))
	{
		cout << _root->data << " ";
		return true;
	}

	return false;
}

Node* NewNode(int _data)
{
	Node* node = new Node(_data);
	return node;
}

int main()
{
/* 

	      1
		 / \
	    2   3
	   / \
	  4   5
	 /
	7

*/

	Node* root = NewNode(1);
	root->lChild = NewNode(2);
	root->rChild = NewNode(3);
	root->lChild->lChild = NewNode(4);
	root->lChild->rChild = NewNode(5);
	root->lChild->lChild->lChild = NewNode(7);

	PrintAncestors(root, 7);// output: 4 2 1
	cout << endl;

	return 0;
}

제목:http://www.acmerblog.com/ancestors-of-a-given-node-6048.html

좋은 웹페이지 즐겨찾기