Find Common Ancestor

王朝other·作者佚名  2006-01-10
窄屏简体版  字體: |||超大  

Problem: find the common ancestor of two nodes in a tree

Given a "tree" pointer pointing to the root node of a tree and the other two pointers to two nodes in the tree. You are expected to write a C++ subroutine to find the common ancestor of the two nodes. In any unexpected condition, your code should return null pointer and avoid crashing.

For example, if the tree is like below, B is the common ancestor of E and G; A is the common ancestor of H and F; D is the common ancestor of D and G.

You are allowed to use recursion but as few as possible. You are NOT allowed to use STL. Please follow the type definitions shown below:

//tree node type

typedef struct _Node

...{

char value;

struct _Node* left;

struct _Node* right;

}Node;

class CommonNodeFinder

...{

//add any auxiliary code here as you wish.

public:

inline Node* FindCommonAncestor(Node* tree, Node* node_1, Node* node_2)

...{

//your code here.

}

}

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有 導航