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

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

乐跑小子 · 2018-4-30 02:06:48

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

#include
#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();
}

jsjplilyplily · 2018-4-30 02:06:49

先序输入  如  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
#include
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);
}

热心网友 · 2018-4-30 02:06:50

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

还有个人 · 2018-4-30 02:06:51

//定义结构体
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);//访问右子树
}
}
其他的细节你自己去完善，我就写到这里了

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

4 个回复