计算机软件基础(自考本科)(1.10).ppt

桂林电子科技大学 GUILIN UNIVERSITY OF ELECTRONIC TECHNOLOGY 桂林电子科技大学 GUILIN UNIVERSITY OF ELECTRONIC TECHNOLOGY 计算机 软件基础 第二篇　数据结构基础 第十章　树和二叉树 一、树（tree） 1. 树的定义 树：是一个具有n（n≥0）个节点的有限集合T。满足以下两个条件： （1） 任意一颗树有且仅有一个特定的根节点（root node）。 （2）除根节点以外，其余节点可以分为m（m ≥0 ）个互不相交的子集T1，T2, … Tm，其中每个子集本身又是一颗树，称为根的子树。 结论：一棵树由若干子树构成，而每一颗子树由若干颗子子树构成。 一、树（tree） 2. 树的表示形式 A B C D E F 自然表示法 集合表示法 A B C E D F 层次表示法 1A 1.1A 1.2B 1.2.1E 1.2.2F 1.3D 一、树（tree） 3. 树的有关名词 （1）节点的度：节点的孩子数。 （2）树的度=树的叉=拥有孩子最多节点的孩子个数 （3）叶子节点=终端节点=没有孩子的节点 （4）双亲节点：指的是这个节点的父亲节点。 （5）树的高度=树的层数 二、二叉树 二叉树：最多具有两个树杈的树。其中，左边的 树杈称为该节点的左子树，右边的树杈称为该节点 的右子树。 2. 二叉树的基本形态：共5种 一个 节点 也没 有 只有 一个 根节 点 只有左子 树 只有右子 树 左、右子 树都有 二、二叉树 3. 二叉树与一般树的区别： 子树有左、右之分（有序树） 不要求子树木顺序（无序树） 树的度≤2 树的度≥0 可以一个根节点都没有（n ≥ 0） 树中至少有一个根节点（n0） 二叉树 一般树 二、二叉树 4. 二叉树的性质 性质1：二叉树的第 i 层上最多有2i-1个节点（i ≥ 1）； 性质2：高度为 k 的二叉树最多有2k-1个节点（k ≥ 1） ； 性质3：任意一颗二叉树中，如果没有孩子的节点个数 为n0，有两个孩子的节点个数为n2，那么n0=n2+1 二、二叉树 5. 二叉树的两种特殊情形： （1）满二叉树：除叶子节点以外，其它节点都有两个 孩子，而且叶子节点位于同一层上的二叉树。 满二叉树 （2）完全二叉树：一个满二叉树的最下层，从右向左 连续缺少n个节点的二叉树。 完全二叉树 注意：深度为k的满二叉树，有2k-1个节点 二、二叉树 例： （2010.4单选）一个深度为 k 的完全二叉树中节点数至少有（ ）。 A 2k B 2k-1 C 2k+1 D 2k-1 二、二叉树 6. 二叉树的存储结构———顺序存储 操作步骤为： step1：现将二叉树变成完全二叉树（给有关节点补 够两个孩子，所补节点为虚拟节点，仅占个空间） step2：将这个完全二叉树中各节点从上到下，逐层 由左向右一次存放到计算机连续空间中。 二、二叉树 例如： 1 2 3 4 5 7 8 9 10 11 12 13 6 a b c d a b c d 13 1 2 3 4 5 6 7 8 9 10 11 12 a b c d 二、二叉树 6. 二叉树的存储结构———链式存储 （1）二叉树链式存储中，每个节点有3个成员（域） data Lchild Rchild Lchild——存放该节点左孩子的地址； Rchild——存放该节点右孩子的地址； data——存放该节点的数据； 二、二叉树 6. 二叉树的存储结构———链式存储 （2）二叉树链式存储类型的定义 struct node { datatype data; struct node *Lchild,*Rchild; }; 三、二叉树的遍历 1. 中序遍历 如果二叉树不为空，则依次执行如下操作： （1）先：中序遍历左子树； （2）再：访问根节点； （3）最后：中序遍历右子树。 根 左子树 右子树 二叉树的遍历：按照一定的顺序访问树中所有节点，而且每个节点仅被访问一次的操作。 三、二叉树的遍历 中序遍历的算法描述 void inorde ( bitree *root) //root为指向根节点的指针 { if ( root != null ) { inorde (root - Lchild); //先遍历左子树 printf (%c, root -data); //然后访问根节点 inorde ( root- Rchild); //最后遍历右子树