20分求解!!!关于二叉树的先,中,后序遍历结果出错(c语言实现)

Question

程序能运行,但是不能得到真确的(中后序)结果.请各位高手在1点前帮我解决,谢谢了.
请附上你输入的二叉树和运行结果,最好能给个二叉树的图形.
........
typedef struct node{
char data;
struct node *lchild,*rchild;
}BinTNode;
typedef BinTNode *BinTree;

BinTree CreatBinTree(void)
{
BinTree T;
char ch;
if((ch=getchar())=='#')
return(NULL);
else{
T=(BinTNode *)malloc(sizeof(BinTNode));
T->data=ch;
T->lchild=CreatBinTree();
T->rchild=CreatBinTree();
return(T);
}
}
void Preorder(BinTree T)
{
if(T!=NULL) {
printf("%c",T->data);
Preorder(T->lchild);
Preorder(T->rchild);
}
}

void Inorder(BinTree T)
{
if(T!=NULL) {
Preorder(T->lchild);
printf("%c",T->data);
Preorder(T->rchild);
}
}
void main()
{
BinTree root;
printf("\n");
printf("Creat Bin_Tree； Input preorder:");
root=CreatBinTree();
Preorder(root);
printf("\n");
Inorder(root);
printf("\n");
}
对不起,刚刚代码传慢了,请用我上面的代码实现吧,谢谢!

Answer 1

二叉树的创建、前序遍历、中序遍历、后序遍历
// BTree.cpp : Defines the entry point for the console application.
/*

*/
#include "stdafx.h"
#include "stdlib.h"

#define MAX_NODE 100
#define NODE_COUNT1 8
#define NODE_COUNT2 15

int TreeValue0[NODE_COUNT1][2] = {{'0',0},{'D',1},{'B',2},{'F',3},{'A',4},{'C',5},{'E',6},{'G',7}};
int TreeValue1[NODE_COUNT1][2] = {{'0',0},{'A',1},{'B',2},{'C',3},{'D',4},{'E',5},{'F',6},{'G',7}};
int TreeValue2[NODE_COUNT2][2] = {{'0',0},{'A',1},{'B',2},{'C',3},{'D',4},{'E',5},{'F',6},{'G',7},{'H',8},{'I',9},{'J',10},{'K',11},{'L',12},{'M',13},{'N',14}};
struct BTree
{
int data;
int order;
BTree *lchild;
BTree *rchild;
};

void Swap(int *p1,int *p2)
{
int t;
t = *p1;
*p1 = *p2;
*p2 = t;
}
/*
function CreateBTree()功能：创建一颗二叉树，并返回一个指向其根的指针
*/
BTree *CreateBTree(int data[][2],int n)
{
BTree *Addr[MAX_NODE];
BTree *p,
*head;
int nodeorder,//节点序号
noderoot, //节点的双亲
i;
if(n>MAX_NODE)
{
printf("参数错误！\n");
return(0);
}
for(i=1;i<=n;i++)
{
p = (BTree *)malloc(sizeof(BTree));
if(p==NULL)
{
printf("内存溢出错误！\n");
return(0);
}
else
{
p->data = data[i][0];
p->lchild = NULL;
p->rchild = NULL;
nodeorder = data[i][1];
p->order = nodeorder;
Addr[nodeorder] = p;
if(nodeorder>1)
{
noderoot = nodeorder/2;
if(nodeorder %2 == 0)
Addr[noderoot]->lchild = p;
else
Addr[noderoot]->rchild = p;
}
else
head = p;
printf("BTree[%d] = %c\t",p->order,p->data);
}
//free(p);
}
return(head);
}

