频道栏目
首页 > 程序开发 > 软件开发 > 其他 > 正文
数据结构例程——从根节点到每个叶子节点的路径之逆
2015-10-21 15:34:00         来源:迂者-贺利坚的专栏  
收藏   我要投稿

本文是数据结构基础系列(6):树和二叉树中第11课时二叉树遍历非递归算法和第12课时层次遍历算法的例程。

问题:设计算法输出从根节点到每个叶子节点的路径之逆。
解法1:利用二叉树后序遍历非递归算法中,每一个叶子节点出现时,栈中从栈顶到栈底,正好是叶子节点到根节点的逆序的性质编写。

[参考解答](btreee.h见算法库)

#include 
#include btree.h

void AllPath1(BTNode *b)
{
    BTNode *St[MaxSize];
    BTNode *p;
    int flag,i,top=-1;  //栈指针置初值
    if (b!=NULL)
    {
        do
        {
            while (b!=NULL) //将*b的所有左节点进栈
            {
                top++;
                St[top]=b;
                b=b->lchild;
            }
            p=NULL;
            flag=1;
            while (top!=-1 && flag)
            {
                b=St[top];       //取出当前的栈顶元素
                if (b->rchild==p)
                {
                    if (b->lchild==NULL && b->rchild==NULL)
                    {
                        //若为叶子节点,输出栈中所有节点值
                        for (i=top; i>0; i--)
                            printf(%c->,St[i]->data);
                        printf(%c
,St[0]->data);
                    }
                    top--;
                    p=b;            //p指向刚访问过的节点
                }
                else
                {
                    b=b->rchild;          //b指向右孩子节点
                    flag=0;
                }
            }
        }
        while (top!=-1);
        printf(
);
    }
}

int main()
{
    BTNode *b;
    CreateBTNode(b,A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I))));
    printf(二叉树b: );
    DispBTNode(b);
    printf(
);
    printf(从根节点到每个叶子节点的路径之逆:
);
    AllPath1(b);
    DestroyBTNode(b);
    return 0;
}

解法2:利用二叉树层次遍历算法的思路解决。

采用非环形顺序队列qu 层次遍历二叉树 将所有已访问过的节点指针进队,并在队列中保存双亲节点的位置。 当找到一个叶子节点时,在队列中通过双亲节点的位置输出根节点到该叶子节点的路径之逆。

[参考解答](btreee.h见算法库)

#include 
#include btree.h

void AllPath2(BTNode *b)
{
    struct snode
    {
        BTNode *node;   //存放当前节点指针
        int parent;     //存放双亲节点在队列中的位置
    } qu[MaxSize];      //定义非环形队列
    BTNode *q;
    int front,rear,p;   //定义队头和队尾指针
    front=rear=-1;      //置队列为空队列
    rear++;
    qu[rear].node=b;    //根节点指针进入队列
    qu[rear].parent=-1; //根节点没有双亲节点
    while (front!=rear) //队列不为空
    {
        front++;        //front是当前节点*q在qu中的位置
        q=qu[front].node;   //队头出队列,该节点指针仍在qu中
        if (q->lchild==NULL && q->rchild==NULL)
        {
            p=front;        //输出*q到根节点的路径序列
            while (qu[p].parent!=-1)
            {
                printf(%c->,qu[p].node->data);
                p=qu[p].parent;
            }
            printf(%c
,qu[p].node->data);
        }
        if (q->lchild!=NULL)    //*q节点有左孩子时将其进列
        {
            rear++;
            qu[rear].node=q->lchild;
            qu[rear].parent=front; //*q的双亲位置为front
        }
        if (q->rchild!=NULL)       //*q节点有右孩子时将其进列
        {
            rear++;
            qu[rear].node=q->rchild;
            qu[rear].parent=front; //*q的双亲位置为front
        }
    }
}

int main()
{
    BTNode *b;
    CreateBTNode(b,A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I))));
    printf(二叉树b: );
    DispBTNode(b);
    printf(
);
    printf(从根节点到每个叶子节点的路径之逆:
);
    AllPath2(b);
    DestroyBTNode(b);
    return 0;
}

注:在main函数中,创建的用于测试的二叉树如下——
这里写图片描述

 

点击复制链接 与好友分享!回本站首页
上一篇:数据结构之自建算法库——二叉树的链式存储及基本运算
下一篇:数据结构例程——二叉树的层次遍历算法
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站