数据结构（C语言版）整套课件完整版电子教案.ppt

6.2.3 树的基本运算 1．Initiate(T) 初始化操作，构造一棵空树T。 2．Root(T) 求树T的根结点，返回树T的根结点的地址，若T为 空，则返回空值。 3．Parent(T,x) 求树T中x结点的双亲结点，返回双亲结点的地址，若无双亲，则返回空值。 4．Child(T,x,i) 求树T中x结点的第i个孩子结点。 5．RightSibling(T,x) 求树T中x结点的右兄弟。 6．Insert(T,y,i,x) 将根为x的子树置为树T中y结点的第i个孩子。 7．Delete(T,x,i) 在树T中删除结点x的第i棵子树。 8．Traverse(T) 遍历树T，即按某个次序依次访问树中每一个结点，并使每个结点都被访问且只被访问一次。 9．Clear(T) 将树T清为空树。 6.2.4树的存储结构? 1．双亲表示法 以一组连续的存储单元来存放树中的结点，对一棵树T中的各结点按层次，从上到下、从左到右的顺序进行存储。 每个结点有两个域：一个是data域，存放结点信息；另一个是parent域，用来存放该结点的双亲的在表中的位置(指针)。 特别要指出的是，只有根结点没有双亲，可以将根结点的parent设为-1。如图6-3是一棵树及其双亲表示的存储结构。 图6-3 树及其双亲表示法的存储结构 6.2.4树的存储结构? 2．孩子链表表示法 孩子链表表示法又称为邻接表表示法，是将一个结点所有孩子结点链接形成一个单链表，而树中有若干个结点，因此会形成若干个单链表。 为了查找方便，可在结点中增加一个指针域，指向其孩子链表的表头，每个单链表有一个表头结点，所有表头结点用一个数组来描述。 如图6-4是图6-3(a)所示树的孩子链表表示法示意图。 图6-4 树的孩子链表表示法示意图 6.2.4树的存储结构? 3．孩子兄弟表示法 孩子兄弟表示法又称二叉树表示法，或二叉链表表示法。即以二叉链表作树的存储结构。 链表中每个结点包括三个域，一个是数据域，用来存储结点的数据值，另外两个是指针域，分别指向该结点的第一个孩子结点（即最左边的孩子结点）和下一个兄弟结点（即该结点的右兄弟），分别命名为firstchild域和nextsibling域。 图6-5是图6-3(a)所示树的孩子兄弟表示法示意图。 图6-5 树的孩子兄弟表示法示意图 6.3 二叉树 在有序树中有一类最特殊，也是最重要的树，称为二叉树（Binary Tree）。 二叉树是树型结构中最简单一种，但却有着十分广泛的应用。 许多实际问题抽象出来的数据结构往往可以表示成二叉树的形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树的概念、存储及算法实现显得特别重要。 6.3.1 二叉树的定义 二叉树是有n(n≥0)个结点的有限集合： （1）该集合或者为空(n=0)。 （2）或者由一个根结点及两个不相交的分别称为左子树和右子树的集合组成。 （3）左子树和右子树同样都是二叉树。 二叉树(Binary Tree)是一种树型结构，它的特点是每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。所以，二叉树是特殊的有序树。 6.3.1 二叉树的定义 二叉树的形态 二叉树可以有五种基本形态（依次如图6-6a～e所示）：(a)空二叉树；(b)仅有根结点的二叉树；(c)右子树为空的二叉树；(d)左子树为空的二叉树；(e) 左、右子树均非空的二叉树。 图6-6 二叉树的基本形态 6.3.2 二叉树的基本运算 1．CreatTree(BT)。建立二叉树BT。 2．SetNull(BT)。将二叉树BT置空。 3．TreeEmpty(BT)。判断二叉树BT是否为空。 4．Root(BT)。求二叉树BT的根结点，若二叉树BT非空则返回其根结点，否则返回空。 5．Parent(BT,x)。在二叉树非空的情况下，求在二叉树BT中，结点x的双亲结点，若二叉树BT为空，或者不存在结点x，或者结点x无双亲均返回空。 6．LeftChild(BT,x)。在二叉树BT非空的情况下，返回二叉树BT中x结点的左孩子，若二叉树BT为空，或者不存在结点x，或者结点x无左孩子均返回空。 7．RightChild(BT,x)。在二叉树BT非空的情况下，返回二叉树BT中x结点的右孩子，若二叉树BT为空，或者不存在结点x，或者结点x无右孩子均返回空。 8．LeftSibling(BT,x)。在二叉树BT非空的情况下，返回二叉树BT中x结点的左兄弟，若二叉树BT为空，或者不存在结点x，或者结点x无左兄