6.41.c

来自「部分高校使用anyview编程测试数据结构习题,此代码为数据结构题集(c语言版)」· C语言 代码 · 共 41 行

6.41③ 编写递归算法，在二叉树中求位于先序序列中
第k个位置的结点的值。

要求实现下列函数：
TElemType PreOrder(BiTree bt, int k);
/* bt is the root node of a binary linked list, */
/* Preorder travel it and find the node whose   */
/* position number is k, and return its value.  */
/* if can't found it, then return '#'.          */

二叉链表类型定义：
typedef struct BiTNode {
    TElemType data;
    BiTNode  *lchild, *rchild;
} BiTNode, *BiTree;
void Search(BiTree bt,int k,char &count,char &temp);
TElemType PreOrder(BiTree bt, int k)
/* bt is the root node of a binary linked list, */
/* Preorder travel it and find the node whose   */
/* position number is k, and return its value.  */
/* if can't found it, then return '#'.          */
{  
   int count=0;
   char temp='#';
   Search(bt,k,count,temp);
   return temp;   
}
void Search(BiTree bt,int k,char &count,char &temp)
  {
   if(bt)
    {count++;
     if(count==k)
       {temp=bt->data;
        }
     else
       {Search(bt->lchild,k,count,temp);
        Search(bt->rchild,k,count,temp);
         }
     }
}