《树的类型定义.》由会员分享，可在线阅读，更多相关《树的类型定义.（162页珍藏版）》请在金锄头文库上搜索。
1、Tree & Binary Tree,树的类型定义,n(n0)个元素的有限集合,基 本 术 语,结点,结点的度,树的度,叶子结点,分支结点,数据元素+若干指向子树的分支,分支的个数,树中所有结点的度的最大值,度为零的结点,度大于零的结点,D,H,I,J,M,(从根到结点的)路径,孩子结点、双亲结点 兄弟结点、堂兄弟结点 祖先结点、子孙结点,由从根到该结点所经分支和结点构成,A,B,C,D,E,F,G,H,I,J,M,K,L,结点的层次,树的深度,A,B,C,D,E,F,G,H,I,J,M,K,L,假设根结点的层次为1，第l 层的结点的子树根结点的层次为l+1,树中叶子结点所在的最大 层次,任何
2、一棵非空树是一个二元组 Tree = （root，F） 其中 root 被称为根结点 F 被称为子树森林,森林,是m（m0）棵互 不相交的树的集合,A,root,B,C,D,E,F,G,H,I,J,M,K,L,F,() 有确定的根 () 树根和子树根之间为有向关系,有向树,有序树,子树之间存在确定的次序关系,无序树,子树之间不存在确定的次序关系,结点(node) 结点的度(degree) 分支(branch)结点 叶(leaf)结点 子女(child)结点 双亲(parent)结点,兄弟(sibling)结点 祖先(ancestor)结点 子孙(descendant)结点 结点所处层次(lev
3、el) 树的高度(depth) 树的度(degree),对比树型结构和线性结构的结构特点,线性结构,树型结构,第一个数据元素 (无前驱),根结点 (无前驱),最后一个数据元素 (无后继),多个叶子结点 (无后继),其它数据元素 (一个前驱、 一个后继),其它数据元素 (一个前驱、 多个后继),树的抽象数据类型定义,数据对象 D,D是具有相同特性的数据元素的集合,1.若D为空集，则称为空树 2.在D中存在唯一的称为根的数据元素 root 3.当n1时，其余结点可分为m (m0)个 互不相交的有限集T1, T2, , Tm，其中 每一棵子集本身又是一棵符合本定义 的树，称为根root的子树,数据关
4、系 R,基本操作,查 找 类,插 入 类,删 除 类,Root(T) / 求树的根结点,查找类,Value(T, cur_e) / 求当前结点的元素值,Parent(T, cur_e) / 求当前结点的双亲结点,LeftChild(T, cur_e) / 求当前结点的最左孩子,RightSibling(T, cur_e) / 求当前结点的右兄弟,TreeEmpty(T) / 判定树是否为空树,TreeDepth(T) / 求树的深度,TraverseTree( T, Visit() ) / 遍历,InitTree(&T) / 初始化置空树,插入类,CreateTree(&T, definiti
5、on) / 按定义构造树,Assign(T, cur_e, value) / 给当前结点赋值,InsertChild(&T, &p, i, c) / 将以c为根的树插入为结点p的第i棵子树,ClearTree(&T) / 将树清空,删除类,DestroyTree(&T) / 销毁树的结构,DeleteChild(&T, &p, i) / 删除结点p的第i棵子树,A,B,C,D,E,F,G,H,I,J,M,K,L,A( B(E, F(K, L), C(G), D(H, I, J(M) ),T1,T3,T2,树根,二叉树的类型定义,二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、
6、互不交叉的二叉树组成,A,B,C,D,E,F,G,H,K,根结点,左子树,右子树,二叉树的五种基本形态,N,空树,只含根结点,N,N,N,L,R,R,右子树为空树,L,左子树为空树,左右子树均不为空树,二叉树的主要基本操作,查 找 类,插 入 类,删 除 类,Root(T) Value(T, e) Parent(T, e) LeftChild(T, e) RightChild(T, e) LeftSibling(T, e) RightSibling(T, e) BiTreeEmpty(T) BiTreeDepth(T),PreOrderTraverse(T, Visit() InOrderTr
7、averse(T, Visit() PostOrderTraverse(T, Visit() LevelOrderTraverse(T, Visit(),InitBiTree(&T) Assign(T, &e, value) CreateBiTree(&T, definition) InsertChild(T, p, LR, c),ClearBiTree(&T) DestroyBiTree(&T) DeleteChild(T, p, LR),完全二叉树 丰满二叉树 排序二叉树 平衡二叉树,二叉树的分类,满二叉树：指的是深度为k且含有2k-1个结点的二叉树,完全二叉树：树中所含的 n 个结点和满
8、二叉树中编号为 1 至 n 的结点一一对应,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,a,b,c,d,e,f,g,h,i,j,二叉树 的重要特性,性 质 1 在二叉树的第i(i1)层上至多有 2i-1 个结点,用归纳法证明 归纳基础 归纳假设 归纳证明,i = 1 层时，只有一个根结点： 2i-1 = 20 = 1,假设对所有的 j，1 j i， 命题成立,二叉树上每个结点至多有两 棵子树，则第 i 层的结点数 2i-2 2 = 2i-1,性 质 2 深度为k（k1）的二叉树上至多 含2k-1 个结点,证明,基于上一条性质，深度为 k 的二 叉树上的结点数至多为
9、20+21+ +2k-1 = 2k-1,性 质 3 对任何一棵二叉树，若它含有n0 个 叶子结点、n2 个度为2的结点，则必存 在关系式：n0 = n2+1,证明,设二叉树上结点总数 n = n0 + n1 + n2 又二叉树上分支总数 b = n1+2n2 而 b = n-1 = n0 + n1 + n2 - 1 由此， n0 = n2 + 1,性 质 4 具有n个结点的完全二叉树的深度 为log2n +1,证明,设完全二叉树的深度为 k 则根据第二条性质得 2k-1 n 2k 即 k-1 log2 n k 因为k只能是整数，因此，k=log2n +1,性 质 5,若对含n个结点的完全二叉树
10、从 上到下且从左至右进行1至n的编号， 则对完全二叉树中任意一个编号为i 的结点：,(1)若i=1，则该结点是二叉树的根， 无双亲，否则，编号为i/2 的 结点为其双亲结点 (2)若2in，则该结点无左孩子，否 则，编号为2i的结点为其左孩子 结点 (3)若2i+1n，则该结点无右孩子结 点，否则，编号为2i+1的结点为 其右孩子结点,树的存储结构,一、广义表表示法 二、双亲表示法 三、孩子表示法 四、孩子兄弟表示法,广义表表示法,树的广义表表示 (结点的utype域没有画出),A,B,C,D,E,F,G,0 A -1 1 B 0 2 C 0 3 D 0 4 E 2 5 F 2 6 G 5,d
11、ata parent,双亲表示法,A,B,C,D,E,F,G,0 A -1 1 B 0 2 C 0 3 D 0 4 E 2 5 F 2 6 G 4,data firstchild,1 2 3,4 5,6,孩子链表表示法,A,B,C,D,E,F,G,A B C E D F G,root,A B C E D F G,孩子兄弟表示法,孩子兄弟表示法,data,firstChild,nextSibling,二叉树的存储结构,二、二叉树的链 式存储表示,一、二叉树的顺 序存储表示,完全二叉树的 一般二叉树的 数组表示 数组表示,顺序存储表示,A,B,C,D,E,F,A B D C E F,0 1 2 3
12、 4 5 6 7 8 9 10 11 12 13,1,4,0,13,2,6,单支树,由于一般二叉树必须仿照完全二叉树那样存储，可能会浪费很多存储空间，单支树就是一个极端情况,A,D,E,B,C,F,root,lchild data rchild,结点结构,二叉链表,链表表示,A,D,E,B,C,F,root,三叉链表,parent lchild data rchild,结点结构,二叉链表的静态结构,森林与二叉树 的转换,森林转化成二叉树 的规则, 若F为空，即n = 0，则 对应的二叉树B为空二叉树 若F不空，则 对应二叉树B的根root(B)是F中第 一棵树T1的根root(T1)，其左子树
13、为 B(T11, T12, , T1m)，其中，T11, T12, , T1m是root(T1)的子树；其右子 树为B(T2, T3, , Tn)，其中，T2, T3, , Tn是除T1外其它树构成的森林,二叉树转换为森林 的规则, 如果B为空，则对应的森林F也为空 如果B非空，则 F中第一棵树T1的根为root；T1的根 的子树森林(T11, T12, , T1m ) 是由 root的左子树LB转换而来，F 除了T1 之外其余的树组成的森林(T2, T3, , Tn )是由root的右子树RB转换而成的 森林,森林与二叉树的转换,二叉树遍历 (Binary Tree Traversal),顺
14、着某一条搜索路径巡访二叉树 中的结点，使得每个结点均被访问一 次，而且仅被访问一次,问题的提出,“访问”的含义可以很广，如：输出结 点的信息等,“遍历”是任何类型均有的操作， 对线性结构而言，只有一条搜索路 径(因为每个结点均只有一个后继)， 故不需要另加讨论。而二叉树是非 线性结构，每个结点有两个后继， 则存在如何遍历即按什么样的搜索 路径遍历的问题,对“二叉树”而言，可以有三条搜索路径,1先上后下的按层次遍历 2先左（子树）后右（子树）的遍历 3先右（子树）后左（子树）的遍历,设 访问根结点 记作 V 遍历根的左子树 记作 L 遍历根的右子树 记作 R 则可能的遍历次序有 前序 VLR 逆前序 VRL 中序 LVR 逆中序 RVL 后序 LRV 逆后序 RLV 层次遍历,前序遍历 (Preorder Traversal),若二叉树为空，则空操作 否则 访问根结点(V) 前序遍历左子树(L) 前序遍历右子树(R) 遍历结果 - + a * b - c d / e f,若二叉树为空，则空操作 否则 中序遍历左子树(L) 访问根结点(V) 中序遍历右子树(R) 遍历结果 a + b *
