数据结构——二叉树的基本操作（不包括还原）

小编没有写主函数，你们需要用什么函数只需要自己写一个主函数调用一下就可以了

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct node //二叉树定义
{
char data;
struct node *lchild , *rchild;
}tree , *stree;

void creat_tree(stree &t)//二叉树的建立
{
if (pre[i++] == ',')
{
t = NULL;
}
else
{
t = (stree)malloc(sizeof (tree));
t->data = pre[i-1];
creat_tree(t->lchild);
creat_tree(t->rchild);
}
}

void inorder(stree &t)//遍历中序的递归实现，可以用非递归实现，需要用到栈的一些知识，为了简洁，可以用C++的STL
{
if (t)
{
inorder(t->lchild);
printf("%c" , t->data);
inorder(t->rchild);
}
}

void postorder(stree &t)//后序的遍历
{
if (t)
{
postorder(t->lchild);
postorder(t->rchild);
printf("%c" , t->data);
}
}

void cengxu(stree &t)层序遍历二叉树，主要的是二叉树的数组形式
{
int in = 0 , out = 0;
tree *temp[1111];
temp[in++] = t;
while(in > out)
{
if(temp[out])
{
printf("%c" , temp[out]->data);
cengxu(temp[out] ->lchild);
cengxu(temp[out]->rchild);
}
out++;
}
}
int countt;
void leave_tree(stree &t)//统计树的叶子节点
{
if (t)
{
if (t->lchild == NULL && t->rchild == NULL)
{
countt++;
}
else
{
leave_tree(t->lchild);
leave_tree(t->rchild);
}
}

}

叶子节点定义：

叶子结点就是度为0的结点就是没有子结点的结点

叶子结点

n0：度为0的结点数，n1:度为1的结点 n2：度为2的结点数。 N是总结点

在二叉树中：

n0=n2+1；

N=n0+n1+n2

int depth_tree(stree &t)
{
if (t == NULL)
{
return 0;
}
int l = depth_tree(t->lchild);
int r = depth_tree(t->rchild);
return l>r?l+1:r+1;
}

二叉树的深度问题：

来自百度知道认证团队 2018-09-25

二叉树结点的度数指该结点所含子树的个数，二叉树结点子树个数最多的那个结点的度为二叉树的度。

二叉树的根结点所在的层数为1，根结点的孩子结点所在的层数为2，以此下去。深度是指所有结点中最深的结点所在的层数。

离散数学

二叉树是一个连通的无环图，并且每一个顶点的度不大于3。有根二叉树还要满足根结点的度不大于2。有了根结点之后，每个顶点定义了唯一的父结点，和最多2个子结点。然而，没有足够的信息来区分左结点和右结点。如果不考虑连通性，允许图中有多个连通分量，这样的结构叫做森林。

遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。

数据结构——二叉树的基本操作（不包括还原）

相关推荐