首页 > 数据结构 > 树形结构 > 找出二叉树中某个节点的所有祖先节点
2014
08-11

找出二叉树中某个节点的所有祖先节点

问题

对于一颗普通的二叉树和一个节点key,找出该节点的所有祖先节点。

例如树结构如下:给定的key为节点7,则应该打印 4,2,1.

              1
            /   \
          2      3
        /  \
      4     5
     /
    7

使用递归可以很容易的解决:

#include<iostream>
#include<stdio.h>
#include<stdlib.h>

using namespace std;
struct node
{
   int data;
   struct node* left;
   struct node* right;
};

bool printAncestors(struct node *root, int target)
{
  if (root == NULL)
     return false;

  if (root->data == target)
     return true;
  //子树可以找到,当前节点肯定为祖先节点
  if ( printAncestors(root->left, target) ||
       printAncestors(root->right, target) )
  {
    cout << root->data << " ";
    return true;
  }

  /* Else return false */
  return false;
}

/* 创建节点. */
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);
}
 int main()
{

  /* 创建下面的结构
              1
            /   \
          2      3
        /  \
      4     5
     /
    7
  */
  struct node *root = newnode(1);
  root->left        = newnode(2);
  root->right       = newnode(3);
  root->left->left  = newnode(4);
  root->left->right = newnode(5);
  root->left->left->left  = newnode(7);

  printAncestors(root, 7);

  return 0;
}

时间复杂度为O(n)

参考:http://www.geeksforgeeks.org/print-ancestors-of-a-given-node-in-binary-tree/


  1. #include <stdio.h>
    int main()
    {
    int n,p,t[100]={1};
    for(int i=1;i<100;i++)
    t =i;
    while(scanf("%d",&n)&&n!=0){
    if(n==1)
    printf("Printing order for 1 pages:nSheet 1, front: Blank, 1n");
    else {
    if(n%4) p=n/4+1;
    else p=n/4;
    int q=4*p;
    printf("Printing order for %d pages:n",n);
    for(int i=0;i<p;i++){
    printf("Sheet %d, front: ",i+1);
    if(q>n) {printf("Blank, %dn",t[2*i+1]);}
    else {printf("%d, %dn",q,t[2*i+1]);}
    q–;//打印表前
    printf("Sheet %d, back : ",i+1);
    if(q>n) {printf("%d, Blankn",t[2*i+2]);}
    else {printf("%d, %dn",t[2*i+2],q);}
    q–;//打印表后
    }
    }
    }
    return 0;
    }

  2. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的

  3. 您没有考虑 树的根节点是负数的情况, 若树的根节点是个很大的负数,那么就要考虑过不过另外一边子树了