【大学数据结构课件】树和二叉树

1、1,内容提要,6.1 树的定义及基本术语 6.2 二叉树 6.3 编历二叉树 6.4 线索二叉树 6.5 二叉排序树 6.6 平衡二叉树 6.7 树和森林 6.8 哈夫曼树及应用,2,6.1 树的定义及基本术语,1、树的定义 (1)树的一般定义 树是包含n个结点的有限集合，在这个集合上定义了一个唯一的关系，这个关系满足下面的条件： I. 存在唯一的一个结点，它没有前驱，称为根 II. 除了根结点外，其它结点有且仅有一个前驱 III. 除了根结点外，任何结点ai(0 im)，都存在唯一 的一个从根到ai的结点序列a0, a1, a2,., am ，其中， a0是根。这个序列称为从根到ai的路径。

2、,3,树的定义及基本术语(contd),(2)树的递归定义 树是包含n个结点的有限集，在这个集合上定义了唯一的关系，它满足下面的条件： I. 有个特定的称为根的结点； II. 当n1时，除了根以外的其余结点根据它们之间 的关系可分为m个不相交的有限集T1,T2,.,Tm，其中，每个有限集都是一棵树。这些树称为根的子树。,T1=b,e,f;T2=c;T3=d,4,树的定义及基本术语(contd),(3)树的基本术语 1. 根,唯一没有前驱的结点 2. 度,结点的度是结点的子树数目,树的度是指结点度的最大值 3. 叶子，度为0的结点，也称终端结点 4. 分枝结点，叶子之外的结点，也称非终端结点。除

3、了根以外的分枝结点又称内部结点。 5. 双亲、子女、祖先、子孙，结点子树的根称为结点的子女，该结点就是它子女的双亲；某结点的祖先是指从根到该结点的路径上的全部结点；结点的子树中全部结点都是该结点的子孙。,5,树的定义及基本术语(contd),(3)树的基本术语 6. 兄弟、堂兄弟，同一个结点的子女互为兄弟，双亲为兄弟的结点互称堂兄弟。 7. 结点的层次、树的深度(高度)，根为第1层，结点的层次是其双亲层次加1。树的深度是指结点的最大层数。 8. 有序树、无序树，如果结点的各子树自左向右是有次序的，则称有序树，否则称无序树 9. 森林，m棵互不相交的树就构成了森林。,6,6.2 二叉树,1. 二

4、叉树的概念 每个结点最多有2棵子树，并且子树有左右之分，不能任意颠倒。 二叉树有5种形态： 空树 只有一个根 只有左子树 只有右子树 有两个子树 2. 二叉树的性质 在二叉树的第i层上至多有2i1个结点(i=1) 深度为k的二叉树至多有2k-1个结点。,7,二叉树(contd),2. 二叉树的性质 设二叉树中，叶结点数为n0,度为1的结点数为n1,度为2的结点数为n2,则有： n0 = n2 + 1 因为 N=n0+n1+n2=1+n1*1+n2*2 具有n个结点的完全二叉树的深度为 log2n +1 log2n 表示 log2n取整 满二叉树：具有最多结点数的二叉树（即一棵深度为k且有2k-

5、1 个结点的二叉树） 完全二叉树：将满二叉树从右向左 删除叶子的结果，因此 , 结点数 n2k-1-1,8,二叉树(contd),2. 二叉树的性质 对于具有n个结点的完全二叉树,将结点按照从上到下从左到右进行编号，则有如下特点： I. i=1则是根，若i1则它的双亲为i/2 II. 如果2in则 i没有左子女，否则它的左子女是2i III.如果2i+1n则 i没有右子女，否则它的右子女是2i1,9,二叉树(contd),3. 二叉树的存储结构 (1) 顺序存储，利用数组按照完全二叉树的方式对结点编号，根据编号将结点存放在数组中相应的位置中。 #define N 50 /二叉树的最大结点数 t

6、ypedef elemtype SQTREEN; /顺序存储的二叉树 SQTREE bt;,10,二叉树(contd),3. 二叉树的存储结构 (2)链式存储，利用二叉链表或三叉链表 typedef struct treenode elemtype data; /结点数据 /指向左右孩子的指针 struct treenode *lchild,*rchild /*,*parent*/; TREENODE,*TREENODEPTR,*BTREE,11,二叉树(contd),4. 二叉树的建立 (1) 按层序遍历顺序为输入顺序,12,二叉树(contd),4.二叉树的建立 (2) 根据广义表字符串建

