1．请根据用户输入的“扩展的先序遍历序列” (用小圆点表示空子树)，建立以二叉链表方式存储的二叉树，然后写出后序遍历该二叉树的非递归算法。
方法一：
#include <stdlib.h>
#include <stdio.h>
#define MAX_TREE_SIZE  100
typedef struct BiTNode {
    char data;
    struct BiTNode * lchild;
    struct BiTNode * rchild;
}BiTNode, *BiTree;
//函数声明
void Print(BiTree *root);
void Selection(int sel,BiTree *root);
void ReadExPreOrder(BiTree *root);
void PrintExPreOrder(BiTree root);
void PostOrderTraverse(BiTree T);
//主函数
void main()    {
   
    BiTree root=NULL; //初始化根结点
   
    Print(&root);
    while (true)    {
        printf("\nPress enter .");
        getchar();
        getchar();
        system("cls");
        Print(&root);
    }
}
void Print(BiTree *root)    {
  //提示
    int sel;
    printf("使用说明:本程序可实现二叉链表方式存储的二叉树，输入为扩展先序遍历序列.\n");
    printf("---------------------\n");
    printf("1.输入扩展先序遍历序列并建立对应的二叉树.\n");
    printf("2.打印当前的二叉树的扩展先序遍历序列.\n");
    printf("3.后序遍历当前的二叉树并打印遍历序列.\n");
    printf("4.按其它任意键退出.\n");
    printf("---------------------\n");
    printf("请选择你要的操作:");
    scanf("%d", &sel);
    getchar();
    Selection(sel, root);
}
void Selection(int sel, BiTree *root)    {
先序中序后序遍历二叉树      //根据用户输入决定下一步骤
    switch (sel) {
        case 1: ReadExPreOrder(root);
                break;
        case 2: PrintExPreOrder(*root);
                break;
        case 3: PostOrderTraverse(*root);
                break;
        default: exit(0);
    }
}
void ReadExPreOrder(BiTree *root)    {
//先序遍历二叉树，root为指向二叉树（或某一子树）根结点的指针
    char ch;
    ch = getchar();
    if (ch == '.')
        *root = NULL;
    else {
        (*root) = (BiTree)malloc(sizeof(BiTNode));
        (*root)->data = ch;
        ReadExPreOrder(&((*root)->lchild));
        ReadExPreOrder(&((*root)->rchild));
    }
}
void PrintExPreOrder(BiTree root)    {
    char ch;
    if (root!=NULL)    {
        ch = root->data;
        printf("%c", ch);
        PrintExPreOrder(root->lchild);
        PrintExPreOrder(root->rchild);
    }
    else
        printf(".");
}
void PostOrderTraverse(BiTree T) {
    BiTree stack[MAX_TREE_SIZE], p;
    int tag[MAX_TREE_SIZE],top=0;
    p = T;
    while(p || top != 0)    {
        while(p)        {
            top++;
            stack[top]=p;
            tag[top]=0;
            p=p->lchild;//从根开始，左结点依次入栈
        }
        if(top> 0)  {
          if(tag[top]==1){//表示是从该结点的右子树返回，则访问该结//点
                p=stack[top];
                printf("%c", p->data);
                top--;
                p=NULL;//将p指向NULL,则下次进入while循环时，不做左子//树入栈操作
            }
            else{ //表明是从该结点左子树返回，应继续访问其右子树
                p=stack[top];
                if(top> 0)  {
                    p=p->rchild;
                    tag[top]=1;  //表明该结点的右子树已访问
                }
            } //end of else
        } //end of if
    }//end of while
}
方法二（顺序栈）：
#include<iostream>
using namespace std;
typedef struct node
{
char ch;
struct node *lchild;
struct node *rchild;
}node;
typedef struct binarytree
{
node *head;//指向根结点
}bt;
int n=0;
void ini(bt * &b)
{
b =new bt;
b->head=NULL;
}
void precreate(node * &t)//先序递归建立二叉树
{
    cout<<"\n\n请输入结点数据，以'.'代表空:";
char c;
cin>>c;
if(c=='.') t=NULL;
else
{
n++;
t=new node;
t->ch=c;
precreate(t->lchild);
precreate(t->rchild);
}

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