Question

用c语言编程实现二叉树的建立和遍历二叉树？

Answer 1

//这是我上数据结构写的 建议理解为主
#include<stdio.h>
#include<stdlib.h>

#define ERROR 0
#define OK 1
#define OVERFLOW -2
#define FLASE 0
#define TURE 1

typedef int Status;
typedef char TElemType;

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

//构造一个二叉树
Status CreateBiTree(BiTree &T){
TElemType str[]="ABC$$D$EF$$G$$$";

static int i=0;

TElemType ch;
ch=str[i++];

if(ch=='$')
T=NULL;
else{
//创建树结点
T=(BiTNode*)malloc(sizeof(BiTNode));
if(!T) exit(OVERFLOW);
T->data=ch;

//创建左子树
CreateBiTree(T->lchild);

//创建右子树
CreateBiTree(T->rchild);
}

return OK;
}

//输出元素data
Status PrntTElem(TElemType data){
putchar(data);

return OK;
}

//先序遍历二叉树
Status PreOrderTraverse(BiTree T,Status(*visit)(TElemType e)){
if(T){
if((*visit)(T->data))
if(PreOrderTraverse(T->lchild,visit))
if(PreOrderTraverse(T->rchild,visit))
return OK;
return ERROR;
}
else return OK;
}

//中序遍历二叉树
Status InOrderTraverse(BiTree T,Status(*visit)(TElemType e)){
if(T){
if(InOrderTraverse(T->lchild,visit))
if(visit(T->data))
if(InOrderTraverse(T->rchild,visit))
return OK;
return ERROR;
}
else return OK;
}

//后序遍历二叉树
Status PostOrderTraverse(BiTree T,Status(*visit)(TElemType e)){
if(T){
if(PostOrderTraverse(T->lchild,visit))
if(PostOrderTraverse(T->rchild,visit))
if(visit(T->data))
return OK;
return ERROR;
}
else return OK;
}

//求二叉树深度
int BiTreeDepth(BiTree T){
int ldep=0,rdep=0;
if(T==NULL)
return 0;
ldep=BiTreeDepth(T->lchild);
rdep=BiTreeDepth(T->rchild);
if(ldep>=rdep)
return ldep+1;
else
return rdep+1;
}
//求叶子数
int BiTreeLeaves(BiTree T){
if(!T)
return 0;
else if(!T->lchild&&!T->rchild)
return 1;
else
return BiTreeLeaves(T->lchild)+BiTreeLeaves(T->rchild);
}

//销毁
int DestroyBiTree(BiTree &T){
if(T){
if(DestroyBiTree(T->lchild))
if(DestroyBiTree(T->rchild))
T=NULL;
}
return OK;
}

void main()
{
BiTree T;

CreateBiTree(T);

printf("先序结果为:");
PreOrderTraverse(T,PrntTElem);

printf("\n中序结果为:");
InOrderTraverse(T,PrntTElem);

printf("\n后序结果为:");
PostOrderTraverse(T,PrntTElem);

printf("\n二叉树的深度为: %d\n",BiTreeDepth(T));

printf("叶子数为: %d\n",BiTreeLeaves(T));

DestroyBiTree(T);

printf("先序结果为:");
PreOrderTraverse(T,PrntTElem);

printf("\n中序结果为:");
InOrderTraverse(T,PrntTElem);

printf("\n后序结果为:");
PostOrderTraverse(T,PrntTElem);

printf("\n");
}

Answer 2

ass CTreeClass
{
typedef struct _TREE_NODE
{
int nData; //数据
_TREE_NODE* pLChild; //左子树
_TREE_NODE* pRChild; //右子树
}TREE_NODE,*PTREE_NODE;
public:
bool IsEmpty(); //判断树是否为空
bool Insert(int nData); //插入数据
void PreOrderTraverse(); //遍历整棵树

private:

bool IsEmpty(PTREE_NODE TreeNode); //判断树是否为空
bool Insert(PTREE_NODE &TreeNode,int nData); //插入数据
void PreOrderTraverse(PTREE_NODE &TreeNode); //遍历整棵树
private:
int m_nCount; //节点数
PTREE_NODE m_pTreeNode; //根
};

//插入数据
bool CTreeClass::Insert(int nData)
{
if (!Insert(m_pTreeNode,nData))
{
return false;
}
return true;
}

bool CTreeClass::Insert(TREE_NODE* &TreeNode,int nData)
{
if (!TreeNode)
{
//新添加节点
TreeNode = new TREE_NODE;
memset(TreeNode,0,sizeof(TREE_NODE));
TreeNode->nData = nData;
m_nCount++;
return true;
}
//判断是否小于根
if (nData < TreeNode->nData)
{
Insert(TreeNode->pLChild,nData);
}
//判断是否小于根
else if (nData > TreeNode->nData)
{
Insert(TreeNode->pRChild,nData);
}
else //等于根
return false;
return true;
}