kingoffreeze
BAN USERI think the node structure in not clear.
If there is a parent pointer exist, then using a stack for DFS and print the path after traversing reaches the leaf.
If there is only the pointer to the child, then we need a stack with pair<node, level> for document the level of tree node( which could be easily done in recursive form ), and a array for document the path.
if the traverse reaches the leaf, by assign the node the path[level], and print path
struct Node {
int data;
vector<Node*> childList;
};
void printTreeLeafPath(Node *root) {
// variable
struct Node *currNode;
int currlv;
stack< pair<struct Node*,int> > DFS_stack;
vector<int> path;
// initialize
currNode = root;
currlv = 1;
DFS_stack.push(pair<struct Node*,int>(currNode,currlv));
while(!DFS_stack.empty()) {
// access stack
currNode = DFS_stack.top().first;
currlv = DFS_stack.top().second;
DFS_stack.pop();
// erase the path
if(currlv <= (int)path.size())
path.erase(path.begin()+currlv-1,path.begin()+path.size());
path.push_back(currNode->data);
if(!currNode->childList.empty()){
for( vector<Node*>::iterator child_iter = currNode->childList.begin();
child_iter != currNode->childList.end(); child_iter++ )
DFS_stack.push(pair<Node *,int>(*child_iter, currlv+1));
}
else {
for(vector<int>::iterator path_iter = path.begin();
path_iter != path.end(); path_iter++)
cout << *path_iter << ",";
cout << endl;
}
}
}
I modify shondik's code, the entire idea is correct, just need a few adjustment
#include<stdio.h>
#include<stdlib.h>
struct node {
struct node *left;
struct node *right;
int data;
};
struct node *newnode(int data)
{
struct node *node=(struct node *)malloc(sizeof(struct node));
node->data=data;
node->left=NULL;
node->right=NULL;
return node;
}
void printBoundaryLeft(struct node *root)
{
if(root==NULL)
return;
if(root->left)
{
printf("%d ",root->data);
printBoundaryLeft(root->left);
}
}
void printBoundaryLeaf(struct node *root)
{
if(root==NULL)
return ;
else
{
printBoundaryLeaf(root->left);
if(root->left==NULL||root->right==NULL)
printf("%d ",root->data);
printBoundaryLeaf(root->right);
}
}
void printBoundaryRight(struct node *root)
{
if(root==NULL)
return;
if(root->right)
{
printBoundaryRight(root->right);
printf("%d ",root->data);
}
}
void printBoundary(struct node *root)
{
if(root)
{
printf("%d ",root->data);
printBoundaryLeft(root->left);
printBoundaryLeaf(root);
printBoundaryRight(root->right);
}
}
int main()
{
struct node *root=newnode(100);
root->left=newnode(50);
root->right=newnode(150);
root->left->right=newnode(57);
root->left->right->right=newnode(60);
root->left->left=newnode(24);
root->right->left=newnode(130);
root->right->left->right=newnode(132);
root->left->left->left=newnode(12);
root->left->left->right=newnode(30);
printBoundary(root);
return 0;
}
is there a name for this computation? seems like a encryption skill or something... anyone knows?
- kingoffreeze July 04, 2012