二叉树 基本操作
/*二叉树基本操作：
创建，
凹入法输出，
求叶子结点数，
求结点数，
求深度，
根据给定值进行查找*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<conio.h>
typedef struct Tnode
{
int data;
struct Tnode* lchild;
struct Tnode* rchild;
}Tnode,*BiTree;
void creat(BiTree *T);
void disTree(BiTree T,int n,char c);
int leafnum(BiTree T);
int nodenum(BiTree T);
int depth(BiTree T);
BiTree search(BiTree T, int e);
void dis(BiTree T, int n, char c);
int main()
{
BiTree T, p; int e;
printf("输入节点值，以0结束:\n");
creat(&T); printf("创建成功！\n");
printf("凹入表如下;\n");
disTree(T, 8, 'D');
dis(T, 10, 'D');
printf("叶子结点数：%d\n", leafnum(T));
printf("结点数：%d\n", nodenum(T));
printf("深度：%d\n", depth(T));
printf("请输入查询结点的值：");
scanf_s("%d", &e);
p = search(T, e);
if (p==NULL)printf("该节点不存在！\n");
if (p->rchild == NULL && p->lchild == NULL) printf("该节点为叶子结点！\n");
if (!p->lchild && p->rchild) printf("该节点的左孩子不存在，右孩子为%d！\n", p->rchild->data);
if (!p->rchild && p->lchild) printf("该节点的左孩子是%d,右孩子为空！\n", p->lchild->data);
else
printf("该节点的左孩子是%d,右孩子是%d\n", p->lchild->data, p->rchild->data);
}
void creat(BiTree *T)
{
int n;
scanf_s("%d", &n);
if (n == 0) *T = NULL;
else
{
*T=(BiTree)malloc(sizeof(Tnode));
(*T)->data = n;
creat(&((*T)->rchild));
creat(&((*T)->lchild));
}
}
void disTree(BiTree T,int n,char c)
{
int i;
if (T)
{
for (i = 0; i < n+4; i++)
putchar('-');
putchar('+');
printf("%d(%c)\n", T->data, c);
n = n - 1;
disTree(T->lchild, n, 'L');
disTree(T->rchild, n, 'R');
}
}
void dis(BiTree T, int n, char c)
{
int i;
if (T)
{
for (i = 0; i < n; i++)
{
putchar('-');
}
putchar('+');
printf("%d(%c)\n", T->data, c);
dis(T->lchild, n-2, 'L');
dis(T->rchild, n - 2, 'R');
}
}
int leafnum(BiTree T)
{
int l, r;
if (!T) return 0;
if (!T->lchild && !T->rchild) return 1;
else
{
l = leafnum(T->lchild);
r = leafnum(T->rchild);
return(l + r);
}
}
int nodenum(BiTree T)
{
int l, r;
if (!T) return 0;
if (!T->lchild && !T->rchild) return 1;
else
{
l = nodenum(T->lchild);
r = nodenum(T->rchild);
return(l + r+1);
}
}
int depth(BiTree T)
{
int l, r,d;
if (!T) return 0;
if (!T->lchild && !T->rchild) return 1;
else
{
l = depth(T->lchild);
r = depth(T->rchild);
d = l > r ? l : r;
return (d+1);
}
}
BiTree search(BiTree T, int e)
{
if (!T) return NULL;
else
{
if (T->data == e) return T;
else
{
search(T->lchild, e);
search(T->rchild, e);
}
}
}
页:
[1]