c语言单链表实现存储,C语言实现二叉链表存储

  • Post author:
  • Post category:其他


利用二叉链表存储,并且利用递归的方法实现二叉树的遍历(前序遍历、中序遍历和后续遍历)操作。

c语言具体实现代码如下:

#include

#include

#include

typedef int ElemType;//数据类型

//定义二叉树结构,与单链表相似,多了一个右孩子结点

typedef struct BiTNode

{

ElemType data;

struct BiTNode *lChild,*rChild;

}BiTNode,*BiTree;

//先序创建二叉树

int CreateBiTree(BiTree *T)

{

ElemType ch;

ElemType temp;

scanf(“%d”,&ch);

temp=getchar();

if(ch==-1)

{

*T=NULL;

}

else

{

*T=(BiTree)malloc(sizeof(BiTNode));

if(!(*T))

{

exit(-1);

}

(*T)->data=ch;

printf(“输入%d的左子结点:”,ch);

CreateBiTree(&(*T)->lChild);

printf(“输入%d的右子结点:”,ch);

CreateBiTree(&(*T)->rChild);

}

return 1;

}

//先序遍历二叉树

void TraverseBiTree(BiTree T)

{

if(T==NULL)

{

return;

}

printf(“%d”,T->data);

TraverseBiTree(T->lChild);

TraverseBiTree(T->rChild);

}

//中序遍历二叉树

void InOrderBiTree(BiTree T)

{

if(T==NULL)

{

return;

}

InOrderBiTree(T->lChild);

printf(“%d”,T->data);

InOrderBiTree(T->rChild);

}

//后序遍历二叉树

void PostOrderBiTree(BiTree T)

{

if(T==NULL)

{

return;

}

PostOrderBiTree(T->lChild);

PostOrderBiTree(T->rChild);

printf(“%d”,T->data);

}

//二叉树的深度

int TreeDeep(BiTree T)

{

int deep=0;

if(T)

{

int leftdeep=TreeDeep(T->lChild);

int rightdeep=TreeDeep(T->rChild);

deep=leftdeep>=rightdeep?leftdeep+1:rightdeep+1;

}

return deep;

}

//求二叉树叶子结点个数

int Leafcount(BiTree T,int &num)

{

if(T)

{

if(T->lChild==NULL&&T->rChild==NULL)

{

num++;

}

Leafcount(T->lChild,num);

Leafcount(T->rChild,num);

}

return num;

}

//主函数

int main(void)

{

BiTree T;

BiTree *p=(BiTree *)malloc(sizeof(BiTree));

int deepth,num=0;

printf(“请输入第一个结点的值,-1表示没有叶结点:\n”);

CreateBiTree(&T);

printf(“先序遍历二叉树:\n”);

TraverseBiTree(T);

printf(“\n”);

printf(“中序遍历二叉树:\n”);

InOrderBiTree(T);

printf(“\n”);

printf(“后序遍历二叉树:\n”);

PostOrderBiTree(T);

printf(“\n”);

deepth=TreeDeep(T);

printf(“数的深度为:%d”,deepth);

printf(“\n”);

Leafcount(T,num);

printf(“数的叶子结点个数为:%d”,num);

printf(“\n”);

return 0;

}

得到的结果如下图所示:

58c7ebc54aba24fa21e5218fefa0a4a2.png

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持脚本之家。