/*
function FirstOrderAccess0()功能：实现二叉树的前序遍历
二叉树前序遍历的思想：
从根节点开始，沿左子树一直走到没有左孩子的节点为止，
依次访问所经过的节点，同时所经[节点]的地址进栈；
当找到没有左孩子的节点时，从栈顶退出该节点的双亲的
右孩子，此时，此节点的左子树已访问完毕；
在用上述方法遍历该节点的右子树，如此重复到栈空为止。
*/
void FirstOrderAccess0(BTree * header)
{
BTree * stack[MAX_NODE];
BTree *p;
int top;
top = 0;
p = header;
do
{
while(p!=NULL)
{
printf("BTree[%d] = %c\t",p->order,p->data);//访问节点P
top = top+1;
stack[top] = p;
p = p->lchild;//继续搜索节点P的左子树
}
if(top!=0)
{
p = stack[top];
top = top-1;
p = p->rchild;//继续搜索节点P的右子树
}
}while((top!=0)||(p!=NULL));
}
/*
function FirstOrderAccess1()功能：实现二叉树的前序遍历
二叉树前序遍历的思想：
从根节点开始，沿左子树一直走到没有左孩子的节点为止，
依次访问所经过的节点，同时所经[节点的非空右孩子]进栈；
当找到没有左孩子的节点时，从栈顶退出该节点的双亲的
右孩子，此时，此节点的左子树已访问完毕；
在用上述方法遍历该节点的右子树，如此重复到栈空为止。
*/
void FirstOrderAccess1(BTree * header)
{
BTree * stack[MAX_NODE];
BTree *p;
int top;
top = 0;
p = header;
do
{
while(p!=NULL)
{
printf("BTree[%d] = %c\t",p->order,p->data);
if(p->rchild!=NULL)
stack[++top] = p->rchild;
p = p->lchild;
}
if(top!=0)
p = stack[top--];
}while((top>0)||(p!=NULL));
}

/*
function MiddleOrderAccess()功能：实现二叉树的中序遍历
二叉树中序遍历的思想：
从根节点开始，沿左子树一直走到没有左孩子的节点为止，
并将所经[节点]的地址进栈；
当找到没有左孩子的节点时，从栈顶退出该节点并访问它，
此时，此节点的左子树已访问完毕；
在用上述方法遍历该节点的右子树，如此重复到栈空为止。
*/
void MiddleOrderAccess(BTree * header)
{
BTree * stack[MAX_NODE];
BTree *p;
int top;
top = 0;
p = header;
do
{
while(p!=NULL)
{
stack[++top] = p;//节点P进栈
p = p->lchild; //继续搜索其左子树
}
if(top!=0)
{
p = stack[top--];//节点P出栈
printf("BTree[%d] = %c\t",p->order,p->data);//访问节点P
p = p->rchild;//继续搜索其左子树
}
}while((top!=0)||(p!=NULL));
}

