二叉树的概念

学习二叉树的概念之前我们要先明确树的概念树的概念树是一种非线性的数据结构它是由(n0)个有限结点组成具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树它的根朝上而叶子朝下。我们可以从两个角度来定义它递归定义树是nn0个节点的有限集当n 0 时树为空树当n 0 时它满足有且只有一个特定的节点称为根。其余节点可以分为m个互不相交的有限集T1T2…Tm其中每一个集合本身又是一棵树称为根的子树。这个定义完美地体现了树递归的本质图论定义树是一个无环连通的无向图。连通任意两个节点之间都有一条路径。无环图中不存在任何环路。树的相关术语概念结点的度一个结点含有的子树的个数称为该结点的度 如上图A的为6叶结点或终端结点度为0的结点称为叶结点 如上图B、C、H、I…等结点为叶结点非终端结点或分支结点度不为0的结点 如上图D、E、F、G…等结点为分支结点双亲结点或父结点若一个结点含有子结点则这个结点称为其子结点的父结点 如上图A是B的父结点孩子结点或子结点一个结点含有的子树的根结点称为该结点的子结点 如上图B是A的孩子结点兄弟结点具有相同父结点的结点互称为兄弟结点 如上图B、C是兄弟结点树的度一棵树中最大的结点的度称为树的度 如上图树的度为6结点的层次从根开始定义起根为第1层根的子结点为第2层以此类推树的高度或深度树中结点的最大层次 如上图树的高度为4堂兄弟结点双亲在同一层的结点互为堂兄弟如上图H、I互为兄弟结点结点的祖先从根到该结点所经分支上的所有结点如上图A是所有结点的祖先子孙以某结点为根的子树中任一结点都称为该结点的子孙。如上图所有结点都是A的子孙森林由mm0棵互不相交的树的集合称为森林树的表示树结构相对线性表就比较复杂了要存储表示起来就比较麻烦了既要保存值域也要保存结点和结点之间的关系实际中树有很多种表示方式如双亲表示法孩子表示法、孩子双亲表示法以及孩子兄弟表示法 等。我们这里就简单的了解其中最常用的孩子兄弟表示法左孩子右兄弟。typedefintDataTpye;typedefstructTreeNode{DataTpye data;structTreeNode*firstChild;// Left childstructTreeNode*nextSibling;// Right sibling}TreeNode;这种表示法的好处是用任何树都可以用二叉树来表示便于统一处理。例如我们可以用这种结构来构建一个简单的树TreeNode*CreateTree(){TreeNode*root(TreeNode*)malloc(sizeof(TreeNode));root-dataA;root-firstChild(TreeNode*)malloc(sizeof(TreeNode));root-firstChild-dataB;root-firstChild-nextSibling(TreeNode*)malloc(sizeof(TreeNode));root-firstChild-nextSibling-dataC;TreeNode*curroot-firstchild;while(cur){//....curcur-nextparent;}returnroot;}这里的孩子节点始终是第一个孩子无论父亲有多少个节点二叉树概念及结构一颗二叉树是节点的有限集合该集合为空由一个根节点加上两课别称为左子树和右子树的二叉树组成二叉树不存在度大于2的结点二叉树的子树有左右之分次序不能颠倒因此二叉树是有序树 注意对于任意的二叉树都是由以下几种情况复合而成的特殊二叉树满二叉树完全二叉树s满二叉树一个二叉树如果每一个层的结点数都达到最大值则这个二叉树就是满二叉树。也就是 说如果一个二叉树的层数为K且结点总数是则它就是满二叉树。完全二叉树完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对于深度为K 的有n个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对 应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。下图就不是一个完全二叉树二叉树的性质若规定根结点的层数为1则一棵非空二叉树的第i层上最多有2i-1个结点.若规定根结点的层数为1则深度为h的二叉树的最大结点数是2h-1对任何一棵二叉树,如果度为0其叶结点个数为n0, 度为2的分支结点个数为n2,则有n2n01证明 /* * 假设二叉树有N个结点 * 从总结点数角度考虑N n0 n1 n2 ① * * 从边的角度考虑N个结点的任意二叉树总共有N-1条边 * 因为二叉树中每个结点都有双亲根结点没有双亲每个节点向上与其双亲之间存在一条边 * 因此N个结点的二叉树总共有N-1条边 * * 因为度为0的结点没有孩子故度为0的结点不产生边; 度为1的结点只有一个孩子故每个度为1的结 点 * * 产生一条边; 度为2的结点有2个孩子故每个度为2的结点产生两条边所以总边数为 n12*n2 * 故从边的角度考虑N-1 n1 2*n2 ② * 结合① 和 ②得n0 n1 n2 n1 2*n2 - 1 * 即n0 n2 1 */若规定根结点的层数为1具有n个结点的满二叉树的深度hlog2n1 . (ps是log以2 为底n1为对数)对于具有n个结点的完全二叉树如果按照从上至下从左至右的数组顺序对所有结点从0开始编号则对 i于序号为i的结点有若i0i位置结点的双亲序号(i-1)/2i0i为根结点编号无双亲结点若2i1n否则无左孩子若2i2n否则无右孩子