关于C语言二叉树?

Question

我想知道C语言的二叉树:后序遍历序列,中序遍历序列,前序遍历序列的定义及拓扑图?

Answer 1

首先二叉树的结点是由做孩子指针*lchild 右孩子指针*rchild 以及数据成员data

L表示左孩子R表示右孩子T表示他们的父结点

后序遍历的访问顺序是LRT
中序遍历的访问顺序是LTR
前序遍历的访问顺序是TLR

其中说的前中后就是指访问父结点的次序；

拓扑图在这里没法给出啊。。。

--------------------------------------------

这是我用C++类写的二叉树的头文件，里面有几个函数你可能用不到，你主要看看那几个遍历函数

#include<iostream>

using namespace std;

typedef char elemType;

struct bnode
{
bnode *lchild,*rchild;
elemType data;
};

class BinaryTree
{
public:
BinaryTree();
void create(bnode* &tempR);
void visite(bnode *T);
void preorder(bnode *T);
void inorder(bnode *T);
void postorder(bnode *T);
int high(bnode *T);
void convert(bnode* &tempR,string &a,int i);
void copy(bnode *T,bnode *&T1);
void level(bnode *T,int i);
void swap(bnode *T);
bnode *root;
private:
int count;
};

BinaryTree::BinaryTree()
{
root = NULL;
count = 0;
}

void BinaryTree::create(bnode* &tempR)
{
elemType x;
cin>>x;
if(x == '.')
{
tempR = NULL;
}
else
{
tempR = new bnode;
count++;
tempR->data = x;
create(tempR->lchild);
create(tempR->rchild);
}
}

void BinaryTree::visite(bnode *T)
{
if(T!=NULL)
cout<<T->data<<' ';
}

void BinaryTree::preorder(bnode *T)
{
if(T!=NULL)
{
visite(T);
preorder(T->lchild);
preorder(T->rchild);
}
}

void BinaryTree::inorder(bnode *T)
{
if(T!=NULL)
{
inorder(T->lchild);
visite(T);
inorder(T->rchild);
}
}

void BinaryTree::postorder(bnode *T)
{
if(T!=NULL)
{
postorder(T->lchild);
postorder(T->rchild);
visite(T);
}
}

int BinaryTree::high(bnode *T)
{
if(T==NULL)
return 0;
else if(high(T->lchild)>high(T->rchild))
return high(T->lchild)+1;
else
return high(T->rchild)+1;
}

void BinaryTree::level(bnode *T,int i)
{
if(T!=NULL)
{
level(T->lchild,i+1);
visite(T);
cout<<i<<' ';
level(T->rchild,i+1);
}
}

void BinaryTree::convert(bnode *&T,string &a,int i)
{
elemType x;
if(i<=a.length())
{
x = a[i-1];
T = new bnode;
count++;
T->data = x;
convert(T->lchild,a,2*i);
convert(T->rchild,a,2*i+1);
}
else
{
T=NULL;
}
}

void BinaryTree::copy(bnode *T,bnode *&T1)
{
elemType x;
if(T!=NULL)
{
x=T->data;
if(x == '.')
{
T1 = NULL;
}
else
{
T1 = new bnode;
T1->data = x;
T1->lchild = NULL;
T1->rchild = NULL;
copy(T->lchild,T1->lchild);
copy(T->rchild,T1->rchild);
}

}
}

void BinaryTree::swap(bnode *T)
{
if(T!=NULL)
{
bnode *temp;
temp=T->lchild;
T->lchild=T->rchild;
T->rchild=temp;
swap(T->lchild);
swap(T->rchild);
}
}

Answer 2

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

typedef struct bitnode //定义二叉树
{
char data;
struct bitnode *lchild, *rchild;
}bitnode, *bitree;

void createbitree(t,n) //建立二叉树
bitnode ** t;
int *n;
{
char x;
bitnode *q;

*n=*n+1;
printf("\n Input %d DATA:",*n);
x=getchar();
if(x!='\n') getchar();

if (x=='\n')
return;

q=(bitnode*)malloc(sizeof(bitnode));
q->data=x;
q->lchild=NULL;
q->rchild=NULL;
*t=q;

printf("This Address is:%o,Data is:%c,\n Left Pointer is:%o,Right Pointer is: %o",q,q->data,q->lchild,q->rchild);

createbitree(&q->lchild,n);
createbitree(&q->rchild,n);
return;
}

void visit(e) //遍历二叉树
bitnode *e;
{
printf(" Address: %o, Data: %c, Left Pointer: %o, Right Pointer: %o\n",e,e->data,e->lchild,e->rchild);
}

void preordertraverse(t)//前序遍历序列
bitnode *t;
{
if(t)
{
visit(t);
preordertraverse(t->lchild);
preordertraverse(t->rchild);
return ;
}else return ;
}

void countleaf(t,c)//二叉树长度
bitnode *t;
int *c;
{
if(t!=NULL)
{
if (t->lchild==NULL && t->rchild==NULL)
{*c=*c+1;
}
countleaf(t->lchild,c);
countleaf(t->rchild,c);
}
return;
}

int treehigh(t)
bitnode *t;
{int lh,rh,h;
if(t==NULL)
h=0;
else{
lh=treehigh(t->lchild);
rh=treehigh(t->rchild);
h=(lh>rh ? lh:rh)+1;
}
return h;
}
main()
{
bitnode *t; int count=0;
int n=0;

printf("\n Please input TREE Data:\n");
createbitree(&t,&n);

printf("\n This is TREE Struct: \n");
preordertraverse(t);

countleaf(t,&count);
printf("\n This TREE has %d leaves ",count);

printf(",High of The TREE is: %d\n",treehigh(t));
}