树与二叉树

树与二叉树

一、树
树是n(n>=0)个结点的有限集合。如果n=0则称为空树；如果n>0,那么有且仅有一个根结点。树是非线性的结构。

与树相关的基本概念：
1)结点：一个数据元素及指向其子树的分支；
2)结点的度：结点拥有的子树个数；
3)树的度：树中结点的度的最大值；
4)叶结点：度为0的树；
5)子女：结点子树的根；
6)父亲：与子女结点直接联系的子女的上层；
7)兄弟：同一结点的子女；
8)堂兄弟：同层，但为不同结点的子女；
9)结点层次：从根开始，根为第一层，根的子女为第二层，以此类推；
10)树的深度：书中结点的最大层数
11)森林：m(m>=0)棵互不相交的树。

二、二叉树
一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两个分别称为左子树和右子树的互不相交的二叉树组成。

特点：每个结点之多只有两棵子树。

性质：
1、二叉树的第i层上至多有2的n-1次方个结点(n>=1)
2、深度为k的二叉树至多有2的k次方-1个检点(k>=1)
3、二叉树中，度为0的结点比度为2的结点个数多1

满二叉树——一棵深度为k且有2的k次方-1个结点的二叉树。

完全二叉树——若二叉树的高度为h，除第h层外，其他各层的结点数都达到最大个数，第i层从右往左连续缺若干结点。

遍历二叉树：
1、前序遍历
        先访问跟结点，然后遍历左子树，再遍历右子树。在遍历左子树和右子树的时候，同样先遍历它的根几点再依次遍历左右子树。
void PreOrder(BTreeNode root){
       if(root!=null){
               Visit(root.data);
               PreOrder(root.lChild);
               PreOrder(root.rChild);
       }
}

2、中序遍历
        先遍历左子树，然后访问根结点，再遍历右子树。在遍历左右子树的时候，同样先遍历它们的左子树再访问根结点再遍历右子树。
void InOrder(BTreeNode root){
       if(root!=null){
                InOrder(root.lChild);
                Visit(root.data);
                InOrder(root.rChild);
       }
}

3、后序遍历
        先遍历左子树，然后遍历右子树，再访问根结点。在遍历左右子树的时候，同样先遍历它们的左子树再访问根结点，然后遍历右子树。
void PostOrder(BTreeNode root){
       if(root!=null){
                PostOrder(root.lChild);
                PostOrder(root.rChild);
                Visit(root.data);
       }
}
由此可知，到底是前序还是中序、后序遍历，是指根结点的遍历次序。


树的遍历：
1、按层次遍历：
        若树不空，则自上而下、自左至右访问树中每个结点。
2、深度优先遍历
(1)先根次序遍历：
     当树非空时，访问跟结点，再依次先根遍历根的各子树。
(2)后根次序遍历：
      当树非空时，依次后根遍历分的各子树，在访问根结点。
3、按对应二叉树遍历：
   先将普通书转换为对应的二叉树，再按二叉树的前序、中序、后序遍历方式访问各结点。

树：先根次序遍历 ====对应====> 二叉树：前序遍历
树：后根次序遍历 ====对应====> 二叉树：中序遍历



如有不足欢迎指正！

评论

1 楼 nello 2012-07-31  

妹子这么爱学习 值得肯定