假设二叉树b采用二叉链存储结构存储,试设计一个算法,输出该二叉树中从根节点出发的第一条最长的路径长度,并输出此路径上各节点的值。并分析你设计的算法的时间复杂度和空间复杂度。
由于二叉树中最长路径一定是从根节点到某个叶子节点的路径,可以求出所有叶子节点到根节点的逆路径,通过比较长度得出最长路径,可以采用多种解法。算法中用形参maxpath[]数组存放最长路径,maxpathlen存放最长路径长度。对应的算法如下:voidMaxPath(BTNode*b,ElemTypemaxpath[],int&maxpathlen){//maxpathlen的初值为0structsnode{BTNode*node;//存放当前节点指针intparent;//存放双亲节点在队列中的位置}Qu[MaxSize];//定义非循环队列ElemTypepath[MaxSize];//存放一条路径intpathlen;//存放一条路径长度intfront,rear,p,i;//定义队头和队尾指针front=rear=-1;//置队列为空队列rear++;Qu[rear].node=b;//根节点指针进进队Qu[rear].parent=-1;//根节点没有双亲节点while(frontlchild==NULL&&b->rchild==NULL)//*b为叶子节点{p=front;pathlen=0;while(Qu.parent!=-1){path[pathlen]=Qu.node->data;pathlen++;p=Qu.parent;}path[pathlen]=Qu.node->data;pathlen++;if(pathlen>maxpathlen)//通过比较求最长路径{for(i=0;ilchild!=NULL)//左孩子节点进队{rear++;Qu[rear].node=b->lchild;Qu[rear].parent=front;}if(b->rchild!=NULL)//右孩子节点进队{rear++;Qu[rear].node=b->rchild;Qu[rear].parent=front;}}}本算法的时间复杂度为O(n),空间复杂度为O(n)。
举一反三
内容
- 0
假设二叉树中每个节点值为单个字符,采用二叉链存储结构存储。设计一个算法,输出二叉树b中第k层(根节点的层次为1)上的所有叶子节点。
- 1
假设二叉树中每个节点值为单个字符,采用二叉链存储结构存储。设计一个算法求二叉树b的最小枝长。所谓最小枝长是指的是根节点到最近叶子节点的路径长度。
- 2
假设二叉树中每个节点值为单个字符,采用二叉链存储结构存储。设计一个算法,求二叉树b中第k层上节点个数。
- 3
假设二叉树采用二叉链存储结构，[tex=0.429x0.929]r8lLiDb0KHTzu/2y/Au89w==[/tex]指向根节点, [tex=0.571x1.0]FGGpnaR8m8C48rN8O0c7aw==[/tex]所指的节点为任一给定节点设计一个算法,输出从根节点到 [tex=0.571x1.0]FGGpnaR8m8C48rN8O0c7aw==[/tex] 所指节点之间的路径。
- 4
【树和二叉树课后习题三算法设计】 （7）求任意二叉树中第一条最长的路径长度，并输出此路径上各结点的值。