原文:
给定一棵二叉树和一个键，编写一个函数，打印给定二叉树中键的所有祖先。 例如，考虑下面的二叉树
1
/ \
2 3
/ \ / \
4 5 6 7
/ \ /
8 9 10
以下是上述树中不同的输入键及其祖先
input key list of ancestors
-------------------------
1
2 1
3 1
4 2 1
5 2 1
6 3 1
7 3 1
8 4 2 1
9 5 2 1
10 7 3 1
这个问题的递归解在讨论。 很明显，我们需要使用基于堆栈的二叉树迭代遍历。其思想是当我们到达具有给定键的节点时，所有祖先都在堆栈中。一旦我们拿到钥匙，我们要做的就是打印堆栈的内容。 当我们到达给定节点时，如何获取堆栈中的所有祖先？我们可以以后序方式遍历所有节点。如果我们仔细观察递归后序遍历，我们可以很容易地观察到，当对一个节点调用递归函数时，递归调用栈包含该节点的祖先。因此，我们的想法是进行迭代后置遍历，并在到达所需节点时停止遍历。 以下是上述办法的实施情况。
c
// c program to print all ancestors of a given key
#include
#include
// maximum stack size
#define max_size 100
// structure for a tree node
struct node
{
int data;
struct node *left, *right;
};
// structure for stack
struct stack
{
int size;
int top;
struct node* *array;
};
// a utility function to create a new tree node
struct node* newnode(int data)
{
struct node* node = (struct node*) malloc(sizeof(struct node));
node->data = data;
node->left = node->right = null;
return node;
}
// a utility function to create a stack of given size
struct stack* createstack(int size)
{
struct stack* stack = (struct stack*) malloc(sizeof(struct stack));
stack->size = size;
stack->top = -1;
stack->array = (struct node**) malloc(stack->size * sizeof(struct node*));
return stack;
}
// basic operations of stack
int isfull(struct stack* stack)
{
return ((stack->top 1) == stack->size);
}
int isempty(struct stack* stack)
{
return stack->top == -1;
}
void push(struct stack* stack, struct node* node)
{
if (isfull(stack))
return;
stack->array[ stack->top] = node;
}
struct node* pop(struct stack* stack)
{
if (isempty(stack))
return null;
return stack->array[stack->top--];
}
struct node* peek(struct stack* stack)
{
if (isempty(stack))
return null;
return stack->array[stack->top];
}
// iterative function to print all ancestors of a given key
void printancestors(struct node *root, int key)
{
if (root == null) return;
// create a stack to hold ancestors
struct stack* stack = createstack(max_size);
// traverse the complete tree in postorder way till we find the key
while (1)
{
// traverse the left side. while traversing, push the nodes into
// the stack so that their right subtrees can be traversed later
while (root && root->data != key)
{
push(stack, root); // push current node
root = root->left; // move to next node
}
// if the node whose ancestors are to be printed is found,
// then break the while loop.
if (root && root->data == key)
break;
// check if right sub-tree exists for the node at top
// if not then pop that node because we don't need this
// node any more.
if (peek(stack)->right == null)
{
root = pop(stack);
// if the popped node is right child of top, then remove the top
// as well. left child of the top must have processed before.
// consider the following tree for example and key = 3. if we
// remove the following loop, the program will go in an
// infinite loop after reaching 5.
// 1
// / \
// 2 3
// \
// 4
// \
// 5
while (!isempty(stack) && peek(stack)->right == root)
root = pop(stack);
}
// if stack is not empty then simply set the root as right child
// of top and start traversing right sub-tree.
root = isempty(stack)? null: peek(stack)->right;
}
// if stack is not empty, print contents of stack
// here assumption is that the key is there in tree
while (!isempty(stack))
printf("%d ", pop(stack)->data);
}
// driver program to test above functions
int main()
{
// let us construct a binary tree
struct node* root = newnode(1);
root->left = newnode(2);
root->right = newnode(3);
root->left->left = newnode(4);
root->left->right = newnode(5);
root->right->left = newnode(6);
root->right->right = newnode(7);
root->left->left->left = newnode(8);
root->left->right->right = newnode(9);
root->right->right->left = newnode(10);
printf("following are all keys and their ancestors\n");
for (int key = 1; key <= 10; key )
{
printf("%d: ", key);
printancestors(root, key);
printf("\n");
}
getchar();
return 0;
}
c
// c program to print all ancestors of a given key
#include
using namespace std;
// structure for a tree node
struct node
{
int data;
struct node *left, *right;
};
// a utility function to create a new tree node
struct node* newnode(int data)
{
struct node* node = (struct node*) malloc(sizeof(struct node));
node->data = data;
node->left = node->right = null;
return node;
}
// iterative function to print all ancestors of a given key
void printancestors(struct node *root, int key)
{
if (root == null) return;
// create a stack to hold ancestors
stack st;
// traverse the complete tree in postorder way till we find the key
while (1)
{
// traverse the left side. while traversing, push the nodes into
// the stack so that their right subtrees can be traversed later
while (root && root->data != key)
{
st.push(root); // push current node
root = root->left; // move to next node
}
// if the node whose ancestors are to be printed is found,
// then break the while loop.
if (root && root->data == key)
break;
// check if right sub-tree exists for the node at top
// if not then pop that node because we don't need this
// node any more.
if (st.top()->right == null)
{
root = st.top();
st.pop();
// if the popped node is right child of top, then remove the top
// as well. left child of the top must have processed before.
while (!st.empty() && st.top()->right == root)
{root = st.top();
st.pop();
}
}
// if stack is not empty then simply set the root as right child
// of top and start traversing right sub-tree.
root = st.empty()? null: st.top()->right;
}
// if stack is not empty, print contents of stack
// here assumption is that the key is there in tree
while (!st.empty())
{
cout<data<<" ";
st.pop();
}
}
// driver program to test above functions
int main()
{
// let us construct a binary tree
struct node* root = newnode(1);
root->left = newnode(2);
root->right = newnode(3);
root->left->left = newnode(4);
root->left->right = newnode(5);
root->right->left = newnode(6);
root->right->right = newnode(7);
root->left->left->left = newnode(8);
root->left->right->right = newnode(9);
root->right->right->left = newnode(10);
cout<<"following are all keys and their ancestors"<
java 语言(一种计算机语言，尤用于创建网站)
// java program to print all ancestors of a given key
import java.util.stack;
public class gfg
{
// class for a tree node
static class node
{
int data;
node left,right;
// constructor to create node
// left and right are by default null
node(int data)
{
this.data = data;
}
}
// iterative function to print all ancestors of a given key
static void printancestors(node root,int key)
{
if(root == null)
return;
// create a stack to hold ancestors
stack st = new stack<>();
// traverse the complete tree in postorder way till we find the key
while(true)
{
// traverse the left side. while traversing, push the nodes into
// the stack so that their right subtrees can be traversed later
while(root != null && root.data != key)
{
st.push(root); // push current node
root = root.left; // move to next node
}
// if the node whose ancestors are to be printed is found,
// then break the while loop.
if(root != null && root.data == key)
break;
// check if right sub-tree exists for the node at top
// if not then pop that node because we don't need this
// node any more.
if(st.peek().right == null)
{
root =st.peek();
st.pop();
// if the popped node is right child of top, then remove the top
// as well. left child of the top must have processed before.
while( st.empty() == false && st.peek().right == root)
{
root = st.peek();
st.pop();
}
}
// if stack is not empty then simply set the root as right child
// of top and start traversing right sub-tree.
root = st.empty() ? null : st.peek().right;
}
// if stack is not empty, print contents of stack
// here assumption is that the key is there in tree
while( !st.empty() )
{
system.out.print(st.peek().data " ");
st.pop();
}
}
// driver program to test above functions
public static void main(string[] args)
{
// let us construct a binary tree
node root = new node(1);
root.left = new node(2);
root.right = new node(3);
root.left.left = new node(4);
root.left.right = new node(5);
root.right.left = new node(6);
root.right.right = new node(7);
root.left.left.left = new node(8);
root.left.right.right = new node(9);
root.right.right.left = new node(10);
system.out.println("following are all keys and their ancestors");
for(int key = 1;key <= 10;key )
{
system.out.print(key ": ");
printancestors(root, key);
system.out.println();
}
}
}
//this code is contributed by sumit ghosh
python 3
# python3 program to print all ancestors of a given key
# class for a tree node
class node:
def __init__(self, data):
self.data = data
self.left = none
self.right = none
# iterative function to print all ancestors of a given key
def printancestors(root, key):
if(root == none):
return;
# create a stack to hold ancestors
st = []
# traverse the complete tree in postorder way till we find the key
while(true):
# traverse the left side. while traversing, append the nodes into
# the stack so that their right subtrees can be traversed later
while(root != none and root.data != key):
st.append(root); # append current node
root = root.left; # move to next node
# if the node whose ancestors are to be printed is found,
# then break the while loop.
if(root != none and root.data == key):
break;
# check if right sub-tree exists for the node at top
# if not then pop that node because we don't need this
# node any more.
if(st[-1].right == none):
root = st[-1];
st.pop();
# if the popped node is right child of top, then remove the top
# as well. left child of the top must have processed before.
while(len(st) != 0 and st[-1].right == root):
root = st[-1];
st.pop();
# if stack is not empty then simply set the root as right child
# of top and start traversing right sub-tree.
root = none if len(st) == 0 else st[-1].right;
# if stack is not empty, print contents of stack
# here assumption is that the key is there in tree
while(len(st) != 0):
print(st[-1].data, end = " ")
st.pop();
# driver program to test above functions
if __name__=='__main__':
# let us construct a binary tree
root = node(1);
root.left = node(2);
root.right = node(3);
root.left.left = node(4);
root.left.right = node(5);
root.right.left = node(6);
root.right.right = node(7);
root.left.left.left = node(8);
root.left.right.right = node(9);
root.right.right.left = node(10);
print("following are all keys and their ancestors");
for key in range(1, 11):
print(key, end = ": ");
printancestors(root, key);
print();
# this code is contributed by rutvik_56.
c
// c# program to print all ancestors
// of a given key
using system;
using system.collections.generic;
class gfg
{
// class for a tree node
public class node
{
public int data;
public node left, right;
// constructor to create node
// left and right are by default null
public node(int data)
{
this.data = data;
}
}
// iterative function to print
// all ancestors of a given key
public static void printancestors(node root,
int key)
{
if (root == null)
{
return;
}
// create a stack to hold ancestors
stack st = new stack();
// traverse the complete tree in
// postorder way till we find the key
while (true)
{
// traverse the left side. while
// traversing, push the nodes into
// the stack so that their right
// subtrees can be traversed later
while (root != null && root.data != key)
{
st.push(root); // push current node
root = root.left; // move to next node
}
// if the node whose ancestors
// are to be printed is found,
// then break the while loop.
if (root != null && root.data == key)
{
break;
}
// check if right sub-tree exists for
// the node at top. if not then pop
// that node because we don't need
// this node any more.
if (st.peek().right == null)
{
root = st.peek();
st.pop();
// if the popped node is right child
// of top, then remove the top as well.
// left child of the top must have
// processed before.
while (st.count > 0 &&
st.peek().right == root)
{
root = st.peek();
st.pop();
}
}
// if stack is not empty then simply
// set the root as right child of top
// and start traversing right sub-tree.
root = st.count == 0 ?
null : st.peek().right;
}
// if stack is not empty, print contents
// of stack. here assumption is that the
// key is there in tree
while (st.count > 0)
{
console.write(st.peek().data " ");
st.pop();
}
}
// driver code
public static void main(string[] args)
{
// let us construct a binary tree
node root = new node(1);
root.left = new node(2);
root.right = new node(3);
root.left.left = new node(4);
root.left.right = new node(5);
root.right.left = new node(6);
root.right.right = new node(7);
root.left.left.left = new node(8);
root.left.right.right = new node(9);
root.right.right.left = new node(10);
console.writeline("following are all keys "
"and their ancestors");
for (int key = 1; key <= 10; key )
{
console.write(key ": ");
printancestors(root, key);
console.writeline();
}
}
}
// this code is contributed by shrikant13
java 描述语言
输出:
following are all keys and their ancestors
1:
2: 1
3: 1
4: 2 1
5: 2 1
6: 3 1
7: 3 1
8: 4 2 1
9: 5 2 1
10: 7 3 1
练习
注意，上面的pg电子试玩链接的解决方案假设给定的键存在于给定的二叉树中。如果密钥不存在，它可能会进入无限循环。扩展上述pg电子试玩链接的解决方案，即使密钥不在树中也能工作。
本文由 控制。如果你发现任何不正确的地方，或者你想分享更多关于上面讨论的话题的信息，请写评论。
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