7、立二叉树,13,二叉树(contd),4.二叉树的建立 (2)根据广义表字符串建立二叉树,14,6.3 遍历二叉树,1. 二叉树的遍历方式 (1) 先序遍历(DLR)，先输出根，再遍历左子树，最后遍历右子树 (2) 中序遍历(LDR)，先遍历左子树，再输出根，最后遍历右子树 (3) 后序遍历(LRD)，先遍历左子树，再遍历右子树，最后输出根,DLR： LDR： LRD：,A,B,D,C,E,A,B,D,C,E,A,B,D,C,E,15,遍历二叉树(contd),2. 二叉树的遍历算法 (1)中序遍历,void inorder(BTREE root) if(root!=NULL) inorder

8、(rootlchild); printf(%d,rootdata); inorder(rootrchild); ,递归算法,16,遍历二叉树(contd),2. 二叉树的遍历算法 (2)先序遍历,void preorder(BTREE root) if(root!=NULL) printf(%d,rootdata); preorder(rootlchild); preorder(rootrchild); ,递归算法,17,遍历二叉树(contd),2. 二叉树的遍历算法 (3)后序遍历,void postorder(BTREE root) if(root!=NULL) postorder(ro

9、otlchild); postorder(rootrchild); printf(%d,rootdata); ,递归算法,18,遍历二叉树(contd),2.二叉树的遍历算法 (4)后序遍历,非递归算法,19,遍历二叉树(contd),2. 二叉树的遍历算法 (4)后序遍历,非递归算法,20,遍历二叉树(contd),2. 二叉树的遍历算法 (5)先序遍历,非递归算法,21,遍历二叉树(contd),2. 二叉树的遍历算法 (6) 层序遍历,自下而上 左右交替 的那种,即栈中栈,22,遍历二叉树(contd),(2)二叉树的遍历算法 (6) 层序遍历,23,遍历二叉树(contd),3. 二叉

10、树遍历算法的应用 (1)求树的深度,int depth(BTREE root) int hr,hl; /记录左右子树的深度 if(!root) return 0;/空树深度为0 else hl=depth(rootlchild); hr=depth(rootrchild); if(hl=hr) return hl+1; else return lr+1; ,24,遍历二叉树(contd),3. 二叉树遍历算法的应用 (2)求二叉树叶子结点的个数,25,6.4 线索化二叉树,线索化 遍历二叉树的结果是将二叉树的结点排列成某种顺序，使这些结点形成线性关系。但这种线性关系只能在重新遍历二叉树时才会重

11、新获得。如果在第一次遍历二叉树时就将这种线性关系保存下来，这种操作称为“线索化”。 为了将二叉树线索化，需要重新定义二叉树结点的数据类型。,typedef struct treenode elemtype data; struct treenode *lchild,*rchild; int ltag,rtag; /*ltag为0,lchild指向左孩子，否则指向线索化序列中的前驱；rtag为0, rchild指向右孩子，否则指向线索化序列中的后继*/ TREENODE, *TREENODEPTR;,26,线索化二叉树(contd),0 lchild域指示结点的左孩子 ltag = 1 lchi

12、ld域指示结点的前驱 0 rchild域指示结点的右孩子 rtag = 1 rchild域指示结点的后继 以这种结点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向结点前驱和后继的指针，叫做线索。加上线索的二叉树称之为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。,27,线索化二叉树(contd),2. 线索化算法(以中序线索为例)：,28,线索化二叉树(contd),3. 利用线索遍历二叉树(以中序为例)：,29,6.5 二叉排序树,1.二叉排序树：又称二叉查找树。二叉排序树或者是棵空树，或者是棵具有下面特征的二叉树： (1) 若它的左子树不空，左子树上

