假设二叉树采用二叉链存储结构存储,设计一个算法,输出该二叉树中第一条最长的路径长度,并输出此路径上各节点的值。
解:采用基于先序递归算法的思路。用[tex=2.0x1.214]60QgBHhP1bYchH9IcCF6sg==[/tex]保存扫描到当前节点的路径, [tex=3.357x1.214]LnL+or6ZaYFHoiqM1kBkFg==[/tex]保存扫描到当前节点的路径长度, [tex=3.857x1.214]pdNwS51hKAMXGIR5OAPuAA==[/tex]保存最长的路径, [tex=5.214x1.214]6JWIb+Izvr1lhYQLLUauzQ==[/tex]保存最长路径长度。当[tex=0.429x1.0]JThLUuJ8WswSAPiYZWihWg==[/tex]为空时,表示当前的一个分支已扫描完毕,将[tex=3.357x1.214]LnL+or6ZaYFHoiqM1kBkFg==[/tex]与 [tex=3.857x1.214]pdNwS51hKAMXGIR5OAPuAA==[/tex]进行比较,将较长的路径及路径长度分别保存在[tex=3.857x1.214]pdNwS51hKAMXGIR5OAPuAA==[/tex]和 [tex=3.357x1.214]LnL+or6ZaYFHoiqM1kBkFg==[/tex]中。对应的算法如下:void LongPath( BTNode * b,ElemType path[ ] , int pathlen, ElemType longpath[ ] , int &longpathlen){ int i; if ( b== NUILL) { if (pathlen > longpathlen) //若当前路径更长,将路径保存在longpath中 { for ( i - pathlen1;i>- o;i--) longpath[ i]= path[ i]; longpathlen = pathlen; } } else { path[ pathlen] = b-> data; //将当前节点放入路径中 pathlen++ ; //路径长度增1 LongPath(b- > lchild, path, pathlen, longpath, longpathlen); //递归扫描左子树 LongPath(b- > rchild, path, pathlen, longpath,longpathlen) ; //递归扫描右子树 }}设计如下主函数:void main(){ BTNode * b; ElemType path[ MaxSize], longpath[ MaxSize]; int i, lonagpathlen = o; CreateBTNode( b, "A( B( D(,G)),C(E,F))") ; printf("括号表示法:"); DispBTNode(b) ; printf"\n"); LongPath( b, path,0, longpath, longpathlen) ; printf("第一条最长逆路径长度:8dn" , 1ongpathlen) ; printf("第一条最长逆路径:"); for ( i = longpathlen; i>= 0; i—- ) printf(" ÷ c " , longpath[ i]); printf( "\n");}程序执行结果如下:括号表示法:A(B( D(,c)),C(E.F))第一条最长逆路径长度:4第―条最长逆路径:GD B A
举一反三
内容
- 0
假设二叉树中每个节点值为单个字符,采用二叉链存储结构存储。设计一个算法,输出二叉树b中第k层(根节点的层次为1)上的所有叶子节点。
- 1
假设二叉树中每个节点值为单个字符,采用二叉链存储结构存储。设计一个算法求二叉树b的最小枝长。所谓最小枝长是指的是根节点到最近叶子节点的路径长度。
- 2
假设二叉树中每个节点值为单个字符,采用二叉链存储结构存储。设计一个算法,求二叉树b中第k层上节点个数。
- 3
【树和二叉树课后习题三算法设计】 （7）求任意二叉树中第一条最长的路径长度，并输出此路径上各结点的值。
- 4
假设二叉树采用二叉链存储结构,设计一个算法把树[tex=0.429x1.0]JThLUuJ8WswSAPiYZWihWg==[/tex]的左,右子树进行交换。要求不破坏原二叉树。