请问这个问题如何处理
问题遇到的现象和发生背景
以二叉链表作存储结构，建立一棵二叉树， 输出该二叉树的先序，中序，后序遍历序列。
二叉链表的类型描述：
typedef char ElemType;
typedef struct BiNode
{ ElemType data;
struct BiNode *lchild,*rchild;
}BiNode,*BiTree;
输入格式:
输入一个二叉树的先序序列，空的位置以#替代。
输出格式:
输出该二叉树的先序遍历序列。输出的遍历序列中字符间均无间隔。
一、实验目的
- 通过练习进一步认识非线性结构的特征；
- 掌握树状结构与线性结构的差别；
- 掌握树的存储结构及遍历二叉树的方法。
二、实验内容
①题目：
先序建立并以递归与非递归方式前中后序遍历二叉树。
建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（先序，中序和后序），打印遍历输出结果。
【基本要求】从键盘接受输入先序序列，以二叉链表作为存储结构，建立二叉树（以先序来建立）并对其进行遍历（先序，中序，后序），然后将遍历结果打印输出。要求采用递归与非递归方式实现。
【测试数据】 ABC##DE#G##F###
【输出结果】
先序序列为 ABCDEGF
中序序列为 CBEGDFA
后序序列为 CGEFDBA
②实验过程：
1.程序设计思路：
A.递归方法
前序根 左 右；中序左 根 右；后序左 右 根。
B.非递归遍历思想:
非递归前序遍历二叉树:
若栈不为空且p不为空时入栈即出栈并打印,然后将其右孩子入栈,再继续访问其左孩子;若p为空,则出栈。
非递归中序遍历二叉树:
从根结点开始,让二叉树左中右遍历,若不为空则入栈,若为空则出栈。
非递归后序遍历二叉树:
每个结点都要进栈俩次,第二次退栈时才访问结点。第一次进栈时，在遍历左子树的过程中将根结点进栈，待左子树访问完后，回溯的结点退栈，即退出这个根结点，但不能立即访问，只能借助这个根去找该根的右子树，并遍历这棵右子树，直到该右子树全部遍历以后，再退出该根结点，并访问它。所以，为了记录结点是第一次还是第二次进栈，需单独定义一个结点作为标志。
2.程序源代码：
方法一：递归方式遍历
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
typedef struct Node
{
char data;
struct Node* LChild;
struct Node* RChild;
}BiTNode, * BiTree;
void PreOrder(BiTree root);
void InOrder(BiTree root);
void PostOrder(BiTree root);
void Visit(char x) {
putchar(x);
}
BiTree CreateBiTree(BiTree T)
{
char ch;
ch = getchar();
if (ch == '#')
return NULL;
else
{
T = (BiTree*)malloc(sizeof(BiTNode));
T->data = ch;
T->LChild = CreateBiTree(T->LChild);
T->RChild = CreateBiTree(T->RChild);
}
return T;
}
//递归方式前序遍历二叉树
void PreOrder(BiTree root)
{
if (root != NULL) {
Visit(root->data);
PreOrder(root->LChild);
PreOrder(root->RChild);
}
}
//递归方式中序遍历二叉树
void InOrder(BiTree root)
{
if (root != NULL) {
InOrder(root->LChild);
Visit(root->data);
InOrder(root->RChild);
}
}
//递归方式后序遍历二叉树
void PostOrder(BiTree root)
{
if (root != NULL) {
PostOrder(root->LChild);
PostOrder(root->RChild);
Visit(root->data);
}
}
int main()
{
BiTree T=NULL;
printf("请依次输入二叉树的结点：\n");
T = CreateBiTree(T);
printf("先序遍历结果为: \n");
PreOrder(T);
printf("\n中序遍历结果为: \n");
InOrder(T);
printf("\n后序遍历结果为: \n");
PostOrder(T);
return 0;
}
运行截图
**
方法二:用栈消除递归遍历二叉树(前,中,后序)**
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define Stack_Size 100//设栈中元素个数为100个
//定义结构体二叉树
typedef struct Node
{
char data;
struct Node* LChild;
struct Node* RChild;
}BiTNode, * BiTree;
//定义结构体顺序栈
typedef BiTree StackElementType;
typedef struct {
StackElementType elem[Stack_Size];//存放栈中元素的一维数组
int top;//栈顶元素下标,top为-1表示空栈
}SeqStack;
SeqStack S;//定义一个全局栈
BiTree p;//定义一各全局树指针
void Visit(char x) {
putchar(x);
}
//先序遍历创建二叉树
BiTree CreateBiTree(BiTree T)
{
char ch;
ch = getchar();
if (ch == '#')
return NULL;
else
{
T = (BiTree*)malloc(sizeof(BiTNode));
T->data = ch;
T->LChild = CreateBiTree(T->LChild);
T->RChild = CreateBiTree(T->RChild);
}
return T;
}
//初始化空栈
void InitStack(SeqStack *S)
{
S -> top = -1;
}
//压栈
int Push(SeqStack *S, StackElementType x)
{
if (S->top == Stack_Size - 1) return FALSE;//
S->top++;
S->elem[S->top] = x;
return TRUE;
}
//出栈
int Pop(SeqStack *S, StackElementType *x)
{
if (S->top == -1)
return FALSE;
else
{
*x = S->elem[S->top];
S->top--;
return TRUE;
}
}
//判断栈是否为空
int IsEmpty(SeqStack *S)
{
if (S->top==-1) return TRUE;//空栈返回1
else
return FALSE;//非空栈返回0
}
//非递归前序遍历二叉树
/*若栈不为空且p不为空时入栈即出栈并打印,然后将其右孩子入栈,
再继续访问其左孩子;若p为空,则出栈*/
void PreOrderByStack(BiTree root)
{
InitStack(&S);
p = root;
if (p == NULL) return;
while (p !=NULL||!IsEmpty(&S))
{
if (p)
{
Push(&S, p);
Pop(&S, &p);
Visit(p->data);
Push(&S, p->RChild);
p = p->LChild;
}
else
Pop(&S, &p);
}
}
//非递归中序遍历二叉树
/*从根结点开始,让二叉树左中右遍历,若不为空则入栈,若为空出栈*/
void InOrderByStack(BiTree root)
{
InitStack(&S);
p = root;
if (p == NULL) return;
while (p!=NULL||!IsEmpty(&S))
{
if (p != NULL)//根指针进栈,遍历左子树
{
Push(&S, p);
p = p->LChild;
}
else
{//根指针退栈,访问根结点,遍历右子树
Pop(&S, &p);
Visit(p->data);
p = p->RChild;
}
}
}
//非递归后序遍历二叉树
/*每个结点都要进栈俩次,第二次退栈时才访问结点。第一次进栈时，
在遍历左子树的过程中将根结点进栈，待左子树访问完后，回溯的结点退栈，
即退出这个根结点，但不能立即访问，只能借助这个根去找该根的右子树，
并遍历这棵右子树，直到该右子树全部遍历以后，再退出该根结点，并访问它。
所以，为了记录结点是第一次还是第二次进栈，需单独定义一个结点作为标志。*/
void PostOrderByStack(BiTree root)
{
InitStack(&S);
p = root;
if (p == NULL) return;
BiTree* tag = NULL;//定义的标志
while (p != NULL || !IsEmpty(&S))
{
while (p!=NULL)
{
Push(&S, p);
p = p->LChild;
}
Pop(&S,&p);//遇到空直接出栈
if (p->RChild==NULL||p->RChild==tag)
{
Visit(p->data);
tag = p;
p = NULL;
}
else
{
Push(&S, p);
p = p->RChild;
}
}
}
int main()
{
BiTree T=NULL;
printf("请依次输入二叉树的结点：\n");
T = CreateBiTree(T);
printf("\n先序非递归遍历结果为: \n");
PreOrderByStack(T);
printf("\n中序非递归遍历结果为: \n");
InOrderByStack(T);
printf("\n后序非递归遍历结果为: \n");
PostOrderByStack(T);
return 0;
}
运行截图
有用请点采纳 ，谢谢！
C语言代码实现如下：
#include<stdio.h>
#include<stdlib.h>
//定义二叉树链表结点结构
typedef char ElemType;
typedef struct BiNode
{
ElemType data;
struct BiNode *lchild,*rchild;
}BiNode,*BiTree;
//创建二叉树
void CreateBiTree(BiTree* bt) //此时bt为二级指针
{
char ch;
ch = getchar();
if (ch == '#')
{
*bt = NULL;
}
else
{
*bt = (BiTree)malloc(sizeof(BiNode));
(*bt)->data = ch;
CreateBiTree(&((*bt)->lchild)); //一级指针值为空，二级指针要把地址传入
CreateBiTree(&((*bt)->rchild));
}
}
//先序遍历
void PreOrder(BiTree root)
{
if (root != NULL)
{
printf("%c", root->data);
PreOrder(root->lchild);
PreOrder(root->rchild);
}
}
//中序遍历
void InOrder(BiTree root)
{
if (root != NULL)
{
InOrder(root->lchild);
printf("%c", root->data);
InOrder(root->rchild);
}
}
//后序遍历
void PostOrder(BiTree root)
{
if (root != NULL)
{
PostOrder(root->lchild);
PostOrder(root->rchild);
printf("%c", root->data);
}
}
int main()
{
BiTree bt = NULL;//创建一个空树
printf("输入先序二叉树结点(子树为空输入#)：\n");
CreateBiTree(&bt);
printf("\n输出先序遍历：");
PreOrder(bt);
printf("\n输出中序遍历：");
InOrder(bt);
printf("\n输出后序遍历：");
PostOrder(bt);
return 0;
}
感谢采纳，不懂可继续交流！
先搞懂基本机构
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
typedef struct Node//结构体
{
char data;
struct Node *LChild;
struct Node *RChild;
} BiTNode,*BiTree;
void InitList(BiTree *l)//初始化
{
*l= (BiTree)malloc(sizeof(BiTNode));
(*l)->LChild = NULL;
(*l)->RChild = NULL;
}
void CreateBiTree(BiTree *bt) //先序创建二叉树
{
char ch;
ch = getchar();
if (ch == ' ') *bt = NULL;
else
{
*bt = (BiTree)malloc(sizeof(BiTNode));
(*bt)->data = ch;
CreateBiTree(&((*bt)->LChild));
CreateBiTree(&((*bt)->RChild));
}
}
void PreOrder(BiTree root)//先序遍历
{
if (root != NULL)
{
printf("%c", root->data);
PreOrder(root->LChild);
PreOrder(root->RChild);
}
}
void InOrder(BiTree root)//中序遍历
{
if (root != NULL)
{
InOrder(root->LChild);
printf("%c", root->data);
InOrder(root->RChild);
}
}
void PostOrder(BiTree root)//后序遍历
{
if (root != NULL)
{
PostOrder(root->LChild);
PostOrder(root->RChild);
printf("%c", root->data);
}
}
int main()
{
BiTree bt;
InitList(&bt);
CreateBiTree(&bt);
PreOrder(bt);
printf("\n");
InOrder(bt);
printf("\n");
PostOrder(bt);
printf("\n");
system("pause");
}
#include<stdio.h>
#include<stdlib.h>
#define BITREE_NODE_TYPE_ELEMENT char
typedef struct bi_tree_node
{
BITREE_NODE_TYPE_ELEMENT data;
struct bi_tree_node* LChild;
struct bi_tree_node* RChild;
}BiTree_Node, * BiTree;
void postOrder(BiTree root); //声明 后序遍历 函数
void inOrder(BiTree root); //声明 中序遍历 函数
void preOrder(BiTree root); //声明 先序遍历 函数
void createBiTree(BiTree* bi_tree); //声明 创建二叉树 函数
void visit(BITREE_NODE_TYPE_ELEMENT data); //声明 访问结点数据 函数
int main()
{
//测试数据：ABC**DE*G**F***
//先序:ABCDEGF
//中序:CBEGDFA
//后序:CGEFDBA
BiTree bi_tree = NULL;
puts("请按先序序列输入一颗二叉树的结点数据，以'#'来代表空值：");
createBiTree(&bi_tree);
printf("\n先序序列：");
preOrder(bi_tree);
printf("\n中序序列：");
inOrder(bi_tree);
printf("\n后序序列：");
postOrder(bi_tree);
putchar('\n');
return 0;
}
//定义 访问结点数据 函数
void visit(BITREE_NODE_TYPE_ELEMENT data)
{
putchar(data);
}
//定义 创建二叉树 函数
void createBiTree(BiTree* bi_tree)
{
char ch;
ch = getchar();
if (ch == '#')
*bi_tree = NULL;
else
{
*bi_tree = (BiTree)malloc(sizeof(BiTree_Node));
(*bi_tree)->data = ch;
createBiTree(&((*bi_tree)->LChild));
createBiTree(&((*bi_tree)->RChild));
}
}
//定义 先序遍历 函数
void preOrder(BiTree root)
//先序遍历二叉树，root为指向二叉树（或某一子树）根节点的指针
{
if (root != NULL)
{
visit(root->data); //访问根节点
preOrder(root->LChild); //先序遍历左子树
preOrder(root->RChild);//先序遍历右子树
}
}
//定义 中序遍历 函数
void inOrder(BiTree root)
//中序遍历二叉树，root为指向二叉树（或某一子树）根节点的指针
{
if (root != NULL)
{
inOrder(root->LChild); //中序遍历左子树
visit(root->data); //访问根节点
inOrder(root->RChild); //中序遍历右子树
}
}
//定义 后序遍历 函数
void postOrder(BiTree root)
//后序遍历二叉树，root为指向二叉树（或某一子树）根节点的指针
{
if (root != NULL)
{
postOrder(root->LChild); //后序遍历左子树
postOrder(root->RChild); //后序遍历右子树
visit(root->data); //访问根节点
}
}
解答如下
#include<stdio.h>
#include<stdlib.h>
typedef char ElemType;
typedef struct BiNode {
ElemType data;
//int data; // 存放数据域
struct BiNode *lchild; // 遍历左子树指针
struct BiNode *rchild; // 遍历右子树指针
} BiNode,*BiTree;
BiTree CreateLink()
{
char data;
int temp;
BiTree T;
scanf("%c",&data); // 输入数据
temp=getchar(); // 吸收空格
if(data == '#') { // 输入-1 代表此节点下子树不存数据，也就是不继续递归创建
return NULL;
} else {
T = (BiTree)malloc(sizeof(BiNode)); // 分配内存空间
T->data = data; // 把当前输入的数据存入当前节点指针的数据域中
printf("请输入%c的左子树: ",data);
T->lchild = CreateLink(); // 开始递归创建左子树
printf("请输入%c的右子树: ",data);
T->rchild = CreateLink(); // 开始到上一级节点的右边递归创建左右子树
return T; // 返回根节点
}
}
// 先序遍历
void ShowXianXu(BiTree T) // 先序遍历二叉树
{
if(T==NULL) // 递归中遇到NULL，返回上一层节点
{
return;
}
printf("%c ",T->data);
ShowXianXu(T->lchild); // 递归遍历左子树
ShowXianXu(T->rchild); // 递归遍历右子树
}
// 中序遍历
void ShowZhongXu(BiTree T) // 先序遍历二叉树
{
if(T==NULL) // 递归中遇到NULL，返回上一层节点
{
return;
}
ShowZhongXu(T->lchild); // 递归遍历左子树
printf("%c ",T->data);
ShowZhongXu(T->rchild); // 递归遍历右子树
}
// 后序遍历
void ShowHouXu(BiTree T) // 后序遍历二叉树
{
if(T==NULL) // 递归中遇到NULL，返回上一层节点
{
return;
}
ShowHouXu(T->lchild); // 递归遍历左子树
ShowHouXu(T->rchild); // 递归遍历右子树
printf("%c ",T->data);
}
int main()
{
BiTree S;
printf("请输入第一个节点的数据:\n");
S = CreateLink(); // 接受创建二叉树完成的根节点
printf("先序遍历结果: \n");
ShowXianXu(S); // 先序遍历二叉树
printf("\n中序遍历结果: \n");
ShowZhongXu(S); // 中序遍历二叉树
printf("\n后序遍历结果: \n");
ShowHouXu(S); // 后序遍历二叉树
return 0;
}
int main() {
BiTree Tree;
CreateBiTree(&Tree);
printf("%d",Tree->lchild->lchild->data);
return 0;
}