《 Trees and Graphs》----CCI

《 Trees and Graphs》----CCI_Q4.6

本文参考该作者文章当作编程笔记：

作者：Hawstein
出处：http://hawstein.com/posts/ctci-solutions-contents.html

Q：

写程序在一棵二叉树中找到两个结点的第一个共同祖先。不允许存储额外的结点。注意：这里不特指二叉查找树。

思路：

首先，理解题义：不允许储存额外的结点。指的是，2叉树结点中除了左右孩子结点不应该有别的结点。

然后，根节点一定是两个结点的祖先。那么我们只要向下遍历根节点的孩子，直到找到符合条件的最后一个祖先节点即可。

CODE：

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 #define N 9    /*树的结点数*/
  4 #define key(A) (A)
  5 #define less(A,B) (A<B)
  6 typedef struct node
  7 {
  8     char item;
  9     struct node *l,*r;
 10 }tree_node;
 11 /*head为存储树的数组栈，g_anc为两个节点的共同祖先*/
 12 tree_node *head,*g_anc;
 13 int C;    /*C为数组下标*/
 14 /*初始化树*/
 15 void treeInit(tree_node **head)
 16 {
 17     *head=(tree_node *)calloc(N,sizeof(tree_node));
 18     g_anc=NULL;
 19     C=0;
 20 }
 21 /*将树的结点压入栈中*/
 22 tree_node * treePush(char item)
 23 {
 24     head[C].item=item;
 25     head[C].l=NULL;
 26     head[C].r=NULL;
 27     return head+C++;    /*返回该节点的地址，并使数组下标加1*/
 28 }
 29 /*插入树的节点,按照2叉查找树的形式*/
 30 void treeInsert(tree_node *node,char item)
 31 {
 32     if(node->item=='00')    /*假设字符为NUL时，该节点为空*/
 33     {
 34         treePush(item);        /*只有根节点在这里插入*/
 35         return;
 36     }
 37     if(less(item,node->item))
 38     {
 39         if(node->l==NULL)    /*如果该左孩子节点为空，说明插入到此节点*/
 40         {
 41             node->l=treePush(item);    /*将左孩子指向新节点的地址*/
 42             return;
 43         }
 44         treeInsert(node->l,item);
 45     }
 46     else
 47     {
 48         if(node->r==NULL)
 49         {
 50             node->r=treePush(item);
 51             return;
 52         }
 53         treeInsert(node->r,item);
 54     }
 55 }
 56 /*判断n1节点是n2节点的父亲或祖先*/
 57 int isFather(tree_node *n1,tree_node *n2)
 58 {
 59     if(n1==NULL || n2==NULL)return 0;
 60     if(n1==n2)return 1;
 61     /*左孩子是n2的父亲或祖先，返回；不然，看右孩子*/
 62     return isFather(n1->l,n2) || isFather(n1->r,n2);
 63 }
 64 /*根结点一定是两个孩子的祖先，在递归根节点的孩子，直到找到最后一个祖先*/
 65 void first_Ancestor(tree_node * head,tree_node *n1,tree_node *n2)
 66 {
 67     /*不包括n1和n2两个结点*/
 68     if(head==NULL || n1==NULL || n2==NULL || head==n1 || head==n2)
 69         return ;
 70     /*head结点必须同时是n1和n2结点的父亲或祖先*/
 71     if(isFather(head,n1) && isFather(head,n2))
 72     {
 73         g_anc=head;
 74         first_Ancestor(head->l,n1,n2);
 75         first_Ancestor(head->r,n1,n2);
 76     }
 77 }
 78 /*打印树*/
 79 void printNode(char c,int width)
 80 {
 81     while(width-->0)
 82         printf("#");
 83     printf("%c
",c);
 84 
 85 }
 86 /*前序遍历并打印树*/
 87 void preTraverse(tree_node *node,int width)
 88 {
 89     if(node==NULL)
 90     {
 91         printNode('*',width);    /* 叶子节点是左右孩子都是* */
 92         return;
 93     }
 94     printNode(node->item,width);
 95     preTraverse(node->l,width+1);
 96     preTraverse(node->r,width+1);
 97 }
 98 int main()
 99 {
100     treeInit(&head);
101     char s[]="DBACDEFYZ";
102     int i;
103     for(i=0;i<N;i++)
104         treeInsert(head,s[i]);
105     preTraverse(head,0);
106     first_Ancestor(head,head+6,head+7);
107     if(g_anc)
108         printf("%c and %c ancestor is %c
",
109                 head[6].item,head[7].item,g_anc->item);
110     free(head);
111     return 0;
112 }

缺点：

我们在判断祖先的两个函数中都用到了递归，如果树的节点多些，程序效率很低。