13、的所有结点值都小于(大于)根结点值 (2) 若它的右子树不空，右子树上的所有结点值都大于(小于)根结点值 (3) 左右子树也都是二叉排序树,30,二叉排序树(contd),2、二叉排序树的建立算法,31,二叉排序树(contd),3、二叉排序树的查找算法,32,二叉排序树(contd),4、二叉排序树的删除算法,33,二叉排序树(contd),4、二叉排序树的删除算法,34,6.6 平衡二叉树,1、平衡二叉树：AVL树，左右子树的深度差的绝对值不超过1的二叉排序树，并且左右子树也是平衡二叉树。,平衡二叉树,非平衡二叉树,35,平衡二叉树(contd),2、平衡二叉树的平衡调整 当向平衡二叉树插

14、入结点或删除结点时，会导致某棵子树深度的变化，在某些情况下，就会导致平衡二叉树失去平衡。这时就需要对二叉树进行平衡调整。 下面以插入结点为例，平衡调整需要两种旋转操作： 单旋和双旋。 当插入新节点时，AVL树的根与插入位置之间路径上的节点的平衡状态可能会变化。因此，插入完一个新节点后，要沿着通向根的路径回溯，检查各节点的平衡状态，一旦发现不平衡节点，就进行平衡化旋转。这样会将不平衡限制最小范围内，并且通常每插入一个节点最多需要一次调整。,36,平衡二叉树(contd),从发生不平衡的节点开始，沿回溯路径向下取两层节点。 (1) 如果这三个节点成一条直线，则需要采用单旋进行平衡化。左旋是指将线上

15、最左端节点向下旋转，右旋是指将线上最右端节点向下旋转。 (2) 如果这三个节点成一条折线，则需要采用双旋进行平衡化。,37,平衡二叉树(contd),(1) 左单旋的情况,原来的AVL树,插入一结点，A点不平衡,左单旋的结果,void LeftRotate(TREENODEPTR * Ptr) /Ptr是发生不平衡的结点 TREENODEPTR *tmp=(*Ptr)rchild; (*Ptr)rchild=tmplchild; tmplchild=*Ptr;*Ptr=tmp; ,38,平衡二叉树(contd),(2) 右单旋的情况,void RightRotate(TREENODEPTR *

16、 Ptr) TREENODEPTR tmp=(*Ptr)lchild; (*Ptr)lchild=tmprchild; tmprchild=*Ptr; *Ptr=tmp; ,原来的AVL树,插入一结点，A点不平衡,右单旋的结果,39,平衡二叉树(contd),(3) 先左后右双旋的情况,void LeftRightRotate(TREENODEPTR * Ptr) LeftRotate( ,原来的AVL树,插入一结点，A点不平衡,先左旋,再右旋,40,平衡二叉树(contd),(4) 先右后左双旋的情况,void RightLeftRotate(TREENODEPTR * Ptr) Right

17、Rotate( ,原来的AVL树,插入一结点，A点不平衡,先右旋,再左旋,41,6 .向AVL树 插入结点,42,6.7 树和森林,1、树的存储结构 (1) 孩子表示法 (2) 孩子双亲表示法 (3) 双亲表示法 (4) 二叉链表法,43,树和森林(contd),(1) 树的孩子表示法和孩子-双亲表示法 树结点中存放有孩子结点的指针的线性表以及双亲指针。孩子指针线性表可以是顺序表或者链表。,typedef struct CTNode/孩子结点 int child; struct CTNode *next; *ChildPtr; Typedef struct elemtype data; Chi

18、ldPtr firstchild;/孩子链表头指针 CTBox; Typedef struct CTBox nodesN; int n,r; /结点数和根的位置； Ctree;,44,树和森林(contd),(1) 树的孩子表示法和孩子-双亲表示法,(a) 孩子链表,(b) 带双亲的孩子链表,45,树和森林(contd),(2) 树的双亲表示法 树结点数据存放到一个静态链表中，每个结点都保存有双亲结点的下标。 #define N 100 typedef struct PTNode elemtype data; int parent;/ 双亲位置域 PTNode; typedef struct PTNode nodesN; int n; /结点数 Ptree;,数组下标,46,树和森林(contd),(3) 树的二叉链表(孩子兄弟)表示法 与二叉树链式存储结构相同，只不过含义不同： 左指针指向第一个孩子，右指针指向下一个兄弟,typedef struct CSNode int data; struct CSNode *firstchild; struct CSNode *nextsibling; CSNode,*CSTree;,二叉链表表