UC知道Find in a tree
来源：百度知道 编辑：UC知道 时间：2024/05/22 20:44:18
Given the list of edges of a rooted tree T and a vertex S in the tree, find the parent, children, ancestors, descendants of S.
Input
The first line is an integer N (N <= 100), the number of vertex in this tree. Next N-1 line will consist of a sequence of edge descriptions. Each edge description will consist of a pair of integers; the first integer identifies the node from which the edge begins, and the second integer identifies the node to which the edge is directed. Node numbers will always be greater than zero. The last line is an integer S. (0 < S <= N)
Output
Output will consist four lines: the parent, children, ancestors and descendants of S. the number of each line must be list in ascend orders. If no integer appearance in a line, you just output -1 in this line.
Sample Input
10
1 2
1 3
2 4
4 5
5 6
3 7
3 8
7 9
7 10
3
Sample Output
#ifndef BINNODE_H
#define BINNODE_H
#include <math.h>
/********************************************************\
template node class for binary tree
\********************************************************/
template <typename dataType> class binNode
{
private:
dataType nodeData;
binNode<dataType> *left, *right;
void deleteNode(binNode<dataType> **root) {
if (left == NULL && right == NULL) {
// leaf node
*root = NULL;
} else if (left == NULL) {
// right branch but no left branch
*root = right;
} else if (right == NULL) {
// left branch but no right branch
*root = left;
} else {
// has left and right branch
binNode<dataType> *temp = right;