/*
function LastOrderAccess()功能：实现二叉树的后序遍历
二叉树后序遍历的思想：
从根节点开始，沿左子树一直走到没有左孩子的节点为止，
并将所经[节点]的地址第一次进栈；
当找到没有左孩子的节点时，此节点的左子树已访问完毕；
从栈顶退出该节点，判断该节点是否为第一次进栈，如是，再
将所经[节点]的地址第二次进栈，并沿该节点的右子树一直走到
没有右孩子的节点为止，如否，则访问该节点；此时，该节点的
左、右子树都已完全遍历，且令指针p = NULL;
如此重复到栈空为止。
*/
void LastOrderAccess(BTree * header)
{
BTree * stack[MAX_NODE];//节点的指针栈
int count[MAX_NODE];//节点进栈次数数组
BTree *p;
int top;
top = 0;
p = header;
do
{
while(p!=NULL)
{
stack[++top] = p;//节点P首次进栈
count[top] = 0;
p = p->lchild; //继续搜索节点P的左子树
}
p = stack[top--];//节点P出栈
if(count[top+1]==0)
{
stack[++top] = p;//节点P首次进栈
count[top] = 1;
p = p->rchild; //继续搜索节点P的左子树
}
else
{
printf("BTree[%d] = %c\t",p->order,p->data);//访问节点P
p = NULL;
}
}while((top>0));
}
/*
function IsLeafNode()功能：判断给定二叉树的节点是否是叶子节点
*/
int IsLeafNode(BTree *node)
{
if((node->lchild==NULL)&&(node->rchild==NULL))
return(1);
else
return(0);
}
/*
function PrintLeafNode()功能：输出给定二叉树的叶子节点
*/
void PrintLeafNode(BTree *header)
{
BTree * stack[MAX_NODE];//节点的指针栈
BTree *p;
int top;
p = header;
top = 0;
do
{
while(p!=NULL)
{
stack[++top] = p;
p = p->lchild;//继续搜索节点P的左子树
}
if(top!=0)
{
p = stack[top--];
if(IsLeafNode(p))
printf("LNode[%d] = %c\t",p->order,p->data);//访问叶子节点
p = p->rchild;//继续搜索节点P的右子树
}
}while(top>0||p!=NULL);
}
/*
function HasTwoChildNode()功能：判断给定二叉树的节点是否存在两个孩子节点
*/
int HasTwoChildNode(BTree *node)
{
if((node->lchild!=NULL)&&(node->rchild!=NULL))
return(1);
else
return(0);
}
/*
function SwapChildNode()功能：交换给定二叉树的所有节点的左、右孩子
*/
void SwapChildNode(BTree *header)
{
BTree * stack[MAX_NODE];//节点的指针栈
BTree *p;
int top;
p = header;
top = 0;
do
{
while(p!=NULL)
{
stack[++top] = p;
p = p->lchild;//继续搜索节点P的左子树
}
if(top!=0)
{
p = stack[top--];
if(HasTwoChildNode(p))
Swap(&p->lchild->data,&p->rchild->data);//交换节点P的左、右孩子
p = p->rchild;//继续搜索节点P的右子树
}
}while(top>0||p!=NULL);
}

int main(int argc, char* argv[])
{
BTree * TreeHeader;
printf("二叉树创建数据结果：\n");
TreeHeader = CreateBTree(TreeValue1,NODE_COUNT1-1);
//TreeHeader = CreateBTree(TreeValue2,NODE_COUNT2-1);
if (TreeHeader==0)
{
printf("二叉树创建失败！\n");
return(0);
}
else
{
printf("\n二叉树前序遍历结果：\n");
FirstOrderAccess1(TreeHeader);
printf("\n二叉树中序遍历结果：\n");
MiddleOrderAccess(TreeHeader);
printf("\n二叉树后序遍历结果：\n");
LastOrderAccess(TreeHeader);
//printf("\n二叉树的所有叶子节点：\n");
//PrintLeafNode(TreeHeader);
//SwapChildNode(TreeHeader);
//printf("\n二叉树交换孩子的结果：\n");
//MiddleOrderAccess(TreeHeader);
printf("\n程序运行完毕!\n");
return 0;
}
}

Answer 2

你的代码中
void Inorder(BinTree T)
{
if(T!=NULL) {
Preorder(T->lchild);
printf("%c",T->data);
Preorder(T->rchild);
}
}
改为
void Inorder(BinTree T)
{
if(T!=NULL) {
Inorder(T->lchild);
printf("%c",T->data);
Inorder(T->rchild);
}
}
就可以了。

×××××××××××××××××××××××××××××××××××××××××

#include <stdio.h>
#include <malloc.h>

#define null 0
struct CTreeNode
{
/*数据*/
char data;
/*左孩子*/
struct CTreeNode* LeftChild;
/*右孩子*/
struct CTreeNode* RightChild;
};

/*访问结点*/
void VisitNode(struct CTreeNode *pNode)
{
printf("%2c ", pNode->data);
}

/*先序遍历*/
void PreOrderTraversal(struct CTreeNode *pNode)
{
VisitNode(pNode);

struct CTreeNode *pLChild = pNode->LeftChild;
if (pLChild != null)
{
PreOrderTraversal(pLChild);
}

struct CTreeNode *pRChild = pNode->RightChild;
if (pRChild != null)
{
PreOrderTraversal(pRChild);
}
}

