二叉树的创建遍历以及统计总结点叶子树高值
时间: 2023-04-16 16:05:05 浏览: 52
二叉树的创建可以通过递归方式实现,每次递归创建左右子树。遍历二叉树可以采用前序、中序、后序遍历,也可以采用层次遍历。统计二叉树的总结点数可以通过递归方式实现,每次递归将左右子树的节点数相加。统计二叉树的叶子节点数可以通过递归方式实现,每次递归判断当前节点是否为叶子节点,如果是则计数器加1,否则递归遍历左右子树。计算二叉树的高度可以通过递归方式实现,每次递归将左右子树的高度取最大值并加1。
相关问题
二叉树的遍历的实验结论
根据引用的实验报告,二叉树的遍历分为前序遍历、中序遍历、后序遍历和层次遍历四种方法。其中前序遍历是先访问根节点,再访问左子树,最后访问右子树;中序遍历是先访问左子树,再访问根节点,最后访问右子树;后序遍历是先访问左子树,再访问右子树,最后访问根节点;层次遍历是按照从上到下、从左到右的顺序逐层访问二叉树的节点。在实验中,作者通过对不同二叉树的遍历,得出了以下结论:
1.前序遍历、中序遍历和后序遍历的时间复杂度均为O(n),其中n为二叉树的节点数。
2.层次遍历的时间复杂度也为O(n)。
3.前序遍历、中序遍历和后序遍历的空间复杂度均为O(h),其中h为二叉树的高度。
4.层次遍历的空间复杂度为O(w),其中w为二叉树的宽度。
5.二叉树的深度可以通过递归求解,时间复杂度为O(n),空间复杂度为O(h)。
6.二叉树的叶子节点个数可以通过递归求解,时间复杂度为O(n),空间复杂度为O(h)。
c语言用二叉链实现二叉树的创建、二叉树的先序/中序/后序递归遍历、统计二叉树的高度、统计结点的个数、叶子结点的个数、先序/中序非递归遍历、层序遍历等运算。
好的,下面我来为您介绍一下C语言如何用二叉链表实现二叉树的创建,以及实现二叉树的各种操作。
1. 二叉树的结构体定义
```C
typedef struct BiTNode
{
char data; // 数据域
struct BiTNode *lchild, *rchild; // 左右孩子指针
}BiTNode, *BiTree;
```
2. 二叉树的创建
二叉树的创建可以采用递归的方式,每次递归创建左右子树。
```C
void CreateBiTree(BiTree *T)
{
char ch;
scanf("%c", &ch);
if(ch == '#') // 如果输入的是'#',则表示该节点为空
*T = NULL;
else
{
*T = (BiTree)malloc(sizeof(BiTNode));
(*T)->data = ch;
CreateBiTree(&((*T)->lchild)); // 递归创建左子树
CreateBiTree(&((*T)->rchild)); // 递归创建右子树
}
}
```
3. 二叉树的先序/中序/后序递归遍历
先序遍历:根节点 -> 左子树 -> 右子树
```C
void PreOrderTraverse(BiTree T)
{
if(T != NULL)
{
printf("%c ", T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
```
中序遍历:左子树 -> 根节点 -> 右子树
```C
void InOrderTraverse(BiTree T)
{
if(T != NULL)
{
InOrderTraverse(T->lchild);
printf("%c ", T->data);
InOrderTraverse(T->rchild);
}
}
```
后序遍历:左子树 -> 右子树 -> 根节点
```C
void PostOrderTraverse(BiTree T)
{
if(T != NULL)
{
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
printf("%c ", T->data);
}
}
```
4. 统计二叉树的高度
二叉树的高度可以采用递归的方式,每次递归计算左右子树的高度,并取最大值。
```C
int TreeHeight(BiTree T)
{
int leftHeight, rightHeight;
if(T == NULL)
return 0;
else
{
leftHeight = TreeHeight(T->lchild);
rightHeight = TreeHeight(T->rchild);
return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}
}
```
5. 统计节点的个数
节点的个数可以采用递归的方式,每次递归计算左右子树的节点个数,并加上根节点。
```C
int NodeCount(BiTree T)
{
if(T == NULL)
return 0;
else
return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
}
```
6. 统计叶子节点的个数
叶子节点的个数可以采用递归的方式,如果当前节点是叶子节点,则返回1,否则返回左右子树叶子节点的个数之和。
```C
int LeafCount(BiTree T)
{
if(T == NULL)
return 0;
else if(T->lchild == NULL && T->rchild == NULL)
return 1;
else
return LeafCount(T->lchild) + LeafCount(T->rchild);
}
```
7. 先序/中序非递归遍历
先序非递归遍历可以采用栈的方式,先入根节点,然后依次入栈右子树、左子树。每次出栈打印节点即可。
```C
void PreOrderTraverse2(BiTree T)
{
if(T == NULL)
return;
BiTree p;
Stack stack;
InitStack(&stack);
Push(&stack, T);
while(!StackEmpty(stack))
{
Pop(&stack, &p);
printf("%c ", p->data);
if(p->rchild != NULL)
Push(&stack, p->rchild);
if(p->lchild != NULL)
Push(&stack, p->lchild);
}
}
```
中序非递归遍历可以采用栈的方式,先入根节点和左子树,然后依次入栈右子树。每次出栈打印节点即可。
```C
void InOrderTraverse2(BiTree T)
{
if(T == NULL)
return;
BiTree p;
Stack stack;
InitStack(&stack);
Push(&stack, T);
while(!StackEmpty(stack))
{
while(GetTop(stack, &p) && p != NULL)
Push(&stack, p->lchild);
Pop(&stack, &p);
if(!StackEmpty(stack))
{
Pop(&stack, &p);
printf("%c ", p->data);
Push(&stack, p->rchild);
}
}
}
```
8. 层序遍历
层序遍历可以采用队列的方式,先入根节点,然后依次入队左右子树。每次出队打印节点即可。
```C
void LevelOrderTraverse(BiTree T)
{
if(T == NULL)
return;
BiTree p;
Queue queue;
InitQueue(&queue);
EnQueue(&queue, T);
while(!QueueEmpty(queue))
{
DeQueue(&queue, &p);
printf("%c ", p->data);
if(p->lchild != NULL)
EnQueue(&queue, p->lchild);
if(p->rchild != NULL)
EnQueue(&queue, p->rchild);
}
}
```
以上就是C语言用二叉链表实现二叉树的各种操作的代码实现。