算法题： 设二叉树的存储结构采用二叉链表，并假设二叉树中结点的值互不相同。编写递归算法：在root为根的二叉树下，判断值为x的结点所在的层次。假设根结点所在层次为1，它的孩子结点层次为2，以此类推。如果没有找到值为x的结点，则返回0。

试编写算法交换以二叉链表做存储结构的二叉树中所有结点的左、右子树。

已知二叉树T采用二叉链表结构存储，每个结点有三个字段：data，Lchild和Rchild。设计算法求出T的顺序存储结构A[1..n]，并给出初始调用形式。要求：如某位置为空，将其置为null；如超出下标范围n则报错；最后返回实际的最大下标。如图所示为，l=15时一个二叉树及所对应的输出结果示例(空缺表示null)。输出结果(表结构的值和最大下标)：maxsub=12(最大下标为12)。【合肥工业大学2001五、5(8分)】

假设二叉树采用二叉链表存储结构存储，试设计一个算法，求出该二叉树中第一条最长的路径长度以及此路径上各结点的值。

设二叉树采用二叉链表作为存储结构。试用类Pascal语言实现按前序遍历顺序输出二又树中结点的非递归算法。要求定义所用结构。设栈已经定义：inits(S)，empty(S)，push(S，P)，pop(S)，top(S)分别为栈初始化，判栈空，入栈，出栈，看栈顶等操作。【北京工业大学1997二、1(10分)】

以二叉链表为存储结构，分别写出求二叉树结点总数及叶子总数的算法。

设二叉树以二叉链表方式存储，试完成下列问题的递归算法。 设二叉树结点和二叉树结构体定义如下： typedef struct btnode { ElemType element; struct btnode* lchild, *rchild; }BTNode; typedef struct binarytree{ BTNode* root; }BinaryTree; （1）求一棵二叉树的高度； int Depth(BTNode *p) { int lh, rh; if (!p) return 0; lh = ______________; rh = _____________; if (lh > rh) return _________; else return ________; } int DepthofBT(BinaryTree Bt) { return ___________; } （2）求一棵二叉树中的结点个数； int Size(BTNode * p) { if (!p) return _____ ; else return Size(p->lchild)+______________+1; } int SizeofBT(BinaryTree Bt) { return ______________); } （3）交换一棵二叉树中每个结点的左、右子树。 void exchange ( BTNode * p) { if(!p) return; if ( p->lchild != NULL || p->rchild != NULL ) { temp = p->lchild; p->lchild = ____________; p->rchild = temp; exchange (___________ ); exchange ( p->rchild ); } } void exchange(BinaryTree *bt) { ____________________; }

某张氏家族的族谱以二叉树来表示，如图所示，以二叉链表作为存储结构，编写一算法，在家谱中查找是否有张三这个人。

  

  解题思路：本题就是在一个二叉链表中查找指定的结点x的过程。可以利用二叉树的任意一种遍历方法进行查找。这里利用先序遍历方法，首先判断当前结点是否是要查找的结点，如果是，则查找成功，返回结点的地址；如果不是，则分别到它的左子树和右子树中进行查找。