第二十讲 遍历二叉树.pptVIP

第 二 十 讲 知 识 点 二叉树的顺序存储结构与链式存储结构 二叉树遍历的概念及三种遍历方法 难 点 二叉树的非递归中序遍历算法 总结： (1) 在二叉树的第i层上至多有2i-1个结点（i=1） (2) 深度为k的二叉树至多有2k-1个结点。 (3) 任一棵二叉树中，叶结点数为n0，度为1 的结点数为n1,度为2的结点数为n2，则有：n0=n2+1 (4) 有n个结点的完全二叉树其深度为： k= ? log2n ?+1 （5）有n个结点的完全二叉树有如下特点： i=1,是树根， 若i1则双亲为i/2(取整)；若2in ，则 i没有左孩子，否则它的左孩子为2i； 若2i+1n 则 i没有右孩子，否则它的右孩子为 2i+1； 6．2．3 二叉树的存储结构 一、顺序存储 把二叉树的所有结点排成一个序列，从树根起，从上至下，每层从左至右给所有结点编号，用一组连续的存储单元存储； 顺序存储有可能对存储空间造成极大浪费，最坏情况下，一个深度为H且只有H个结点的右单支树实际占用了2H-1个结点空间。并且，不利于结点的插入与删除操作。 二、链式存储 1、二叉链表定义 typedef struct treenode { elemtype data; //树中结点的数据值。 struct treenode *lchild, *rchild; //指向树结点的左、右孩子指针 } treeNODE, * treePTR ; 本节主要讨论二叉树的相关操作。 2、三叉链表定义 typedef struct treenode { elemtype data; struct treenode *lchild,*rchild,*parent; //指向树结点的左、右孩子指针和双亲指针 } treeNODE, *treePTR; 6.3 二叉树的遍历 一、遍历的概念 二叉树的遍历(Traversal)是指按一定规律访问二叉树的每个结点，且每个结点只被访问一次。 对二叉树的遍历过程实际是将非线性结构的二叉树中的结点排成一个线性序列的过程。 本节仅讨论链式存储的二叉树的遍历过程。 以L代表左子树、D代表根，R代表右子树，二叉树，遍历方案有： DLR、LDR、LRD，分别称做先序遍历、中序遍历和后序遍历。 二、三种遍历次序的定义 中序（Inorder）遍历 若遍历的二叉树为空，执行空操作；否则 依次执行下列操作： 中序遍历左子树； 访问根结点； 中序遍历右子树。 先序（Preorder）遍历 若遍历的二叉树为空，执行空操作；否 则依次执行下列操作： 访问根结点； 先序遍历左子树； 先序遍历右子树。 后序（Postorder）遍历 若遍历的二叉树为空，执行空操作；否则 依次执行下列操作： 后序遍历左子树； 后序遍历右子树； 访问根结点。 三、二叉树的遍历算法 1、先序遍历的递归算法（P129 算法6.1) Status PreOrder(BiTreeT, status(*Visit)(ElemType) ) {if (T) {if (Visit(T-data)) if (PreOrder (T-lchild, Visit)) if (PreOrder(T-rchild, Visit)) return OK; return ERROR; } else return OK;} 最简单的Visit函数是： Status Print( ElemType e ) { // 输出元素e的值 printf( e ); return OK; } 2、中序遍历的非递归算法1（P130 算法6.2) Status InOrder1 (BiTree T, Status (*Visit)(ElemTp)) {stack S; BiTree p; InitStack(S); Push(S, T); // 根指针进栈 while (!StackEmpty(S)) {while (GetTop(S, p) p) Push(S, p-lchild); // 向左走到尽头 Pop(S, p); // 空指针退栈 if (!StackEmpty(S)) { // 访问结点，向右一步 Pop(S, p); if (!Visit(p-data)) return ERROR;