Question

用c语言写二叉树，源代码。

老师布置一道题，不会做，请教各位大师；
1、按先序次序输入二叉树中的结点值（分别为数值和字符两种）建立相应的二叉树；
2、中序遍历该二叉树。
谢谢各位了。

Answer 1

二叉树是采用递归定义的，实现起来代码简洁（也许并不简单）。并且它在具体的计算机科学中有很重要的运用，是一种很重要的数据结构，二叉树有三种遍历和建立的方式。今天先学习一下它的建立和打印。
以下代码在Win-Tc1.9.1下编译通过。

#include <stdio.h>
#define ElemType char
//节点声明，数据域、左孩子指针、右孩子指针
typedef struct BiTNode{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//先序建立二叉树
BiTree CreateBiTree(){
char ch;
BiTree T;
scanf("%c",&ch);
if(ch=='#')T=NULL;
else{
T = (BiTree)malloc(sizeof(BiTNode));
T->data = ch;
T->lchild = CreateBiTree();
T->rchild = CreateBiTree();
}
return T;//返回根节点
}
//先序遍历二叉树
void PreOrderTraverse(BiTree T){
if(T){
printf("%c",T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}

//中序遍历
void InOrderTraverse(BiTree T){
if(T){
PreOrderTraverse(T->lchild);
printf("%c",T->data);
PreOrderTraverse(T->rchild);
}
}
//后序遍历
void PostOrderTraverse(BiTree T){
if(T){
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
printf("%c",T->data);
}
}
void main(){
BiTree T;
T = CreateBiTree();//建立
PreOrderTraverse(T);//输出
getch();
}

Answer 2

先序输入 如 abc##d##e## (#表示空)
输出 cbdae

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#include "cstdlib"
#include "malloc.h"
typedef int Status;
typedef char TElemType;
#include <stdio.h>
#include <iostream>
using namespace std;

typedef struct BiTNode { // 结点结构
TElemType data;
struct BiTNode *lchild, *rchild; // 左右孩子指针
} BiTNode, *BiTree;

Status CreateBiTree(BiTree &T){//构造二叉树
TElemType ch;
scanf("%c",&ch);
if(ch=='#') T=NULL;
else{
if(!(T=(BiTree)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return OK;
}//CreateBiTree

Status Visit(char Data)
{
printf("%c",Data);
return OK;
}

Status InOrderTraval(BiTree pTree)
{
if(pTree)
{
if(InOrderTraval(pTree->lchild))
{
if(Visit(pTree->data))
{
if(InOrderTraval(pTree->rchild))
{
return OK;
}
}
return ERROR;
}
return ERROR;
}
else
{
return OK;
}
}

Status v(char a)
{
printf("%c",a);
return OK;
}
void main()
{
BiTree A,b;
printf("先序输入，空用 ＃ 表示：\n");
CreateBiTree(A);
b=A;
printf("中序输出：\n");
InOrderTraval(b);
}

Answer 3

BiTree CreateBiTree(BiTree &T) { // 算法6.4
// 按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树，
// 构造二叉链表表示的二叉树T。
char ch;
scanf("%c",&ch);
if (ch=='#') T = NULL;
else {
if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) return ERROR;
T->data = ch; // 生成根结点
CreateBiTree(T->lchild); // 构造左子树
CreateBiTree(T->rchild); // 构造右子树
}
return T;
} // CreateBiTree

Status InOrderTraverse(BiTree T, Status (*Visit)(ElemType)) {
// 算法6.3
// 采用二叉链表存储结构，Visit是对数据元素操作的应用函数。
// 中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit。
stack S;
BiTree p;
InitStack(S); p = T;
while (p || !StackEmpty(S)) {
if (p) { Push(S, p); p = p->lchild; } // 非空指针进栈，继续左进
else { // 上层指针退栈，访问其所指结点，再向右进
Pop(S, p);
if (!Visit(p->data)) return ERROR;
p = p->rchild;
}
}
return OK;
} // InOrderTraverse

Status PreOrderTraverse( BiTree T, Status(*Visit)(ElemType) ) {
// 算法6.1
// 采用二叉链表存储结构，Visit是对数据元素操作的应用函数，
// 先序遍历二叉树T的递归算法，对每个数据元素调用函数Visit。
// 最简单的Visit函数是：
// Status PrintElement( ElemType e ) { // 输出元素e的值
// printf( e ); // 实用时，加上格式串
// return OK;
// }
// 调用实例：PreOrderTraverse(T, PrintElement);
if (T) {
if (Visit(T->data))
if (PreOrderTraverse(T->lchild, Visit))
if (PreOrderTraverse(T->rchild, Visit)) return OK;
return ERROR;
} else return OK;
} // PreOrderTraverse

Answer 4

//定义结构体
typedef struct btnode
{
char data;
struct btnode *lchild,*rchild;
}*bitreptr;
//建立二叉树
void create_btr(bitreptr t)
{
getchar();
if(x=='#')
t=NULL;
else
{
p=new node;
p->data=x;
t=p;
create_btr(t->lchild);
create_btr(t->rchild);
}
}
//中序遍历二叉树
void inorder(bitreptr p)
{
if(p)
{
inorder(p->lchild);//访问左子树
printf("%c",p->data);//访问根节点
inorder(p->rchild);//访问右子树
}
}
其他的细节你自己去完善，我就写到这里了