二叉树

About二叉树

干货

1、二叉树中仅有一个没有前驱(前件)的节点即树的根,但其有两个后继(后件),分别为左子树与右子树。

2、每一个节点都可有多个后件,成为其的子节点,无后件的节点则称之为叶子节点。

3、一个节点拥有的后件的个数成为该节点的度;所有节点的最大的度成为该树的度。

4、二叉树的深度即位二叉树的最大层数。

5、二叉树是一种非线性结构,二叉树是n(n≥0)个结点的有限集合。n=0的树称为空二叉树,空二叉树无节点,非空二叉树有且只有一个根节点。n>0的二叉树由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。

6、二叉树通常采用链式存储结构,存储节点由数据域与指针域(左指针域和右指针域)组成。二叉树的链式存储结构也称二叉链表,对满二叉树和完全二叉树可按层次进行顺序存储。以二叉链表作为树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和第二个孩子结点。

image-20190204192359833

满二叉树与完全二叉树

一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。 也就是说,如果一个二叉树的层数为K,且结点总数是(2^k) -1 ,则它就是满二叉树;满二叉树在第i层上有2^(i-1)个节点,深度为m的满二叉树共有2^m-1个节点。

满二叉树的节点数的计算公式为:2^h-1(h为其深度)

若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。image-20190204180613465< !–more–>

因此,若一个二叉树为满二叉树,则它一定也为完全二叉树,反之不成立。

二叉树的基本

Nature 1:在二叉树的第k层上最多有2^(k-1)个节点 (k>=1)。

Nature 2:深度为m的二叉树最多共有2^m-1个节点。

Nature 3:对任何一个二叉树,度为0的节点(即叶子节点)总是比度为2的节点多一个。

Nature 4:具有n个节点的二叉树的深度至少为[log2^n]+1(以2为底的n的对数 我不会打orz),且[log2^n]表示其整数部分。

二叉树的遍历

定义:即不重复的访问二叉树的每一个节点,主要针对非空二叉树。其主要遍历方式分为 前序遍历,中序遍历和后序遍历。

三种遍历方式 当二叉树为空时,均执行空操作,否则均按各遍历的遍历顺序依次进行遍历。

style 1:前序遍历是指访问是首先访问根节点,其次访问左子树,再对左子树进行前序遍历,最后前序遍历右子树。

style 2:中序遍历是指访问时首先中序遍历左子树,再访问根节点,最后中序遍历右子树。

style 3:后序遍历是指首先后序遍历左子树,其次后序遍历右子树,最后访问根节点。

以上即为二叉树的三种遍历规则。