1、1树树数据结构与算法2引言前述我们所研究的数据结构线性表是线性结构。本章将研究的树型结构是一种动态的，非线性的，可描述结构层次特性的数据结构。这种结构是按分枝关系把信息联系起来的数据组织形式。在日常生活中这种结构是不少见的，如：3家谱图(谱系图)Chang Chang父祖父祖母Chang母外祖父外祖母4行政机构图中央人民政府湖南省湖北省上海市长沙 全省各地市各市、县、区5UNIX文件目录6XML文件结构7树型的网络拓扑结构8编译程序中使用语法树9树型结构小节 客观世界客观世界中广泛存在树结构中广泛存在树结构 树结构也在树结构也在计算科学领域计算科学领域中被广泛的中被广泛的（创造和）应用（创造和
2、）应用以上各例的数据(信息)组织形式，均称为树型结构。当然它与植物树有所不同，(它的根在上，枝在下)10树的定义和基本术语11树的定义 一棵树树(tree)T是由一个或一个以上结点组成的有限集 其中有一个特定的结点R称为T的根结点。 集合(TR)中的其余结点可被划分为n0个互不相交的子集T1，T2，, Tn，其中每个子集本身又是一棵树，并且其相应的根结点R1，R2，, Rn是R的子结点 子集Ti(1in)称为树T的子树子树(subtree)。 子树可如下排序：Ti排在Tj之前，当且仅当i1时，其余结点可分为时，其余结点可分为m (m0)个互个互 不相交的有限集不相交的有限集T1, T2, ,
3、Tm，其中每一其中每一 棵子集本身又是一棵符合本定义的树，棵子集本身又是一棵符合本定义的树， 称为根称为根root的子树。的子树。 数据关系数据关系 R：20 基本操作：基本操作：查查 找找 类类 插插 入入 类类删删 除除 类类21 Root(T) / 求树的根结点求树的根结点 查找类：查找类：Value(T, cur_e) / 求当前结点的元素值求当前结点的元素值 Parent(T, cur_e) / 求当前结点的双亲结点求当前结点的双亲结点LeftChild(T, cur_e) / 求当前结点的最左孩子求当前结点的最左孩子 RightSibling(T, cur_e) / 求当前结点的右
4、兄弟求当前结点的右兄弟TreeEmpty(T) / 判定树是否为空树判定树是否为空树 TreeDepth(T) / 求树的深度求树的深度TraverseTree( T, Visit() ) / 遍历遍历22InitTree(&T) / 初始化置空树初始化置空树 插入类：插入类：CreateTree(&T, definition) / 按定义构造树按定义构造树Assign(T, cur_e, value) / 给当前结点赋值给当前结点赋值InsertChild(&T, &p, i, c) / 将以将以c为根的树插入为结点为根的树插入为结点p的第的第i棵子树棵子树23 ClearTree(&T)
5、/ 将树清空将树清空 删除类：删除类：DestroyTree(&T) / 销毁树的结构销毁树的结构DeleteChild(&T, &p, i) / 删除结点删除结点p的第的第i棵子树棵子树24树结点的ADT/ General tree node ADTtemplate class GTNode public: GTNode(const Elem&); / Constructor GTNode(); / Destructor Elem value(); / Return value bool isLeaf(); / TRUE if is a leaf GTNode* parent(); / Re
6、turn parent GTNode* leftmost_child(); / First child GTNode* right_sibling(); / Right sibling void setValue(Elem&); / Set value void insert_first(GTNode* n); void insert_next(GTNode* n); void remove_first(); / Remove first child void remove_next(); / Remove sibling;25树的ADT/ General tree node ADTtempl
7、ate class GenTree private： void printhelp(GTNode *); /print helper functionpublic: GenTree(); /constructor GenTree(); /Destructor void clear(); /Send nodes to free store GTNode* root(); /Return the root /Combine two subtree Void newroot(Elem&,GTNode*,GTNode*); Void print(); /Print a tree;26二叉树的定义和性质
8、27二叉树Binary Trees二叉树二叉树(binary tree)是结点是结点(node)的有限集的有限集合，这个集合或者为合，这个集合或者为空空(empty)，或者由一或者由一个个根结点根结点(root)以及两棵二叉树组成以及两棵二叉树组成, 这两这两棵二叉树分别称作这个根的棵二叉树分别称作这个根的左子树左子树(left subtree)和右和右子树子树(right subtree) ,这两棵这两棵二叉树分别与根结点相连且彼此不相交二叉树分别与根结点相连且彼此不相交. 2829二叉树的五种基本形态N空树空树只含根结点只含根结点NNNLRR右子树为空树右子树为空树L左子树为空树左子树为空
9、树左右子左右子树均不树均不为空树为空树30二叉树的特性(性质1)：在二叉树中，第i层上的结点数最多为2i1(i1);(归纳法)： 当i=1时，只有一个结点，2i1=20=1(归纳基础)归纳假设：假定对所有的j, 1ji 命题成立，即第j层上结点总数最多为2j1个结点。那么，可以证明 j=i 时命题成立。31归纳步骤：由归纳假设可知，i1层上的结点总数最多为2i2。由于二叉树每个结点的度最大为2，所以第i层上的结点最大数为第i1层上结点最大数的2倍，即2 2i2，从而得证，i层上最大结点数为2i1.32：深度为k的二叉树至多有2k1个结点. (k1)证明：证明：深度为k的二叉树结点最大数为每一层
10、结点最大数之和。由特性一得：122)(111kkiikii层上结点最大数第二叉树的特性(性质2)33：对任一棵二叉树，若叶结点数为n0, 度为2的结点数为n2，则有n0=n2+1 成立证明：证明：设度为1的结点数为n1，则二叉树的结点总数为：n=n0+n1+ n2 (1)二叉树的特性(性质3)34设二叉树的分支总数为B，除根结点外，每一个结点都有一个分支进入，则B=n1 又因为度为1的结点发出一个分支，度为2的结点发出2个分支所以： B=n1+2n2从而得 n=n1+2n2+1 (2)由(1), (2)式得 n0=n2+1 成立.35Full and Complete Binary Trees
11、满满二叉树二叉树(full binary tree)的每一个结点或者是一个的每一个结点或者是一个分支结点，并恰有两个非空子结点；或者是叶结点分支结点，并恰有两个非空子结点；或者是叶结点.完全完全二叉树二叉树(complete binary tree)从根结点起每一从根结点起每一层的结点从左到右连续填充层的结点从左到右连续填充, 除了最下面一层以外除了最下面一层以外其余各层都是满的其余各层都是满的, 并且最下面一层的结点都集中并且最下面一层的结点都集中在该层的最左边在该层的最左边.36：具有n个结点的完全二叉树，其深度为： k=log2n+1证证：根据性质2和完全二叉树的定义，设完全二叉树的深度
12、为k，则 2k1 1 n 2k1深度为k1的完全二叉树的最大结点数深度为k的完全二叉树的最大结点数即2k1 n 2k 于是有k1 log2nk k为整数 k =log2n +1 得证完全二叉树的特性(性质4)37特性五：特性五：如果对一棵有n个结点的完全二叉树(其深度为log2n+1)的结点按层次自上而下，从左至右编号，则对任一编号为i的结点(1in)有 2) 若2in 则结点i的左孩子是编号为2i的结点; 否则结点i无左孩子（结点i为叶子结点）。1) 若i=1, 则该结点为根结点，无双亲，若i1, 则结点i的双亲是编号为i/2 的结点。记为parent(i)= i/2 完全二叉树的特性(性质
13、5)3) 若2i+1n 则结点i的右孩子是结点2i+1; 否则结点i无右孩子。3848925106371结点3211时，其余结点可分为不相交的有限集时，其余结点可分为不相交的有限集 Tl、 Tr，其中每一，其中每一 个子集本身又是一棵符合个子集本身又是一棵符合 本定义的二叉树，称为根本定义的二叉树，称为根root的子树。的子树。 数据关系数据关系 R：48二叉树结点的ADT/ Binary tree node abstract classtemplate class BinNode public: virtual Elem& val() = 0; / Return the nodes elem
14、ent virtual void setVal(const Elem&) = 0; / Set the nodes element virtual BinNode* left() const = 0; / Return the nodes left child virtual void setLeft(BinNode*) = 0; / Set the nodes left child virtual BinNode* right() const = 0; / Return the nodes right child virtual void setRight(BinNode*) = 0; /
15、Set the nodes right child virtual bool isLeaf() = 0; / Return true iff the node is a leaf;49Binary Tree Node Class (1)/ Binary tree node classtemplate class BinNodePtr : public BinNode private: Elem it; / The nodes value BinNodePtr* lc; / Pointer to left child BinNodePtr* rc; / Pointer to right chil
16、dpublic: BinNodePtr() lc = rc = NULL; BinNodePtr(Elem e, BinNodePtr* l =NULL, BinNodePtr* r =NULL) it = e; lc = l; rc = r; 50Binary Tree Node Class (2) Elem& val() return it; void setVal(const Elem& e) it = e; inline BinNode* left() const return lc; void setLeft(BinNode* b) lc = (BinNodePtr*)b; inli
17、ne BinNode* right() const return rc; void setRight(BinNode* b) rc = (BinNodePtr*)b; bool isLeaf() return (lc = NULL) & (rc = NULL); ;51 二叉树的主要基本操作：二叉树的主要基本操作：查查 找找 类类插插 入入 类类删删 除除 类类52 Root(T); Value(T, e); Parent(T, e); LeftChild(T, e); RightChild(T, e); LeftSibling(T, e); RightSibling(T, e); BiTre
18、eEmpty(T); BiTreeDepth(T); PreOrderTraverse(T, Visit(); InOrderTraverse(T, Visit(); PostOrderTraverse(T, Visit(); LevelOrderTraverse(T, Visit();53 InitBiTree(&T); Assign(T, &e, value); CreateBiTree(&T, definition); InsertChild(T, p, LR, c);54ClearBiTree(&T); DestroyBiTree(&T);DeleteChild(T, p, LR);要
19、点回顾要点回顾 树型结构是一种动态的，非线性的，可描述结构层次特性的数据结构 树ADT的设计，包括树节点ADT和树ADT的设计 二叉树的性质是很重要的56课堂练习课堂练习 定义一个结点的度数定义一个结点的度数（degree）为其非空子为其非空子结点的数目。用结点的数目。用归纳法归纳法证明任何二叉树中度数证明任何二叉树中度数为为2的结点的数目为叶结的结点的数目为叶结点数目减点数目减1. 请下课时，提交你的练习结果给我，谢谢。请下课时，提交你的练习结果给我，谢谢。 并请写好你的学号和姓名。并请写好你的学号和姓名。57课后思考课后思考 你认为二叉树ADT的基本操作中，最基础且重要的操作是什么； 在将来利用二叉树来实现程序时，什么操作你认为是首先要搞清楚的。 从数据结构的角度，你认为掌握二叉树的性质有什么作用请邮件告诉我（）58树的存储结构。 课后预习课后预习
