、满二叉树

有且仅有一个特定的称为根的结点。

当n1时其余节点可分为mm0个互不相交的有限集T1,T2,…,Tm其中每个集合本身又是一棵树并且称为根的子树。

无序树树中任意节点的子结点之间没有顺序关系这种树称为无序树,也称为自由树有序树树中任意节点的子结点之间有顺序关系这种树称为有序树二叉树每个节点最多含有两个子树的树称为二叉树满二叉树叶节点除外的所有节点均含有两个子树的树被称为满二叉树完全二叉树除最后一层外所有层都是满节点且最后一层缺右边连续节点的二叉树称为完全二叉树哈夫曼树最优二叉树带权路径最短的二叉树称为哈夫曼树或最优二叉树。

定义一棵树的根结点层次为1其他结点的层次是其父节点层次加1。

一棵树中所有结点的层次的最大值称为这棵树的深度。

例如

结点的度结点拥有的子树数目叶子终端结点度为0的结点分支非终端结点度不为0的结点树的度树的各结点度的最大值内部结点除根结点之外的分支结点双亲与孩子结点结点的子树的根称为该结点的孩子该结点称为孩子的双亲兄弟属于同一双亲的孩子结点的祖先从根到该结点所经分支上的所有结点结点的子孙该结点为根的子树中的任一结点结点的层次表示该结点在树中的相对位置。

根为第一层其他的结点依次下推若结点在第L层上则其孩子在第L1层上兄弟节点双亲在同一层的结点互为兄弟节点树的深高度树中结点的最大层次有序树树中各结点的子树从左至右是有次序的不能互换。

否则称为无序树路径长度从树中某结点Ni出发能够“自上而下”通过树中结点到达结点Nj则称Ni到Nj存在一条路径路径长度等于这两个结点之间的分支数树的路径长度从根到每个结点的路径长度之和。

森林是mm≥0棵互不相交的树的集合

由于二叉树的使用在数据结构中更加广泛所以我们以二叉树为主来进行讲解下面介绍一下关于二叉树的基本知识。

二、满二叉树

二叉树中如果所有分支结点都存在左子树和右子树并且所有叶子节点都在同一层上这样的二叉树称为满二叉树。

如图为一颗满二叉树

叶子节点只能出现在最下一层。

非叶子结点的度一定是2。

在同样深度的二叉树中满二叉树的结点个数最多叶子数最多。

设树的深度为i则总结点数为

2^i

对二叉树节点由左至右由上至下的编号如果编号为i的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同则这棵二叉树称为完全二叉树。

如图为一颗完全二叉树

叶子结点只能出现在最下层和次下层。

最下层的叶子结点集中在树的左部。

倒数第二层若存在叶子结点一定在右部连续位置。

如果结点度为1则该结点只有左孩子即没有右子树。

同样结点数目的二叉树完全二叉树深度最小。

满二叉树一定是完全二叉树但反过来不一定成立。

(i≥1)个结点深度为k的二叉树至多有2^k-1个结点(k≥1)对任何一棵二叉树T如果其终端结点数为N0度为2的结点数为N2则N0N21具有n个结点的完全二叉树的深度为[log2(n)]1一棵具有n个结点的完全二叉树又称顺序二叉树对其结点按层从上至下每层从左至右进行1-n的编号则对任一结点i1≤i≤n有若i1则i的双亲是[i/2]若i1则i是根无双亲。

若2i≤n则i的左孩子是2i否则i无左孩子若2i1≤n则i的右孩子是2i1否则i无右孩子

顺序存储结构

二叉树的顺序存储是指用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素即将完全二叉树上编号为i

依据二叉树的性质完全二叉树和满二叉树采用顺序存储比较合适树中结点的序号可以唯一地反映结点之间的逻辑关系这样既能最大可能地节省存储空间又能利用数组元素的下标值确定结点在二叉树中的位置以及结点之间的关系。

但对于一般的二叉树为了让数组下标能反映二叉树中结点之间的逻辑关系只能添加一些并不存在的空结点让其每个结点与完全二叉树上的结点相对照再存储到一维数组的相应分量中。

然而在最坏情况下一个高度为h

且只有h

个结点的单支树却需要占据近2h-1个存储单元。

二叉树的顺序存储结构如图所示其中0表示并不存在的空结点。

链式存储结构

由于顺序储存结构非常不便所以我们通常采用链式存储结构实现二叉树。

链式存储结构通过开辟一块空间节点通过指针储存左孩子、右孩子节点以及数据。

由于顺序结构操作起来并不方便所以我们通常都以链式存储结构通过递归来实现二叉树定义如下

typedef

(BTNode*)malloc(sizeof(BTNode));if

(node

NULL){return;}printf(%d,root-val);PreOrder(root-left);PreOrder(root-right);

中序遍历

NULL){return;}InOrder(root-left);printf(%d

后序遍历

NULL){return;}BackOrder(root-left);BackOrder(root-right);printf(%d

root-val);

NULL){return;}DestoryTree(root-left);DestoryTree(root-right);free(root);

BT*

以上就是对二叉树的介绍以及基本操作的实现各位老爷别忘了给个支持三连