当前位置: 首页 > 数据结构&&算法 > 正文

初探二叉树

                                                                               数据结构之初探二叉树

      树的一些基本概念:

               树:N个节点组成的有限集合(N>=0)。

               子树:上一个根节点的孩子,并且也是下一层子树的根节点。

               二叉树:最多只有两个孩子节点的树。

               空树:没有子节点的树。

               非空树:

                     树中至少有一个节点——根。

                     树中各子树是互不相交的集合。

        树的表示方法:

                   嵌套集合表示法,广义表法,凹入表示法。

        树的基本术语:

                   结点:表示树中的元素,包括数据项及若干指向其子树的分支。

                   结点的度:结点拥有的子树个数。

                   叶子结点:度为0的结点。

                   树的度:一颗树中最大的结点度数(子树数)。

   孩子:结点的子树的根称为该结点的孩子(结点)。

                   双亲:孩子结点的上一层结点叫该结点的父节点。

   兄弟:同一双亲的孩子互称兄弟(结点)。

                   结点的层次 :从根节点算起根为第一层。

                   树的深度 :树中结点的最大层次数。

                   堂兄弟:其双亲在同一层的结点互称为堂兄弟

                   结点的祖先:从根节点到该结点所经分支上的所有结点。

                   结点的子孙:以某根节点为根的子树中的任一结点叫之。

                   有序树:树中各结点的子树从左到右有次序(不能互换)。

                     森林:

                                 多棵互不相交的树构成的集合。

                        树


                例如这就是一棵二叉树。

                  二叉树的基本特征:

                          1.每个结点最多只有两棵子树。

                          2.子树有左右之分,其次序不能任意颠倒,是一个有序树。

         二叉树的几个基本性质:

                    一。

在二叉树的第i层上至多有2^(i-1)次方个结点。

     二。

                                深度为k的二叉树上至多含2^k-1个结点。

                     三。

                                 对任何一棵二叉树,若它含有N个叶子节点,N1个度为2的结点,则N=N1+1;

                      四。

                                  具有N个结点的完全二叉树的深度为:

                                          log2N(取整)+1.

                     五。

                                对于含有N个结点的完全二叉树从上到下且从左至右进行1至N的编号,则对完全二叉树中的任意一个编号为i的结点。

                               若i=1,该结点是二叉树的根,无双亲;否则编号为i/2向上取整的结点为其双亲。

                               若2i>n,  则该结点无左孩子,否则编号为2i的结点无右孩子结点,否则,编号为2i+1的结点为其右孩子结点,

                               若2i+1>n,则该结点无右孩子结点,否则编号为2i+1的结点为其右孩子结点。

                 

          满二叉树:

                          指的是深度为K且含有2^(k)-1个结点的二叉树。

           特点:每一层的结点树都是最大结点数

                  性质:第i层上至多有2^(i-1)个结点。

                  性质:深度为K的二叉树至多有2^k-1个结点。

            

         完全二叉树:

                        若一棵二叉树中所含的N个结点与满二叉树中编号为1至N的结点一一对应(编号和位置一一对应)。

                    特点:

                              1.叶子节点只可能在层次最大的两层上出现。

                               2.对任一结点,若其右分支下子孙的最大层次为1.则其左分支下子孙的最大层次必为1或1+1.

                

              下面将附上用二叉链表的方式建立二叉树,并且用#占位,显示先中后三种遍历方式:


                    

版权声明:本文为博主原创文章,未经博主允许不得转载。

]]>

本文固定链接: http://zmrlinux.com/2015/05/12/%e5%88%9d%e6%8e%a2%e4%ba%8c%e5%8f%89%e6%a0%91/ | Kernel & Me

该日志由 root 于2015年05月12日发表在 数据结构&&算法 分类下, 你可以发表评论,并在保留原文地址及作者的情况下引用到你的网站或博客。
原创文章转载请注明: 初探二叉树 | Kernel & Me