西交《数据结构》拓展资源（六）

易百网

西交《数据结构》拓展资源（六）
第六章 树与二叉树
两个二叉树相关的常见题目
前记：这一章课件里主要讲了树和二叉树的属性和一些常用的操作。下面针对二叉树的遍历举一个具体的例子，这个题目在等级考试或者面试中都经常出现，大家多思考一下。
一        题目描述：已知二叉树前序遍历和中序遍历分别为：ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为？
答案：DGEBHFCA
解题思路：
先序遍历的第一个结点是根结点，所以A是根；
然后在中序遍历中找到A，（DBGE）A（CHF）；
由中序遍历的定义知（DBGE）是左子树的中序遍历，（CHF）是右子树的中序遍历。
然后在先序遍历中把左子树和右子树划开，A（BDEG）（CHF），所以B是左子树根，C是右子树根。
然后继续在中序遍历中找到B和C，（（D）B（GE））A（C（HF））。
对于DBEG，B是根，D是左子树，EG是右子树的中序遍历，对于CHF，C是根，HF是右子树的中序遍历。因为仍然有没划分完的部分，所以继续看先序。
对于BDEG，B是根已知，D是整个左子树已知，所以EG是右子树的先序遍历，E是右根，再对照中序可知G是E的左子树，CHF同理。所以树的结构是A（B（D，E（G，）），C（，F（H，）））
把它画成图，后序遍历就是DGEBHFCA总之先序序列是用来确定根结点，中序序列是用来划分出左右子树。二        题目：建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果
[基本要求]
从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），并采用递归算法对其进行遍历（先序、中序、后序），将遍历结果打印输出。
[测试数据]
ABC  DE G  F   （其中 表示空格字符）
则输出结果为 先序：ABCDEGF
中序：CBEGDFA
后序：CGBFDBA
C语言描述的方法：
//示例的是先序遍历，其它的可以在这个基础上改。
#include<stdio.h>
#include<stdlib.h>
typedef struct tnode
{        char data;
        struct tnode *lchild;
        struct tnode *rchild;
}tnode;
tnode *Tree_creat(tnode *t)
{        char ch;
        ch=getchar();
        if(ch==' ')
                t=NULL;
        else
        {
                if(!(t=(tnode *)malloc(sizeof(tnode))))
                        printf("Error!");
                t->data=ch;//printf("[%c]",t->data);
                t->lchild=Tree_creat(t->lchild);
                t->rchild=Tree_creat(t->rchild);
        }
        return t;
}void preorder(tnode *t)
{        if(t!=NULL)
        {        printf("%c ",t->data);
                preorder(t->lchild);
                preorder(t->rchild);
        }
}void main()
{
        tnode *t=NULL;
        t=Tree_creat(t);
        preorder(t);
}
本内容由易百网整理发布
网址 www.openhelp100.com
QQ 515224986