在网上调查了二叉树寻找根节点的算法，有各种说法，在节点构造体中追加指向父节点的指针； 递归地查找父节点而不遍历树； 直接利用树的递归扫描，打印输出父节点……
向父节点添加指针的方法被认为不能很好地表达树的逻辑结构。 虽然树的结构(特别是二叉树的存储结构)已经成熟，接近于习俗，但重新添加指针后，有关二叉树的许多基本操作发生了变化，非常繁琐。 因此本论文直接使用树的递归扫描方式寻找树的根节点。 由于树的定义中体现了递归的特征，与树相关的操作大多可以有效地实现递归方法，代码可读性强。 另外，关于非递归的解法，本文中省略了说明，请读者自由。
*此外，本文仅提供一个想法，而不是万能模板。 具体问题需要根据实际情况来决定。
【问题】可以构建二叉排序树(也称为二叉搜索树)，使其成为空树。
二叉树定义：
1 .在左子树不为空情况下，左子树的所有键值都小于等于根节点的键值；
2 .如果右子树不为空，则右子树的所有键值都等于或大于根节点的键值；
3 .左、右子树本身也是二叉排序树。
这里，给出n个键值分别不同的节点。 请按顺序插入最初为空树的二叉树，并在每次插入成功时提示相应父节点的键值。 如果没有父亲节点，则输出-1。
输入：
第一行，一个数字n(n=100 )表示要插入的节点数。
第二行，n个互不相同的正整数表示依次插入节点的键值，这些值小于或等于10^8。 也就是说，限制在可以用int型数据类型表示的范围内。
输出：
输出共计n行，每次插入节点时，该节点对应的父节点的键值。 根节点的父节点默认为-1
代码采用数组二叉树方式存储树，具有两个优点： loc值可以获知节点总数，有利于节点遍历步数的控制； 输入值保存在对应的数组中，便于操作。
二叉树的记忆方法，期待着读者的指导。
# include stdio.hstruct node { int data； Node* lchild； Node* rchild； }树[ 101 ]； //数组二叉树int loc； //loc表示当前节点数Node* creat () /树节点tree [ loc ].lchild=tree [ loc ].rchild=null； 返回树[ loc ]； //返回指向新节点的指针} /*在一棵二叉树中依次插入节点，二叉排序树*/node*insert(node*t，int x ) if ) t==null ) { T=creat T-data=x； 返回t； }elseif(xt-data ) t-lchild=insert ) t-lchild，x )； }elseif(xt-data ) t-rchild=insert ) t-rchild，x )； } return T； (/)遍历一棵树找到每个节点的父节点- -首先遍历模型，注意遍历子节点的条件。 孩子不是空的(/voidfindparent(node*t，int x ) if (！ t )返回； if(T-Lchild！=nullt-lchild-data==x(/左边的孩子必须为空才能遍历。 否则，递归边界错误printf('%d的父节点是%dn”，x，T-data )； if(T-Rchild )！=NULL T-rchild-data==x ) printf('%d的父节点是%dn '，x，T-data )； if(t-lchild ) find parent (t-lchild，x )； if(t-rchild ) find parent (t-rchild，x )； 返回； (}int main ) ) { int n； wile(Scanf('%d '，n )！=eof(loc=0； node * t=空； //创建根节点for (inti=0； in； I ) { int x； scanf('%d '，x )； t=insert(t，x )； ///返回树的根节点(/*根节点的父节点的判断有点投机，要判断函数访问的节点是否是树的根节点，可以选择-1*/printf('%d的父节点为-1(n )，) //作者在这里直接跳过判断，但二叉排序树的第一个节点必须是根节点for(intI=1； iloc； I ) )//按顺序遍历树，找到根节点findparent(t，Tree[i].data )并输出。 } } return 0； }执行结果：