题目

C++,判断二叉树中某结点是其双亲结点的左孩子还是右孩子
以先序的方式创建一棵二叉树,结点为字符型.给定某结点的值,判断它是其双亲结点的左孩子还是右孩子,如果二叉树无该结点,输出“none”,如果该结点是二叉树的根,输出“root”.
--------------------------------------------------------------------------------
输入样例:
abdh###e#i##cf##gj###
d
--------------------------------------------------------------------------------
输出样例:
left
--------------------------------------------------------------------------------
输入描述:
第一行按先序输入扩展二叉树的先序遍历序列第二行输入一个结点的值
--------------------------------------------------------------------------------
输出描述:
输出该结点是其双亲结点的左孩子还是右孩子,如果是左孩子输出“left”,如果是右孩子输出“right”,如果该结点不存在,输出“none”,如果该结点为二叉树的根,输出“root”.
对了我需要具体的代码,

提问时间：2021-02-03

答案

你的题目出错了.前序输入的二叉树,或者你的是一个后序全二叉树
输入样例:
abdh###e#i##cf##gj###
d
--------------------------------------------------------------------------------
输出样例:
输出应该是right吧
其实是个完全二叉树的求下标算法.
叶子结点只可能在最大的两层上出现,对任意结点,若其右分支下的子孙最大层次为L,则其左分支下的子孙的最大层次必为L 或 L+1； 出于简便起见,完全二叉树通常采用数组而不是链表存储,其存储结构如下: var tree:array[1..n]of longint;{n:integer;n>=1} 对于tree,有如下特点： （1）若i为奇数且i>1,那么tree的左兄弟为tree[i-1]； （2）若i为偶数且i1,tree的双亲为tree[i div 2]； （4）若2*i