构造二叉链表储存二叉树T
时间: 2023-06-03 22:05:26 浏览: 117
很高兴接受你的问题。关于构造二叉链表储存二叉树T,我们可以用以下代码实现:
```
typedef struct BiTNode{ //定义二叉树结点
int data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
```
上述代码中,定义了具有左右子树指针的二叉树结点。同时声明了一个二叉树类型别名BiTree。
下面是一个构造二叉链表储存二叉树T的示例:
```
void CreateBiTree(BiTree *T){ //构造二叉链表
int ch;
scanf("%d",&ch);
if (ch == 0) {
*T = NULL;
} else {
*T = (BiTree)malloc(sizeof(BiTNode));
(*T)->data = ch;
CreateBiTree(&(*T)->lchild);
CreateBiTree(&(*T)->rchild);
}
}
```
上述代码中,CreateBiTree函数用于通过递归方式构建二叉树结点。如果当前结点值为0,则将指针T赋值为NULL。否则,为当前结点分配内存空间,存储其值,并递归地为其左右子树分配空间。
希望这个回答可以帮助到您。如果您有其他问题,欢迎继续问我。
相关问题
用数据结构c语言编程,构造二叉链表存储二叉树T,三种方式递归遍历T,递归计算T的深度,递归统计T中结点的个数,递归统计T中叶子结点的个数
好的,这是一个关于数据结构的问题,我可以回答。首先,构造二叉链表存储二叉树T可以采用C语言中的结构体来实现。然后,三种方式递归遍历T可以分别采用先序遍历、中序遍历和后序遍历三种方式来实现。递归计算T的深度可以采用以当前节点为根节点的左右子树深度的最大值加1的方式来实现。递归统计T中结点的个数可以采用以当前节点为根节点的左子树节点数加右子树节点数再加1的方式来实现。递归统计T中叶子结点的个数可以采用以当前节点为根节点的左右子树中叶子结点个数之和的方式来实现。
用c语言编程构造二叉链表存储二叉树T以及用三种方式递归遍历T以及递归计算T的深度然后递归统计T中结点的个数以及递归统计T中叶子结点的个数的具体算法
答案:
构造二叉链表存储二叉树T的算法如下:
```
#define ElemType int
typedef struct BiTNode {
ElemType data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
void CreateBiTree(BiTree *T) {
ElemType ch;
scanf("%d", &ch);
if (ch == 0) {
*T = NULL;
} else {
*T = (BiTree)malloc(sizeof(BiTNode));
(*T)->data = ch;
CreateBiTree(&(*T)->lchild);
CreateBiTree(&(*T)->rchild);
}
}
```
三种方式递归遍历二叉树T的算法如下:
前序遍历:
```
void PreOrderTraverse(BiTree T) {
if (T) {
printf("%d ", T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
```
中序遍历:
```
void InOrderTraverse(BiTree T) {
if (T) {
InOrderTraverse(T->lchild);
printf("%d ", T->data);
InOrderTraverse(T->rchild);
}
}
```
后序遍历:
```
void PostOrderTraverse(BiTree T) {
if (T) {
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
printf("%d ", T->data);
}
}
```
递归计算二叉树T的深度的算法如下:
```
int TreeDepth(BiTree T) {
if (!T) {
return 0;
} else {
int leftDepth = TreeDepth(T->lchild);
int rightDepth = TreeDepth(T->rchild);
return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
}
}
```
递归统计二叉树T中结点的个数的算法如下:
```
int NodeCount(BiTree T) {
if (!T) {
return 0;
} else {
return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
}
}
```
递归统计二叉树T中叶子结点的个数的算法如下:
```
int LeafCount(BiTree T) {
if (!T) {
return 0;
} else if (!T->lchild && !T->rchild) {
return 1;
} else {
return LeafCount(T->lchild) + LeafCount(T->rchild);
}
}
```