《数据结构第六章树与二叉树》由会员分享，可在线阅读，更多相关《数据结构第六章树与二叉树（104页珍藏版）》请在金锄头文库上搜索。
1、树的定义和基本术语 二叉树 (Binary Tree) 二叉树的存储结构 遍历二叉树 (Binary Tree Traversal) 线索化二叉树 (Threaded Binary Tree) 树与森林 (Tree & Forest) 赫夫曼树 (Huffman Tree) 二叉树的计数,第6章 树和二叉树,6.1 树的定义和基本术语,1. 树的定义 树是由n (n 0)个结点组成的有限集合。如果n = 0，称为空树；如果n 0，则: 有一个特定的称之为根(root)的结点，它只有后继，但没有前驱； 除根以外的其它结点划分为m (m 0)个互不相交的有限集合T0, T1, , Tm-1，每个集
2、合本身又是一棵树，并且称之为根的子树(subTree)。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个后继。,结点(node) 结点的度(degree) 分支(branch)结点 叶(leaf)结点 孩子(child)结点 双亲(parent)结点,兄弟(sibling)结点 祖先(ancestor)结点 子孙(descendant)结点 结点所处层次(level) 树的深度(depth) 树的度(degree),有序树无序树森林,1）度（次数、级）（1）结点的度：一个结点所拥有的子数的个数（2）树的度：树内各结点的度的最大值 2）描述上下及左右的关系孩子结点：一个结点的子树的根双亲
3、结点： P120兄弟结点：同一个双亲的孩子之间互称兄弟祖先：结点的祖先是从根到该结点所经分支上的所有结点子孙：P120结点的后代 3）层次（1）结点的层次（2）树的深度（高度）,2. 树的基本术语,树的基本操作：p119 树的建立和遍历重点,树的抽象数据类型,6.2 二叉树 (Binary Tree),二叉树的定义,二叉树的五种不同形态,一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。 特点：1）每个结点的度2；2）是有序树,基本操作：p121p123 二叉树的建立和遍历,二叉树的抽象数据类型,性质1 若二叉树的层次从1
4、开始, 则在二叉树的第 i 层最多有 2i-1个结点。(i 1)证明用数学归纳法 性质2 深度为k的二叉树最多有 2k-1个结点。 (k 1)证明用求等比级数前k项和的公式 性质3 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2, 则有n0n21,二叉树的性质,证明：若设度为1的结点有n1个，总结点个数为n，总边数为e，则根据二叉树的定义，n = n0 + n1 + n2 e = 2n2 + n1 = n - 1 因此，有 2n2 + n1 = n0 + n1 + n2 - 1n2 = n0 - 1 n0 = n2 + 1 同理： 三次树： n0=1+n2+2n3
5、 四次树： n0=1+n2+2n3+3n4 K次树： n0=1+n2+2n3+(k-1)nk,定义1 满二叉树(Full Binary Tree) 定义2 完全二叉树(Complete Binary Tree)若设二叉树的深度为h，则共有h层。除第h层外，其它各层(0h-1)的结点数都达到最大个数，第h层从右向左连续缺若干结点，这就是完全二叉树。,性质4 具有n个结点的完全二叉树的深度为log2n +1 证明：设完全二叉树的深度为k，则有2k-1 - 1 n 2k - 1 2k-1 n 2k取对数 k-1 log2n 1, 则 i 的双亲为i /2若2*i n, 则 i 的左孩子为2*i，否则
6、无左孩子若2*i+1 n, 则 i 的右孩子为2*i+1，否则无右孩子若 i 为偶数, 且i != n, 则其右兄弟为i+1若 i 为奇数, 且i != 1, 则其左兄弟为i-1i 所在层次为 log2 i +1,完全二叉树的数组表示 一般二叉树的数组表示,二叉树的存储结构,1. 顺序存储结构（数组表示）,#define MAX_TREE_SIZE 100 typedef TElemType SqBiTreeMAX_TREE_SIZE; SqBiTree bt;,由于一般二叉树必须仿照完全二叉树那样存储，可能会浪费很多存储空间，单支树就是一个极端情况。,单支树,2.链式存储结构,typedef
7、 struct BiTNode /二叉链表的定义 TElemType data; Struct BiTNode *lchild,*rchild; BiTNode, *BiTree;,二叉树链表表示的示例,3. 静态二叉链表和静态三叉链表,预先开辟空间，用数组表示 leftChild, rightChild数组元素的下标,6.3 遍历二叉树 (Traversing Binary Tree) p128,所谓树的遍历，就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。遍历的结果：产生一个关于结点的线性序列。设访问根结点记作 D遍历根的左子树记作 L遍历根的右子树记作 R则可能的遍历次序
8、有先序 DLR DRL 逆先序中序 LDR RDL 逆中序后序 LRD RLD 逆后序,先序遍历 (Preorder Traversal),先序遍历二叉树算法的框架是 若二叉树为空，则空操作； 否则 访问根结点 (D)； 先序遍历左子树 (L)； 先序遍历右子树 (R)。,遍历结果（前缀表达式） - + a * b - c d / e f,在波兰式中，自左到右依次扫描：连续出现2个操作数时，将其前面的运算符退出，对该两操作数进行这两个操作数前面的运算符的运算，运算的中间结果进栈，然后再进行上述的操作。,先序遍历二叉树的递归算法void PreOrderTraverse(BiTree T)if
9、(T)printf(“%c“,T-data);PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild); ,中序遍历二叉树算法的框架是： 若二叉树为空，则空操作； 否则 中序遍历左子树 (L)； 访问根结点 (D)； 中序遍历右子树 (R)。遍历结果（中缀表达式）a + b * c - d - e / f,中序遍历 (Inorder Traversal),表达式语法树,中序遍历二叉树的递归算法void InOrderTraverse(BiTree T)if (T) InOrderTraverse(T-lchild);printf(“%c“,T-
10、data);InOrderTraverse(T-rchild); ,后序遍历 (Postorder Traversal),后序遍历二叉树算法的框架是 若二叉树为空，则空操作； 否则 后序遍历左子树 (L)； 后序遍历右子树 (R)； 访问根结点 (D)。,在逆波兰式中，自左到右依次扫描：是操作数，则依次进栈；遇到运算符。则退出两个操作数，对该两操作数进行该运算符的运算，运算的中间结果进栈；然后再继续重复上述的操作。,遍历结果（后缀表达式） a b c d - * + e f / -,后序遍历二叉树的递归算法void PostOrderTraverse(BiTree T)if (T) PostO
11、rderTraverse(T-lchild);PostOrderTraverse(T-rchild);printf(“%c“,T-data); ,由二叉树的先序序列和中序序列可唯一地确定一棵二叉树。例, 先序序列 ABHFDECKG 和中序序列 HBDFAEKCG , 构造二叉树过程如下：,遍历二叉树的非递归算法,先序遍历：算法1，将右子树根结点 入栈，(栈所需最大容量为n/2+1)；算法2将根结点入栈 中序遍历：在遍历左子树之前，先把根结点入栈，当左子树遍历结束后，从栈中弹出，访问，再遍历右子树 后序遍历：1）设定一个指针，指向 最近访问过的结点。在退栈取出根结点时，需判断：若根结点的右子树
12、为空，或它的右子树非空，但已遍历完毕，即它的右子树根结点恰好是最近一次访问过的结点时，应该遍历该根结点。反之，该根结点应重新入栈，先遍历它的右子树。2）还可同时设定一个标记，指示该根结点是第一次还是第二次入栈,需用到栈，顺序栈的定义如下： typedef BiTNode* SElemType; typedef structSElemType *base;SElemType *top;int stacksize; SqStack;,先序遍历的非递归算法void preorder(BiTree T) SqStack S; BiTree P=T;InitStack(S); Push(S,NULL);
13、while (P) printf(“%c“,P-data);if (P-rchild)Push(S,P-rchild);if (P-lchild)P=P-lchild;else Pop(S,P);,先序遍历的非递归算法2void preorder(BiTree T)int top=0;BiTree stack20, P=T;do while (P)printf(“%c“,P-data);stacktop=P; top+;P=P-lchild; if (top)top-; P=stacktop;P=P-rchild;while (top | P); ,中序遍历的非递归算法1void inorde
14、r(BiTree T)SqStack S; BiTree P=T;InitStack(S);do while(P) * (S.top) = P; S.top+;P=P-lchild; if (S.top)S.top-; P=*(S.top);printf(“%c“,P-data);P=P-rchild;while(S.top!=S.base) | P); ,中序遍历的非递归算法2（p131算法6.3)void inorder(BiTree T) SqStack S; BiTree P=T;InitStack(S);while( P | !Empty(S) if (P) Push(S,P);P=
15、P-lchild; else Pop(S,P);printf(“%c“,P-data);P=P-rchild;,后序遍历时，每遇到一个结点，先把它推入栈中，让PopTim=0。在遍历其左子树前，改结点的PopTim=1，将其左孩子推入栈中。在遍历完左子树后，还不能访问该结点，必须继续遍历右子树，此时改结点的PopTim=2，并把其右孩子推入栈中。在遍历完右子树后，结点才退栈访问。,后序遍历的非递归算法1void Postorder(BiTree T) BiTree p=T,q=NULL;SqStack S; InitStack(S); Push(S,p);while (!StackEmpty(S) if (p ,后序遍历的非递归算法2void postorder(BiTree T) BiTree P=T,q; int flag; SqStack S; InitStack(S);do while (P) *(S.top)=P;S.top+;P=P-lchild;q=NULL; flag=1;while (S.top!=S.base) ,
