数据结构_树

数据结构_树

 

一、树的定义

 

    （1）有且仅有一个根节点；

    （2）当结点个数大于1时，其余节点可分为互不相交的子树。 递归定义

 

   概念：

       结点的度 ：节点拥有的子树数；

       叶子（终端）结点 ：度为0的结点

       树的度 ：树内各结点度的最大值

       孩子 ：结点的子树的根，对应 双亲，兄弟，祖先，子孙，堂兄弟

       深度 ：树中结点的最大层次

       有序树 ：树中结点的各子树看成是从左到右是有次序的，不能互换。反之为无序树。

 

二、森林

    互不相交的树的集合。

 

三、二叉树

 

 树的度小于等于2的树

 

 满二叉树：除叶子节点外，其他结点的度都为2的二叉树。2^K-1个结点，k为深度

 

完全二叉树：对于深度为K的，有N个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点

 

 性质：

  (1) 在二叉树中，第i层的结点总数不超过2^(i-1)；

  (2) 深度为h的二叉树最多有(2^h)-1个结点(h>=1)，最少有h个结点； 　　

  (3) 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1； 　　

  (4) 具有n个结点的完全二叉树的深度为int（log2n）+1 　　

  (5)有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系： 　　

      若I为结点编号则 如果I<>1，则其父结点的编号为I/2； 　　

      如果2*I<=N，则其左儿子（即左子树的根结点）的编号为2*I；若2*I>N，则无左儿子； 　　

      如果2*I+1<=N，则其右儿子的结点编号为2*I+1；若2*I+1>N，则无右儿子。 　

  (6)给定N个节点，能构成h(N)种不同的二叉树。

 

  存储结构：

  1、顺序存储结构

        利用数组存储，结点在数组中的相对位置蕴含结点间的关系。如tree[i]的双亲为tree[n-1],n为(i+1)/2向下取整

        左孩子tree[2i+1]和tree[2i+2]

        适合完全二叉树，一般二叉树会造成空间的浪费。

 

   2、链式存储结构

       两种实现方式：

         （1）左孩子指针域，数据域，右孩子指针域

         （2）左孩子指针域，数据域，右孩子指针域，父节点指针域    便于找到结点双亲

 

   二叉树的遍历：

        先根序遍历、中根序遍历、后根序遍历