/*中序遍历*/
void InOrderTraversal(struct CTreeNode *pNode)
{
struct CTreeNode *pLChild = pNode->LeftChild;
if (pLChild != null)
{
InOrderTraversal(pLChild);
}

VisitNode(pNode);

struct CTreeNode *pRChild = pNode->RightChild;
if (pRChild != null)
{
InOrderTraversal(pRChild);
}
}

/*后序遍历*/
void PostOrderTraversal(struct CTreeNode *pNode)
{
struct CTreeNode *pLChild = pNode->LeftChild;
if (pLChild != null)
{
PostOrderTraversal(pLChild);
}

struct CTreeNode *pRChild = pNode->RightChild;
if (pRChild != null)
{
PostOrderTraversal(pRChild);
}

VisitNode(pNode);
}

int main()
{
/*
构建一个树
A
| \
B C
| \ \
D E F
*/
struct CTreeNode* A = (struct CTreeNode*)malloc(sizeof(struct CTreeNode));
struct CTreeNode* B = (struct CTreeNode*)malloc(sizeof(struct CTreeNode));
struct CTreeNode* C = (struct CTreeNode*)malloc(sizeof(struct CTreeNode));
struct CTreeNode* D = (struct CTreeNode*)malloc(sizeof(struct CTreeNode));
struct CTreeNode* E = (struct CTreeNode*)malloc(sizeof(struct CTreeNode));
struct CTreeNode* F = (struct CTreeNode*)malloc(sizeof(struct CTreeNode));

A->data = 'A';
A->LeftChild = B;
A->RightChild = C;

B->data = 'B';
B->LeftChild = D;
B->RightChild = E;

C->data = 'C';
C->LeftChild = null;
C->RightChild = F;

D->data = 'D';
D->LeftChild = null;
D->RightChild = null;

E->data = 'E';
E->LeftChild = null;
E->RightChild = null;

F->data = 'F';
F->LeftChild = null;
F->RightChild = null;

/*先序遍历*/
printf("PreOrderTraversal :");
PreOrderTraversal(A);
printf("\n");

/*中序遍历*/
printf("InOrderTraversal :");
InOrderTraversal(A);
printf("\n");

/*后序遍历*/
printf("PostOrderTraversal:");
PostOrderTraversal(A);
printf("\n");

free(A);
free(B);
free(C);
free(D);
free(E);
free(F);
return 0;
}本回答被提问者采纳

Answer 3

二叉树前序遍历函数dpre_Order_Access()<递归算法>
参数描述：
BTNode *head: 二叉树的根节点指针
*/
void dpre_Order_Access(BTNode *head)
{
if(head!=NULL)
{
if(SHOWCHAR)
printf("%c ",head->data);
else
printf("%d ",head->data);
dpre_Order_Access(head->lchild); /*递归遍历左子树*/
dpre_Order_Access(head->rchild); /*递归遍历右子树*/
}
}
/*
二叉树中序遍历函数dmid_Order_Access()<递归算法>
参数描述：
BTNode *head: 二叉树的根节点指针
*/
void dmid_Order_Access(BTNode *head)
{
if(head!=NULL)
{
dmid_Order_Access(head->lchild); /*递归遍历左子树*/
if(SHOWCHAR)
printf("%c ",head->data);
else
printf("%d ",head->data);
dmid_Order_Access(head->rchild); /*递归遍历右子树*/
}
}
/*
二叉树后序遍历函数dlast_Order_Access()<递归算法>
参数描述：
BTNode *head: 二叉树的根节点指针
*/
void dlast_Order_Access(BTNode *head)
{
if(head!=NULL)
{
dlast_Order_Access(head->lchild); /*递归遍历左子树*/
dlast_Order_Access(head->rchild); /*递归遍历右子树*/
if(SHOWCHAR)
printf("%c ",head->data);
else
printf("%d ",head->data);
}
}
树:~~~~6
`````````/```\
````````2`````4
```````/`\```/`\
``````8``7`3``9
前序：6 2 8 7 4 3 9
中序：8 2 7 6 3 4 9
后序：8 7 2 3 9 4 6