二叉树是什么意思(最小二叉树是什么意思)-东辰安华知识网

大家好，关于二叉树是什么意思很多朋友都还不太明白，今天小编就来为大家分享关于最小二叉树是什么意思的知识，希望对各位有所帮助！

本文目录

二叉树的实现方式

1.第一类数组实现——空间浪费

用数组root[]存储结点值。

在这种实现当中，对于编号为k的节点，其左子节点的编号为2k，右子节点的编号为2k+1，根节点的编号为1。这种实现易产生巨大的空间浪费，比如对于一个只有一条链的树，假设该树含有31个节点，存储这31个节点却需要开一个2^30的数组，因此该方法较少使用。

2.结构体+指针实现——节省空间

用结构体指针p来表示一个节点，其中p->v表示该节点的权值，p->left和p->right分别指向该节点的左右子节点，初始化全部为NULL.

若需用到该节点，则申请空间，否则视为无子节点！就这样互相联系成一颗结构体指针二叉树！节省空间，但是容易出现指针悬挂或者未知的指针内存错误。

3.第二类数组实现

对于一棵有n个节点树，只需要开一个大小为n的数组，节点按照出现顺序依次编号，这么一来，每个节点的左右节点的编号就无法通过2k，2k+1的形式来直接确定了。

这时就需要数组lch[maxn],rch[maxn]；其中lch[u]表示p节点的左子节点的编号，因此通过p=lch[p]就可以访问到p节点的左子节点，rch[p]的含义同理。

另外，用value[p]表示编号为p节点的权值，如此一来，申请新节点的newnode函数与初始化的newtree函数写法就变得不同了。

二叉树的三种遍历方式

1、先序遍历：按照根节点->左子树->右子树的顺序访问二叉树

2、中序遍历：按照左子树->根节点->右子树的顺序访问二叉树

3、后序遍历：按照左子树->右子树–>根节点的顺序访问二叉树

原理：二叉树是每个结点的度不大于2的树结构。它有五种基本形态：二叉树可以是空集；根可以有空的左子树或右子树；或者左、右子树皆为空。

二叉树的关键字是tree

二叉树里每个结点都有度，即它的子结点数，如果没有子结点度就是0，叶子结点的度就是0。所有结点的度加起来二叉树的度。

二叉树的最小深度为根节点到最近叶子节点的距离。

文章分享结束，二叉树是什么意思和最小二叉树是什么意思的答案你都知道了吗？欢迎再次光临本站哦！