软件技术基础姚全珠非线性数据结构(绝对免费!供大家学习).pptVIP

第三章 非线性数据结构 计算机软件基础 三种特殊二叉树之间的关系 满二叉树 完全二叉树 平衡二叉树 ? ? ? ? 计算机软件基础 4. 二叉树的存储 （1）顺序存储结构 实现方法：二叉树的顺序存储结构是用一组地址连续的存储单元依次（从上到下，从左到右）存放二叉树中的各个结点的数据信息，借助于各个结点在存储结构中存放的相对位置来反映其逻辑关系。 适用范围：只适合 完全二叉树 。 ? ? ? ? 计算机软件基础 B C D E F G A I H J 例：对如下完全二叉树进行顺序存储。 A B C D E F G H I J 1 2 3 4 5 6 7 8 9 10 ? ? ? ? 计算机软件基础 思考：如何设法将顺序存储方法扩展应用于一棵非完全二叉树？ A B C D E F G H A B C D E F G H A B C D E F G H 1 2 3 4 5 6 7 8 9 10 11 12 13 14 添加虚结点 ? ? ? ? 计算机软件基础 分析以上采用的存储方法的利弊。 结论： 虽然通过添加虚结点的办法可将一棵普通二叉树构造成一棵完全二叉树并对其进行顺序存储，但这种做法既繁琐，又造成了大量存储空间的浪费，故该方法在实际工作中很少被使用。 ? ? ? ? lchild data rchild 计算机软件基础 （2）链式存储结构 实现方法：二叉树的链式存储结构中最常用的是二叉链表，其结点结构包括三个域，其中一个是数据域，用于存放结点的数据值；另外两个是指针域，分别存放该结点的左孩子和右孩子的地址。除此之外，为了存储根结点的地址，还需设立一个指针变量tree。 ? ? ? ? 计算机软件基础 F ∧ ∧ A B C D ∧ E ∧ ∧ tree G ∧ ∧ H ∧ ∧ A B C D E F H G 例：对如下二叉树采用二叉链表方式进行链式存储。 二叉树示意图 链式存储示意图 ? ? ? ? 计算机软件基础 typedef struct node { datatype data; struct node * lchild,* rchild; }bstree； 二叉链表中结点类型的定义： 注意：datatype在此处代表任意数据类型，实现时应根据结点的实际数据类型用对应的类型标识符代替。 ? ? ? ? 计算机软件基础 5. 二叉树的遍历 遍历是二叉树所有算法中最重要和最基本的算法。 遍历是指按照一定的顺序访问二叉树中的所有结点，使得每个结点都能被访问且仅访问一次。这里所谓的访问有很广的含义，可以是对结点的各种操作，如修改、计算、输出等。 ? ? ? ? 计算机软件基础 （1）先（根）序遍历 具体遍历过程： 若遍历的二叉树不为空，依次执行以下操作： 1）访问根结点； 2）先序访问左子树； 3）先序访问右子树； ? ? ? ? 计算机软件基础 B C D E G F H A A B D C F E G H 例：写出对下面的二叉树进行先序遍历的序列。 先序遍历序列：A B D E G H C F ? ? ? ? 计算机软件基础 先序遍历算法 算法思想： 对一棵非空的二叉树遵循先根再左子树再右子树的顺序依次进行访问。由于对左、右子树的访问和对整棵树的访问都遵循同样的办法，因此可采用递归的方法方便的实现整个遍历过程。 ? ? ? ? 计算机软件基础 算法实现： void preorder (bstree ?p) { if (p!=NULL) { printf(“%5c”,p-data); /*访问根结点*/ preorder(p-lchild); /*先序遍历左子树*/ preorder(p-rchild); /*先序遍历右子树*/ } } ? ? ? ? 计算机软件基础 （2）中（根）序遍历 具体遍历过程： 若遍历的二叉树不为空，依次执行以下操作： 1）