1、遍历二叉树。
请输入一棵二叉树的扩展的前序序列，经过处理后生成一棵二叉树，然后对于该二叉树输出前序、中序和后序遍历序列。
答：
示例：先序建树:依次输入二叉树的结点号，孩子为空的时候输入空格:
输入：abd f  ce  先序中序后序遍历二叉树
输出：
先序遍历二叉树为:abdfce
中序遍历二叉树为:dfbaec
后序遍历二叉树为:fdbeca
代码如下：
#include<stdio.h>
#include<stdlib.h>
#define OVERFLOW -2
typedef struct BiTNode
{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
BiTree create(BiTree T)
{
char ch;
scanf("%c",&ch);
if(ch==' ')
T=NULL;
else
{
T=(BiTree)malloc(sizeof(BiTNode));
if(!T)
exit(OVERFLOW);
T->data=ch;
T->lchild=create(T->lchild);
T->rchild=create(T->rchild);
}
return T;
}
void PreOrderTraverse(BiTree T)
{
    if(T){
        printf("%c",T->data);
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->rchild);
    }
}
void InOrderTraverse(BiTree T)
{
    if(T){
        InOrderTraverse(T->lchild);
        printf("%c",T->data);
        InOrderTraverse(T->rchild);
    }
}
void PostOrderTraverse(BiTree T)
{
    if(T){
        PostOrderTraverse(T->lchild);
        PostOrderTraverse(T->rchild);
        printf("%c",T->data);
    }
}
void main()
{ BiTree T;
printf("先序建树:依次输入二叉树的结点号，孩子为空的时候输入空格:\n");
T=create(T);
printf("\n先序遍历二叉树为:");
PreOrderTraverse(T);
printf("\n中序遍历二叉树为:");
InOrderTraverse(T);
printf("\n后序遍历二叉树为:");
PostOrderTraverse(T);
}
2、按层次遍历二叉树。
答：
示例：先序建树:依次输入二叉树的结点号，孩子为空的时候输入空格:
输入：abd f  ce 
输出：层次遍历二叉树:abcdef
代码如下：（程序存为.cpp）
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef struct BiTNode
{
char data;
struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;
typedef struct QNode{
BiTree data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct {
QueuePtr front;//对头指针
QueuePtr rear;//队尾指针
}LinkQueue;
int InitQueue(LinkQueue &Q){
//构造一个空队列
Q.ar=(QueuePtr)malloc(sizeof(QNode));

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。