能看所有网站的浏览器,wordpress集成,discuz 与Wordpress,网站怎么添加栏目一、二叉树的概念 1、二叉树的定义 二叉树#xff08; binary tree#xff09;是 n 个结点的有限集合#xff0c;该集合或为空集#xff08;空二叉树#xff09;#xff0c;或由一个根结点与两棵互不相交的#xff0c;称为根结点的左子树、右子树的二叉树构成。 二叉树的…一、二叉树的概念 1、二叉树的定义 二叉树 binary tree是 n 个结点的有限集合该集合或为空集空二叉树或由一个根结点与两棵互不相交的称为根结点的左子树、右子树的二叉树构成。 二叉树的特点是 1每个结点最多有两棵子树故二叉树中不存在度大于 2 的结点。 2二叉树是有序的其次序不能任意颠倒即使树中的某个结点只有一棵子树也要区分它是左子树还是右子树。 二叉树具有以下 5 种基本形态
1、 2、特殊的二叉树 在实际应用中常会用到以下几种特殊的二叉树。 1.斜树 所有的结点都只有左子树的二叉树称为左斜树所有的结点都只有右子树的二叉树称为右斜树,在斜树中每层只有一个结点因此斜树的结点个数与其深度相同. 2.满二叉树 在一棵二叉树中若所有的分支结点都存在左子树和右子树且所有的叶子都在同一层上则称为满二叉树。
其特点是
叶子只能出现在最下一层只有度为 0、度为 2 的结点 由于满二叉树的特性可知满二叉树在同样深度的二叉树中结点个数、叶结点个数最多。 3.完全二叉树 对一棵具 n 个结点的二叉树按层序编号若编号为 i 的结点与同样深度的满二叉树中编号 i 的结点在二叉树中的位置完全相同则称为完全二叉树那么显然有满二叉树是完全二叉树 其特点是 (1)若i ≤ n / 2, 则结点i为分支结点否则为叶子结点。 (2)叶子结点只可能在层次最大的两层上出现。对于最大层次中的叶子结点都依次排列在该层最左边的位置上。 (3)若有度为1的结点则只可能有一个且该结点只有左孩子而无右孩子(重要特征)。 (4)按层序编号后一旦出现某结点(编号为i)为叶子结点或只有左孩子则编号大于i 的结点均为叶子结点。 (5)若n为奇数则每个分支结点都有左孩子和右孩子;若n为偶数则编号最大的分支结点(编号为n / 2 )只有左孩子没有右孩子其余分支结点左、右孩子都有。 简单来说在满二叉树中从最后一个结点开始连续去掉任意个的结点即是一棵完全二叉树 3、二叉树的性质 1.非空二叉树的第 i 层上行最多有 个结点 2.在一棵深度为 k 的二叉树中最多有 个结点最少有 k 个结点
推论深度为 k 且具 个结点的二叉树一定是满二叉树但深度为 k 具有 k 个结点的二叉树不一定是斜树 3.任意一棵树若结点数量为n ,则边的数量为n − 1 。 4.在一棵二叉树中若叶结点个数为 度为 2 结点个数为 那么有 5.具有 n 个结点的完全二叉树的深度为 , 6.对完全二叉树按从上到下、从左到右的顺序依次编号1 , 2,...,n,则有以下关系: (1)若 i1则结点 i 为根节点若 i1则结点 i 的父结点编号为 i / 2,即当i 为偶数时 它是双亲的左孩子;当i为奇数时它是双亲的右孩子。 (2)若2 i ≤ n 时结点i 的左孩子编号为2 i , 否则无左孩子。 (3)若2 i 1 ≤ n 时结点i 的右孩子编号为2 i 1 否则无右孩子。 (4)结点i 所在层次(深度)为 4、二叉树的存储结构 1、顺序存储结构 二叉树的顺序存储结构是用一维数组存储二叉树中的结点并用结点的存储位置表示结点间的逻辑关系父子关系 由于二叉树本身不具有顺序关系因此二叉树的顺序存储结构要解决的关键问题是如何利用数组下标来反映结点间的逻辑关系。 由于完全二叉树中结点的层序编号可以唯一反映结点间的逻辑关系因此对于一般的二叉树可以添加一些不存在的空结点使其成为一棵完全二叉树再利用一维数组存储。 具体步骤为 1、根节点编号为 1 2、若某结点 i 有左孩子则其左孩子编号为 2i 3、若某结点 i 有右孩子则其右孩子编号为 2i1 缺陷顺序存储会造成存储空间的浪费最坏的情况是右斜树一棵深度为 k 的右斜树却要分配 个存储空间。 因此二叉树的顺序存储结构一般仅用于存储完全二叉树。 2、链式存储结构 既然顺序存储适用性不强我们就要考虑链式存储结构。二叉树每个结点最多有两个孩子所以为它设计一个数据域和两个指针域是比较自然的想法我们称这样的链表叫做二叉链表。
lchilddatarchild 其中data是数据域lchild 和rchild都是指针域分别存放指向左孩子和右孩子的指针。 以下是我们的二叉链表的结点结构定义代码。
/*二叉树的二叉链表结点构造定义*/
/*结点结构*/
struct BiTNode{TElemType data; //结点数据BiTNode *lchild, *rchild; //左右孩子指针
} BiTNode, *BiTree; //根结点 容易验证在含有n 个结点的二叉链表中含有n 1 个空链域。 二、遍历二叉树 二叉树的遍历是指从根结点出发按照某种次序依次访问二叉树中所有结点使得每个结点被访问一次且仅被访问一次。
1、先序遍历
先序遍历(PreOrder) 的操作过程如下若二叉树为空则什么也不做否则 1)访问根结点; 2)先序遍历左子树; 3)先序遍历右子树。 2、中序遍历
中序遍历( InOrder)的操作过程如下若二叉树为空则什么也不做否则 1)中序遍历左子树; 2)访问根结点; 3)中序遍历右子树。 3、后序遍历
后序遍历( InOrder)的操作过程如下若二叉树为空则什么也不做否则 1)中序遍历左子树; 2)中序遍历右子树。 3)访问根结点; 三种遍历算法中,递归遍历左、右子树的顺序都是固定的只是访问根结点的顺序不同。不管采用哪种遍历算法每个结点都访问一次且仅访问一次故时间复杂度都是O(n)。在递归遍历中递归工作栈的栈深恰好为树的深度所以在最坏情况下二叉树是有n个结点且深度为n的单支树遍历算法的空间复杂度为O(n)。
