二叉树遍历输出（编写程序 实现对建立的二叉树进行后序遍历，并输出遍历结果二叉树用二叉链表存储结构存储）

本文目录

• 编写程序 实现对建立的二叉树进行后序遍历，并输出遍历结果二叉树用二叉链表存储结构存储
• 前序遍历顺序输出二叉树前n层所有结点
• 二叉树的遍历，为什么输出为null
• c语言 二叉树的遍历

编写程序 实现对建立的二叉树进行后序遍历，并输出遍历结果二叉树用二叉链表存储结构存储

(1)、二叉树的链表形式的建立；
(2)、用递归方式写出二叉树的先序、中序、后序三种遍历方法。
(3)、用非递归方式写出二叉树的中序遍历程序。
#include《stdio.h》
#define MAXSIZE 100
typedef struct BiTNode
{
char data;
struct BiTNode *lchild, *rchild;
}BiTNode,*BiTree;
BiTree CreateBiTree()
{
BiTree T;
char ch=getchar();
if(ch==’#’)
T=NULL;
else
{
T=(BiTNode *)malloc(sizeof(BiTNode));
T-》data=ch;
T-》lchild=CreateBiTree();
T-》rchild=CreateBiTree();
}
return T;
} //递归生成二叉树，用#代表空子树
void preorder(BiTree t)
{
if(t)
{
printf("%c ",t-》data);
preorder(t-》lchild);
preorder(t-》rchild);
}
} //递归先序遍历
void Inorder(BiTree T)
{
if(T)
{
Inorder(T-》lchild);
printf("%c ",T-》data);
Inorder(T-》rchild);
}
}
//递归中序遍历
void postorder(BiTree t)
{
if(t)
{
preorder(t-》lchild);
preorder(t-》rchild);
printf("%c ",t-》data);
}
} //递归后序遍历
void NInorder(BiTree T)
{
BiTree stack;
BiTree p=T;
int top=-1;
while(p||top!=-1)
{
if(p)
{
top++;
stack=p;
p=p-》lchild;
}
else
{
p=stack;
top--;
printf("%c ",p-》data);
p=p-》rchild;
}
}
} //非递归中序遍历
main()
{
BiTree T;
printf("please input the tree: ");
T=CreateBiTree();
printf("\n");
getch();
printf("the tree after preorder is: ");
preorder(T);
printf("\n");
getch();
printf("the tree after ineorder is: ");
Inorder(T);
printf("\n");
getch();
printf("the tree after postorder is: ");
postorder(T) ;
printf("\n");
getch();
printf("the tree after noinorder is: ");
NInorder(T) ;
printf("\n");
getch();
}

前序遍历顺序输出二叉树前n层所有结点

输入先序扩展序列:
abd##e##c##
对应的先序序列:a b d e c
对应的二叉树:
          a
       /      \
      b        c
    /    \    / \
   d      e  #   #
  / \    / \
 #   #  #   #
输入要显示的层数n: 2
a b c
#include《stdio.h》
#include《stdlib.h》
typedef struct Node
{
    char data;
    struct Node *left;
    struct Node *right;
}Bitree;
//用"先序扩展序列"创建二叉树
void CreateTree(Bitree **p)
{
    char ch;
    scanf("%c",&ch); //输入数据
    if(ch==’#’)      //’#’是空结点
    {
        *p=NULL;
    }
    else
    {
        *p=(Bitree *)malloc(sizeof(Bitree));
        if(*p == NULL)
        {
            printf("\nmalloc error.\n");
            exit(1);
        }
        (*p)-》data=ch;
        CreateTree(&((*p)-》left));
        CreateTree(&((*p)-》right));
    }
}
//输出先序遍历结点
void preOrder(Bitree *p)
{
    if(p)
    {
        printf("%c ",p-》data);
        preOrder(p-》left);
        preOrder(p-》right);
    }
}
//输出前n层的先序遍历结点
void showTree(Bitree *p,int n)
{
    static int depth=0;
    depth++;
    if(p)
    {
        if(depth《=n)
        {
            printf("%c ",p-》data);
        }
        showTree(p-》left,n);
        showTree(p-》right,n);
    }
    depth--;
}
int main()
{
    Bitree *root;
    int n;
    CreateTree(&root);
    printf("前序遍历序列: ");
    preOrder(root);
    while(1)
    {
        printf("\n输入要显示的层数n(输入0退出): ");
        scanf("%d",&n);
        if(n《1)
        {
            break;
        }
        showTree(root,n);
        printf("\n");
    }
    return 0;
}

二叉树的遍历，为什么输出为null

有两个错误：1.当读入的是空格时，T赋值为空不错，但此时应该返回，而不应该进入下一个判断的else分句，楼主的代码就是进入了if(ch==’#’) exit(0);的else分句。2.可以看到主函数中对createbitree的调用需要用一个指针承接返回值，所以根据递归调用的形式不变，在createbitree中调用自身的时候也要承接返回值。根据楼主的代码修改如下：
#include《stdio.h》
#include《malloc.h》
#include《stdlib.h》
typedef struct BiTNode
{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
BiTree creatbitree(BiTree t) //先序建立二叉树
{
BiTree T=t;
char ch;
ch=getchar();
if(ch==’ ’)
T=NULL;
else {
if(ch==’#’)
exit(0);
else{
T=(BiTNode *)malloc(sizeof(BiTNode));
T-》data=ch;
T-》lchild = creatbitree(T-》lchild);
T-》rchild = creatbitree(T-》rchild);
}
}

return T;
}
void BiTreeTra(BiTree t) //先序遍历二叉树
{
if(t)
{
printf("%c",t-》data);
BiTreeTra(t-》lchild);
BiTreeTra(t-》rchild);
}
}
void main()
{
BiTree tree;
BiTree T=NULL;
tree=creatbitree(T);
BiTreeTra(tree);
}

c语言 二叉树的遍历

//---------------------------------------------------------------------------
#include《iostream》
using namespace std;
typedef struct node
{
struct node *L,*R;
string name;
}NODE;
//输入
void Input(NODE **T,int num)
{
string name;
int L,R;
*T = new NODE;
for (int i=0;i《num;)
{
cout 《《 "输入第"《《i+1《《"个结点名称、左右子序号:"《《endl;
cin 》》 name 》》 L 》》 R;
if(L 》=num || R 》=num)
{
cout 《《 "输入结点序号非法，请重新输入"《《endl;
continue;
}
(*T+i)-》name = name;
(*T+i)-》L = L==-1? NULL:*T+L;
(*T+i)-》R = R==-1? NULL:*T+R;
i++;
}
}
//前序
void NLR(NODE *T)
{
if(T==NULL)return ;
cout 《《T-》name《《" ";
NLR(T-》L);
NLR(T-》R);
}
//中序
void LNR(NODE *T)
{
if(T==NULL)return ;
NLR(T-》L);
cout 《《T-》name《《" ";
NLR(T-》R);
}
//后序
void LRN(NODE *T)
{
if(T==NULL)return ;
NLR(T-》L);
NLR(T-》R);
cout 《《T-》name《《" ";
}
int main()
{
NODE *T=NULL,t;
int num;
cout 《《 "输入结点数:"《《endl;
cin 》》 num;
Input(&T,num);
cout 《《"前序：";
NLR(T);
cout 《《 endl;
cout 《《"中序：";
LNR(T);
cout 《《 endl;
cout 《《"后序：";
LRN(T);
cout 《《 endl;
system("PAUSE");
return 0;
}