数据结构-叉树.pptVIP

第六章 二叉树和树 6.1二叉树 6.2二叉树遍历 6.3树和森林 6.4树的应用 6.1二叉树 6.1.1二叉树的定义和基本术语 二叉树（binary Tree） n个元素的有限集，或为空集，或含有唯一的根元素，其余元素分成两个互不相交的子集，每个子集本身也是一颗二叉树。分别称为根的左子树、右子树，集合为空的二叉树称空树 二叉树的元素又称结点 左孩子，右孩子，父亲，兄弟，堂兄弟，祖先，子孙 结点的度：子树的个数 叶子结点：左右子树均空的结点；度为零 层次：根的层次为1，层次为k的结点其孩子层次为k+1 二叉树的深度：二叉树中叶子结点的最大层次数 满二叉树（full binary tree）：所有结点度为2，叶子结点在同一层次 完全二叉树（complete binary tree）：深度h，h-1为满二叉树，h层的结点都集中在左侧 二叉树的基本操作 性质1 在二叉树的第i层的结点个数最多 2 (i-1) 性质2 深度为k 的二叉树的最大结点数为2k-1 性质3 任一二叉树T，如果其叶子结点数为n0， 度为2的结点数为n2，则n0=n2+1 n0+n1+n2=n=2n2+n1+1 性质4 具有n个结点的完全二叉树深度为[logn]+1 性质5 如果对一个有n个结点的完全二叉树T的结点按层序（从第一层到第[logn]+1层，层内从左到右）从1开始编号，则对任意一个编号为i(1=i=n)的结点有： 如果i＝1，则该结点是二叉树的根，无双亲；如果i1，，则其双亲结点Parent(i)的编号为[i/2] 如果2in，则编号为i 的结点没有左孩子，为叶子结点；否则其左孩子LChild(i)的编号为2i 如果2i+1n，则编号为i 的结点没有右孩子；否则其右孩子RChild(i)的编号为2i+1 顺序存储结构 Const MAXSIZE＝100 typedef struct{ ElemType *data; int nodenum; }SqBiTree 链式存储结构 二叉链表 包涵data，lchild，rchild三个域，找父亲必须从根开始 三叉链表 包涵data，lchild，rchild，parent四个域，找父亲容易 ????? typedef BiTNode{ ElemType data; struct BiTNode *lchild,*rchild[,*parent]; }BiTNode,*BiTree; 6.2二叉树遍历 6.2.1问题的提出 二叉树遍历 对所有结点进行访问，且仅被访问一次 LDR、LRD、DLR、DRL、RLD、RDL六种次序 先序（根）DLR、中序（根）LDR、后序（根）LRD 例：右图得三种遍历序列 先序遍历：ABDEC 中序遍历：DBEAC 后序遍历：DEBCA 算法6.1 递归实现 void preorder(BiTree T,void (* visit)(BiTree)) 算法6.2 非递归实现 typedef enum {Travel=1,Visit=0} TaskType; typedef struct { BiTree ptr; TaskType task; }SElemType; void InOrder_iter (BiTree BT,void (* visit)(BiTree)) 用栈实现遍历 例6.1 建立二叉树的存储结构－二叉链表 算法6.3 void CreateBiTree(BiTree T) 递归 先序 例6.2求二叉树的深度 递归算法 算法6.4 void BiTreeDepth(BiTree T,int h,int depth)先序 算法6.5 int BiTreeDepth(BiTree T) 后序 例6.3复制二叉树 递归算法 算法6.6 void CopyTree(BiTNode *T) 后序 例6.4求存于二叉树中的数学表达式的值 算法6.7 double Value(BiTree T,float opnd[]) 后序 补充6.1：求一二叉树中所有结点数和叶子结点数 （先序） void Count(BiTree T,int C1, int C2) { if(!T)return; C1++; if(T-lchild==NULL T-rchild==NULL)C2++; count(T-lchild,C1,C2); count(T-rchild,C1,C2); } 在二叉链表的结点中增加两个指针域，分别指向“前驱”和“后继”，该指针称线索。加上线索的二叉树成为线索二叉树 typedef BiTHrNod