|
楼主 |
发表于 2018-4-25 10:59:05
|
显示全部楼层
- #include <stdio.h>
- #include <stdlib.h>
- typedef struct BiNode
- {
- char data;
- struct BiNode *lchild,*rchild;
- }BiNode,*BiTree;
- int inittree(BiTree *T) //构造空二叉树
- {
- (*T)=NULL;
- printf("空树构造成功。\n");
- return 0;
- }
- void creattree(BiTree *T) //利用递归先序创建二叉树
- {
- char ch;
- scanf("%c",&ch);
- if(ch=='#')
- (*T)=NULL;
- else
- {
- (*T)=(BiTree)(malloc(sizeof(BiNode)));
- (*T)->data=ch;
- creattree(&(*T)->lchild);
- creattree(&(*T)->rchild);
- }
- }
- void preordertree(BiTree T) //递归先序遍历二叉树
- {
- if(T)
- {
- printf("%c",T->data);
- preordertree(T->lchild);
- preordertree(T->rchild);
- }
- }
- void inordertree(BiTree T) //递归中序遍历二叉树
- {
- if(T)
- {
- inordertree(T->lchild);
- printf("%c",T->data);
- inordertree(T->rchild);
- }
- }
- void postordertree(BiTree T) //递归后续遍历二叉树
- {
- if(T)
- {
- postordertree(T->lchild);
- postordertree(T->rchild);
- printf("%c",T->data);
- }
- }
- int isemptytree(BiTree T) //判断二叉树是否为空二叉树
- {
- if(T==NULL)
- {
- printf("该二叉树为空。\n");
- return 0;
- }
- else
- {
- printf("该二叉树不为空。\n");
- return -1;
- }
- }
- void destroytree(BiTree *T) //递归销毁二叉树,即把包括头的全部节点释放,详见“https://blog.csdn.net/bzhxuexi/article/details/41721429”
- {
- if(*T)
- {
- if((*T)->lchild)
- {
- destroytree(&(*T)->lchild);
- }
- if((*T)->rchild)
- {
- destroytree(&(*T)->rchild);
- }
- free(*T);
- (*T)=NULL; //空指针赋值0;
- }
- }
- int cleartree(BiTree *T) //清空树,即保留头结点,后面全部释放
- {
- if(*T==NULL)
- return 0;
- else
- {
- cleartree(&(*T)->lchild);
- cleartree(&(*T)->rchild);
- free((*T));
- return 1;
- }
- }
- int deeptree(BiTree T) //求二叉树的深度,递归过程详见“https://blog.csdn.net/tackycheng/article/details/6445916”
- {
- int deep=0;
- int ldeep,rdeep; //左子树深度和右子树深度
- if(T==NULL)
- return 0;
- else
- {
- ldeep=deeptree(T->lchild);
- rdeep=deeptree(T->rchild);
- deep=ldeep>=rdeep?ldeep+1:rdeep+1;
- return deep;
- }
- }
- int nodecount(BiTree T)
- {
- int lnode,rnode,node;
- if(T==NULL)
- return 0;
- else
- {
- lnode=nodecount(T->lchild);
- rnode=nodecount(T->rchild);
- return (lnode+rnode+1);
- }
- }
- int leafcount(BiTree T)
- {
- int lleaf,rleaf,leaf; //分别记录左右子树上的叶子结点总数以及叶子结点总数
- leaf=0;
- if(T==NULL)
- return 0;
- else
- {
- lleaf=leafcount(T->lchild);
- rleaf=leafcount(T->rchild);
- if(lleaf==0&&rleaf==0)
- return 1;
- else
- return lleaf+rleaf;
- }
- }
- /*int leafcount(BiTree T)
- {
- int count=0;
- if(T)
- {
- if(T->lchild ==NULL &&T->rchild==NULL)
- count++;
- leafcount(T->lchild);
- leafcount(T->rchild);
- return count;
- }
- }*/
- char root(BiTree T) //若树存在,返回树的根。
- {
- char e;
- if(T==NULL)
- return 0;
- else
- {
- e=T->data;
- return e;
- }
- }
- int main()
- {
- BiTree T;
- int deep;
- printf("请创建一棵二叉树:\n");
- inittree(&T);
- creattree(&T);
- //deep=deeptree(T);
- //printf("二叉树深度为%d\n",deep);
- //deep=nodecount(T);
- //printf("二叉树结点总数为%d\n",deep);
- deep=root(T);
- printf("二叉树根为%c\n",deep);
- //deep=leafcount(T);
- //printf("二叉树叶子结点总数为%d\n",deep);
- //destroytree(&T);
- //isemptytree(T);
- printf("该二叉树的前序遍历结果为:");
- preordertree(T);
- printf("该二叉树的中序遍历结果为:");
- inordertree(T);
- printf("该二叉树的后序遍历结果为:");
- postordertree(T);
- return 0;
- }
复制代码 |
|