编程论坛 » 数据结构与算法 » 求二叉树遍历的应用

tanlypan 发表于 2005-6-23 16:58

求二叉树遍历的应用

求 举例讨论二叉树前序遍历和中序遍历的应用 哪位哥哥姐姐能帮小弟下的，在线等啊~~

热情依然 发表于 2005-6-24 13:32

其实主要是应用在递归跟非递归转换那方面．

srgzyq 发表于 2008-5-14 09:35

/*第六题-先序、中序、后序遍历的递归算法*/
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

#define OK 1
#define ERROR 0
#define NULL 0
#define OVERFLOW -2

typedef int Status;
typedef char TElemType;

/*二叉树的二叉链表存储表示*/
typedef struct BiTNode{
        TElemType data;
        struct BiTNode *lchild, *rchild;        //左右孩子指针
}BiTNode, *BiTree;

/*建立二叉链表*/
Status CreateBiTree(BiTree &T){
        //按先序次序输入二叉树中结点值，空格表示空树
        //构造二叉链表表示的二叉树
        char ch;
        scanf("%c",&ch);
       
        //ch=getchar();
        if(ch==' ')
                T=NULL;
               
        else
        {
                if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
                T->data=ch;
                CreateBiTree(T->lchild);
                CreateBiTree(T->rchild);
        }
        return OK;
}

/*打印二叉树的内容*/
Status PrintElement(char ch)
{
        printf("%c",ch);

        return OK;
}

/*先序遍历二叉树，递归算法*/
Status PreOrderTraverse(BiTree T,Status(*PrintElement)(TElemType e))
{
        if(T)
        {
                if(PrintElement(T->data))
                        if(PreOrderTraverse(T->lchild,PrintElement))
                                if(PreOrderTraverse(T->rchild,PrintElement))
                                        return OK;
                return ERROR;
        }
        else return OK;
}
/*中序遍历二叉树，递归算法*/
Status InOrderTraverse(BiTree T,Status(*PrintElement)(TElemType e))
{
        if(T)
        {
                if(InOrderTraverse(T->lchild,PrintElement))
                        if(PrintElement(T->data))
                                if(InOrderTraverse(T->rchild,PrintElement))
                                        return OK;
                return ERROR;
        }
        else return OK;
}

/*后序遍历二叉树，递归算法*/
Status PostOrderTraverse(BiTree T,Status(*PrintElement)(TElemType e))
{
        if(T)
        {
                if(PostOrderTraverse(T->lchild,PrintElement))
                        if(PostOrderTraverse(T->rchild,PrintElement))
                                if(PrintElement(T->data))
                                        return OK;
                return ERROR;
        }
        else return OK;
}


int main()
{        BiTree T;
        printf("请输入二叉树:");
        printf("\n");
        CreateBiTree(T);
       
        printf("先序遍历:");
        printf("\n");
        PreOrderTraverse(T,PrintElement);
       
        printf("\n");
        printf("中序遍历:");
        printf("\n");
        InOrderTraverse(T,PrintElement);
       
        printf("\n");
        printf("后序遍历:");
        printf("\n");
        PostOrderTraverse(T,PrintElement);
        printf("\n");
        return 0;

}

张信哲 发表于 2008-5-16 20:22

有空帮我看看我空间里的那个遍历的问题吧。
用C++模板做的，有点问题，谢谢啊

moonlight锦 发表于 2008-5-17 22:49

HUFFMAN编码就是一个应用啊！

jiangzw625 发表于 2008-6-10 18:38

后缀表达式代码生成，计算等

狼族518 发表于 2008-11-19 16:02

请教c++编写哈夫曼树及编码程序

谢谢大家回帖我是新手，请多指教啊呵呵

狼族518 发表于 2008-11-19 16:08

不好意思刚才是想发新帖结果发成回复了，

查看完整版本: 求二叉树遍历的应用