求:一棵完全二叉树中两个结点u和v是否具有祖先后代关系?
分析:
树的深度由根所在层从0开始,例如结点a的深度为0,结点c的深度为2。树总的深度为D。
解:
方法一:对节点进行二进制编码。若u结点是v结点的祖先,则v结点则必遗传u结点的标识。定义结点u的标识为其右边第一个非零位的左边所有位。例图中结点b的二进制为“0000 0100”,右边第一个为0的是第三位,则结点u的标识“0000 0”。
(1) 对完全二叉树按照中序遍历进行编码(从1开始),编码二进制如图所示(高四位全为0,省略)。
(2) 遍历树可得结点u、v的编码Cu、Cv以及他们的深度lu、lv;
(3) 假设lu
方法二:
(1) 非递归遍历树,中间结点保存在栈中;
(2) 当u(或v)需要进栈时:若v(或u)在栈中,则v(u)是u(v)的祖先;若不在且v(或u)未被访问,则接着遍历,若已经访问,则可判定结点u和v不存在祖先后代关系。
方法三:
(1) 对树按先序排序,则a,b,c,d,e,f,g,h,i,j,k,l,m,o的编码分别为1,2,3,4,5,6,7,8, 9,10,11,12,13,14;
(2) 将结点的所有祖先与它的排序作为它的编码。例:结点b的编码1.2,结点j的编码1.9.10;
(3) 若u(或v)的排名出现在v(或u)的编码中,则u(或v)是v(或u)的祖先;否则不具有祖先后代关系。
欢迎指正以及提出不同方法。