数据结构电子教案深圳大学自动化课件ds05

1、1 1第五章 树与二叉树数据结构电子教案数据结构电子教案殷人昆殷人昆2 2第五章第五章 树与二叉树树与二叉树3 3树和森林的概念树和森林的概念n两种树：自由树与有根树。两种树：自由树与有根树。n自由树自由树：一棵自由树一棵自由树 tf 可定义为一个二元组可定义为一个二元组 tf = (v, e) 其中其中v = v1, ., vn 是由是由 n (n0) 个元素组成个元素组成的有限非空集合，称为顶点集合。的有限非空集合，称为顶点集合。e = (vi, vj) | vi, vj v, 1i, jn 是是n-1个序对的集合，称个序对的集合，称为边集合，为边集合，e 中的元素中的元素 (vi, vj

2、）称为边或分支。）称为边或分支。4 4自由树n有根树有根树：一棵有根树一棵有根树 t，简称为树，它是，简称为树，它是n (n0) 个个结点的有限集合。当结点的有限集合。当n = 0时，时，t 称为空树；称为空树；否则，否则，t 是非空树，记作是非空树，记作 5 5u r 是是一个特定的称为一个特定的称为根根(root)的结点，它只的结点，它只有直接后继，但没有直接前驱；有直接后继，但没有直接前驱；u根以外的其他结点划分为根以外的其他结点划分为 m (m 0) 个互不个互不相交的有限集合相交的有限集合t1, t2, , tm，每个集合又，每个集合又是一棵树，并且称之为是一棵树，并且称之为根的子树

3、根的子树。u每棵子树的根结点有且仅有一个直接前驱，每棵子树的根结点有且仅有一个直接前驱，但可以有但可以有0个或多个直接后继。个或多个直接后继。00n,t,.,t,tr,n,tm216 6树的基本术语树的基本术语n子女子女：若结点的子树非空，结点子树的根即：若结点的子树非空，结点子树的根即为该结点的子女。为该结点的子女。n双亲双亲：若结点有子女，该结点是子女双亲。：若结点有子女，该结点是子女双亲。1层2层4层3层depth= 4dacbijhgfemlkheight= 37 7n兄弟兄弟：同一结点的子女互称为兄弟。：同一结点的子女互称为兄弟。n度度：结点的子女个数即为该结点的度；树中：结点的子女

4、个数即为该结点的度；树中各个结点的度的最大值称为各个结点的度的最大值称为树的度树的度。n分支结点分支结点：度不为：度不为0的结点即为分支结点，的结点即为分支结点，亦称为非终端结点。亦称为非终端结点。n叶结点叶结点：度为：度为0的结点即为叶结点，亦称为的结点即为叶结点，亦称为终端结点。终端结点。n祖先祖先：某结点到根结点的路径上的各个结点：某结点到根结点的路径上的各个结点都是该结点的祖先。都是该结点的祖先。n子孙子孙：某结点的所有下属结点，都是该结点：某结点的所有下属结点，都是该结点的子孙。的子孙。8 8n结点的层次结点的层次：规定根结点在第一层，其子女：规定根结点在第一层，其子女结点的层次等于

5、它的层次加一。以下类推。结点的层次等于它的层次加一。以下类推。n深度深度：结点的深度即为结点的层次；离根最：结点的深度即为结点的层次；离根最远结点的层次即为远结点的层次即为树的深度树的深度。1层2层4层3层depth= 4dacbijhgfemlkheight= 49 9n高度高度：规定叶结点的高度为：规定叶结点的高度为1，其双亲结点，其双亲结点的高度等于它的高度加一。的高度等于它的高度加一。n树的高度树的高度：等于根结点的高度，即根结点所：等于根结点的高度，即根结点所有子女高度的最大值加一。有子女高度的最大值加一。n有序树有序树：树中结点的各棵子树：树中结点的各棵子树 t0, t1, 是有是

6、有次序的，即为有序树。次序的，即为有序树。n无序树无序树：树中结点的各棵子树之间的次序是：树中结点的各棵子树之间的次序是不重要的，可以互相交换位置。不重要的，可以互相交换位置。n森林森林：森林是：森林是m（m0）棵树的集合。）棵树的集合。 1010树的抽象数据类型树的抽象数据类型template class tree /对象对象: 树是由树是由n (0) 个结点组成的有限集合。在个结点组成的有限集合。在/类界面中的类界面中的 position 是树中结点的地址。在顺序是树中结点的地址。在顺序/存储方式下是下标型存储方式下是下标型, 在链表存储方式下是指针在链表存储方式下是指针/型。型。t 是树

7、结点中存放数据的类型是树结点中存放数据的类型, 要求所有结要求所有结/点的数据类型都是一致的。点的数据类型都是一致的。public: tree (); tree (); 11 11 buildroot (const t& value); /建立树的根结点 position firstchild(position p); /返回 p 第一个子女地址, 无子女返回 0 position nextsibling(position p); /返回 p 下一兄弟地址, 若无下一兄弟返回 0 position parent(position p); /返回 p 双亲结点地址, 若 p 为根返回 0

8、 t getdata(position p); /返回结点 p 中存放的值 bool insertchild(position p, t& value); /在结点 p 下插入值为 value 的新子女, 若插 /入失败, 函数返回false, 否则返回true1212 bool deletechild (position p, int i); /删除结点 p 的第 i 个子女及其全部子孙结 /点, 若删除失败, 则返回false, 否则返回true void deletesubtree (position t); /删除以 t 为根结点的子树 bool isempty (); /判树

9、空否, 若空则返回true, 否则返回false void traversal (void (*visit)(position p); /遍历以 p 为根的子树; 1313llrr二叉树二叉树 (binary tree)(binary tree)n二叉树的定义二叉树的定义一棵二叉树是结点的一个有限集合，该集合一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉别称为左子树和右子树的、互不相交的二叉树组成。树组成。1414二叉树的性质二叉树的性质n性质性质1 若二叉树结点的层次从若二叉树结点的层次

10、从 1 开始开始, 则在则在二叉树的第二叉树的第 i 层最多有层最多有 2i-1 个结点。个结点。( i1) 证明用数学归纳法证明用数学归纳法n性质性质2 深度为深度为 k 的二叉树最少有的二叉树最少有 k 个结点，个结点，最多有最多有 2k-1个结点。个结点。( k1 ) 因为每一层最少要有因为每一层最少要有1个结点，因此，最个结点，因此，最少结点数为少结点数为 k。最多结点个数借助性质。最多结点个数借助性质1：用求等比级数前用求等比级数前k项和的公式项和的公式 20 +21 +22 + +2k-1 = 2k-11515n性质性质3 对任何一棵二叉树，如果其叶结点有对任何一棵二叉树，如果其叶

11、结点有 n0 个个, 度为度为 2 的非叶结点有的非叶结点有 n2 个个, 则有则有 n0n21 若设度为若设度为 1 的结点有的结点有 n1 个，总结点数为个，总结点数为n， 总边数为总边数为e，则根据二叉树的定义，则根据二叉树的定义， n = n0+n1+n2 e = 2n2+n1 = n-1 因此，有因此，有 2n2+n1 = n0+n1+n2-1 n2 = n0-1 n0 = n2+1 1616n定义定义1 满二叉树满二叉树 (full binary tree) n定义定义2 完全二叉树完全二叉树 (complete binary tree) 若设二叉树的深度为若设二叉树的深度为 k，

12、则共有，则共有 k 层。除第层。除第 k 层外，其它各层层外，其它各层 (1k-1) 的结点数都达到的结点数都达到最大个数，第最大个数，第k层从右向左连续缺若干结点，层从右向左连续缺若干结点，这就是完全二叉树。这就是完全二叉树。1717n性质性质4 具有具有 n (n0) 个结点的完全二叉树的个结点的完全二叉树的深度为深度为 log2(n+1) 设完全二叉树的深度为设完全二叉树的深度为k，则有，则有 2k-1-1 n 2k-1 变形变形 2k-1 n+12k 取对数取对数 k-1 1, 则则 i 的双亲为的双亲为 i2 若若2*i = n, 则则 i 的左子女为的左子女为 2*i，若若2*i+

13、1 = n, 则则 i 的右子女为的右子女为2*i+1 若若 i 为奇数为奇数, 且且i != 1, 则其左兄弟为则其左兄弟为i-1, 若若 若若 i 为偶数为偶数, 且且i != n, 则其右兄弟为则其右兄弟为i+1123485679101919二叉树的抽象数据类型二叉树的抽象数据类型template class binarytree /对象: 结点的有限集合, 二叉树是有序树public: binarytree ();/构造函数 binarytree (bintreenode *lch, bintreenode *rch, t item); /构造函数, 以item为根, lch和rch为

14、左、右子 /树构造一棵二叉树 int height ();/求树深度或高度 int size ();/求树中结点个数2020 bool isempty ();/判二叉树空否？ bintreenode *parent (bintreenode *t);/求结点 t 的双亲 bintreenode *leftchild (bintreenode *t); /求结点 t 的左子女 bintreenode *rightchild (bintreenode *t);/求结点 t 的右子女 bool insert (t item);/在树中插入新元素 bool remove (t item);/在树中删除

15、元素 bool find (t& item);/判断item是否在树中 bool getdata (t& item);/取得结点数据2121 bintreenode *getroot ();/取根 void preorder (void (*visit) (bintreenode *t);/前序遍历, visit是访问函数 void inorder (void (*visit) (bintreenode *t);/中序遍历, visit是访问函数 void postorder (void (*visit) (bintreenode *t);/后序遍历, (*visit)是访问函

16、数 void levelorder (void (*visit)(bintreenode *t);/层次序遍历, visit是访问函数;2222正则二叉树正则二叉树 理想平衡二叉树理想平衡二叉树满的满的2323完全二叉树 一般二叉树的顺序表示 的顺序表示二叉树的顺序表示二叉树的顺序表示11 2 3 4 5 6 7 8 9 10 141 2 3 4 6 7 8 9 12 1424891056731237648912510 111324241371531极端情形极端情形: 只有右单支的二叉树只有右单支的二叉二叉树结点定义：每个结点有二叉树结点定义：每个结点有3个数据成员，

17、个数据成员，data域存储结点数据，域存储结点数据，leftchild和和rightchild分别存放指向左子女和右子女的指针。分别存放指向左子女和右子女的指针。leftchild data rightchilddataleftchildrightchild二叉链表二叉链表二叉树的链表表示（二叉链表）二叉树的链表表示（二叉链表）2626leftchild data parent rightchildparentdataleftchildrightchild三叉链表三叉链表二叉树的链表表示（三叉链表）二叉树的链表表示（三叉链表）n每个结点增加一个指向双亲的指针每个结点增加一个指向双亲的指针par

18、ent，使得查找双亲也很方便。使得查找双亲也很方便。2727 aaabbbcccdddfffeeerootrootroot二叉树 二叉链表 三叉链表2828abcdferootdata parent leftchild rightchild012345a - -1 1 - -1b 0 2 3c 1 - -1 - -1d 1 4 5e 3 - -1 - -1f 3 - -1 - -12929二叉树的类定义二叉树的类定义template struct bintreenode /二叉树结点类定义 t data; /数据域 bintreenode *leftchild, *rightchild; /左

19、子女、右子女链域 bintreenode () /构造函数 leftchild = null; rightchild = null; bintreenode (t x, bintreenode *l = null, bintreenode *r = null) data = x; leftchild = l; rightchild = r; ;3030template class binarytree /二叉树类定义public: binarytree () : root (null) /构造函数 binarytree (t value) : refvalue(value), root(nul

20、l) /构造函数 binarytree (binarytree& s); /复制构造函数 binarytree () destroy(root); /析构函数 bool isempty () return root = null; /判二叉树空否 int height () return height(root); /求树高度 int size () return size(root); /求结点数3131 bintreenode *parent (bintreenode *current) return (root = null | root = current) ? null :

21、parent (root, current); /返回双亲结点 bintreenode *leftchild (bintreenode *current) return (current != null)？current-leftchild : null; /返回左子女 bintreenode *rightchild (bintreenode *current) return (current != null)？current-rightchild : null; /返回右子女 bintreenode *getroot () const return root; /取根3232 void pr

22、eorder (void (*visit) (bintreenode *t) preorder (root, visit); /前序遍历 void inorder (void (*visit) (bintreenode *t) inorder (root, visit); /中序遍历 void postorder (void (*visit) (bintreenode *t) postorder (root, visit); /后序遍历 void levelorder (void (*visit)(bintreenode *t); /层次序遍历 int insert (const t&

23、 item); /插入新元素 bintreenode *find (t& item) const; /搜索3333protected: bintreenode *root; /二叉树的根指针 t refvalue; /数据输入停止标志 void createbintree (istream& in, bintreenode *& subtree); /从文件读入建树 bool insert (bintreenode *& subtree, t& x); /插入 void destroy (bintreenode *& subtree); /删除

24、bool find (bintreenode *subtree, t& x); /查找3434 bintreenode *copy (bintreenode *node); /复制 int height (bintreenode *subtree); /返回树高度 int size (bintreenode *subtree); /返回结点数 bintreenode *parent (bintreenode * subtree, bintreenode *current); /返回父结点 bintreenode *find (bintreenode * subtree, t&

25、x) const; /搜寻x3535 void traverse (bintreenode *subtree, ostream& out); /遍历输出 void preorder (bintreenode& subtree, void (*visit) (bintreenode *p); /前序遍历 void inorder (bintreenode& subtree, void (*visit) (bintreenode *p); /中序遍历 void postorder (bintreenode& tree, void (*visit) (bintreen

26、ode *p); /后序遍历3636 friend istream& operator (istream& in, binarytree& tree); /重载操作：输入 friend ostream& operator (ostream& out, binarytree& tree); /重载操作：输出;template bintreenode *binarytree:parent (bintreenode *subtree, bintreenode *current) 部分成员函数的实现部分成员函数的实现3737/私有函数: 从结点 subt

27、ree 开始, 搜索结点 t 的双/亲, 若找到则返回双亲结点地址, 否则返回null if (subtree = null) return null; if (subtree-leftchild = current | subtree-rightchild = current ) return subtree;/找到, 返回父结点地址 bintreenode *p; if (p = parent (subtree-leftchild, current) != null) return p; /递归在左子树中搜索 else return parent (subtree-rightchild,

28、current); /递归在左子树中搜索;3838 template void binarytree:destroy (bintreenode * subtree) /私有函数: 删除根为subtree的子树 if (subtree != null) destroy (subtree-leftchild); /删除左子树 destroy (subtree-rightchild); /删除右子树 delete subtree; /删除根结点 ;3939templateistream& operator (istream& in, binarytree& tree) /重载

29、操作: 输入并建立一棵二叉树tree。in是输/入流对象。 createbintree (in, tree.root); /建立二叉树 return in;4040二叉树遍历二叉树遍历n二叉树的遍历就是按某种次序访问树中的结点，二叉树的遍历就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。要求每个结点访问一次且仅访问一次。n设设访问根结点访问根结点记作记作 v 遍历根的左子树遍历根的左子树记作记作 l 遍历根的右子树遍历根的右子树记作记作 rn则可能的遍历次序有则可能的遍历次序有 前序前序 vlr 镜像镜像 vrl 中序中序 lvr 镜像镜像 rvl 后序后序 lrv 镜像镜像

30、rlv4141中序遍历二叉树算法的框架是：中序遍历二叉树算法的框架是：n若二叉树为空，则空操作；若二叉树为空，则空操作；n否则否则u中序遍历左子树中序遍历左子树 (l)；u访问根结点访问根结点 (v)；u中序遍历右子树中序遍历右子树 (r)。遍历结果遍历结果 a + b * c - d - e / f中序遍历中序遍历 (inorder traversal)(inorder traversal)4242二叉树递归的中序遍历算法二叉树递归的中序遍历算法template void binarytree:inorder (bintreenode * subtree, void (*visit) (bi

31、ntreenode *t) if (subtree != null) inorder (subtree-leftchild, visit); /遍历左子树 visit (subtree);/访问根结点 inorder (subtree-rightchild, visit); /遍历右子树 ;4343前序遍历二叉树算法的框架是：前序遍历二叉树算法的框架是：n若二叉树为空，则空操作；若二叉树为空，则空操作；n否则否则u访问根结点访问根结点 (v)；u前序遍历左子树前序遍历左子树 (l)；u前序遍历右子树前序遍历右子树 (r)。遍历结果遍历结果 - + a * b - c d / e f前序遍历前序

32、遍历 (preorder traversal)(preorder traversal)4444二叉树递归的前序遍历算法二叉树递归的前序遍历算法template void binarytree:preorder (bintreenode * subtree, void (*visit) (bintreenode *t) if (subtree != null) visit (subtree);/访问根结点preorder (subtree-leftchild, visit); /遍历左子树preorder (subtree-rightchild, visit); /遍历右子树 ;4545后序遍历

33、二叉树算法的框架是：后序遍历二叉树算法的框架是：n若二叉树为空，则空操作；若二叉树为空，则空操作；n否则否则u后序遍历左子树后序遍历左子树 (l)；u后序遍历右子树后序遍历右子树 (r)；u访问根结点访问根结点 (v)。遍历结果遍历结果 a b c d - * + e f / -后序遍历后序遍历 (postorder traversal)(postorder traversal)4646二叉树递归的后序遍历算法二叉树递归的后序遍历算法template void binarytree:postorder (bintreenode * subtree, void (*visit) (bintree

34、node *t ) if (subtree != null ) postorder (subtree-leftchild, visit); /遍历左子树postorder (subtree-rightchild, visit); /遍历右子树visit (subtree); /访问根结点 ;4747template int binarytree:size (bintreenode * subtree) const /私有函数：利用二叉树后序遍历算法计算二叉/树的结点个数 if (subtree = null) return 0; /空树空树 else return 1+size (subtre

35、e-leftchild) + size (subtree-rightchild);应用二叉树遍历的事例应用二叉树遍历的事例4848template int binarytree:height ( bintreenode * subtree) const /私有函数：利用二叉树后序遍历算法计算二叉二叉/树的高度或深度 if (subtree = null) return 0;/空树高度为0 else int i = height (subtree-leftchild); int j = height (subtree-rightchild); return (i j) ? j+1 : i+1;

36、;4949利用二叉树利用二叉树前序遍历前序遍历建立二叉树建立二叉树n以递归方式建立二叉树。以递归方式建立二叉树。n输入结点值的顺序必须对应二叉树结点前序输入结点值的顺序必须对应二叉树结点前序遍历的顺序。并约定以输入序列中不可能出遍历的顺序。并约定以输入序列中不可能出现的值作为空结点的值以结束递归现的值作为空结点的值以结束递归, 此值在此值在refvalue中。例如用中。例如用“”或用或用“-1”表示字表示字符序列或正整数序列空结点。符序列或正整数序列空结点。5050如图所示的二叉树的前序遍历顺序为如图所示的二叉树的前序遍历顺序为a b c d e g f abcdegf5151 templat

37、e void binarytree:createbintree (ifstream& in, bintreenode *& subtree) /私有函数: 以递归方式建立二叉树。 t item; if ( !in.eof () ) /未读完, 读入并建树 in item; /读入根结点的值 if (item != refvalue) subtree = new bintreenode(item); /建立根结点 if (subtree = null) cerr “存储分配错!” leftchild); /递归建立左子树 createbintree (in, subtree-ri

38、ghtchild); /递归建立右子树 else subtree = null; /封闭指向空子树的指针封闭指向空子树的指针 ;5353cabcdedcc访问访问a进栈进栈c左进左进b访问访问b进栈进栈d左进左进空空退栈退栈d访问访问d左进左进空空退栈退栈c访问访问c左进左进e访问访问e左进左进空空栈空栈空结束结束利用栈的前序遍历非递归算法利用栈的前序遍历非递归算法5454利用栈的前序遍历非递归算法利用栈的前序遍历非递归算法template void binarytree:preorder (void (*visit) (bintreenode *t) ) stackbintreenode*

39、s; bintreenode *p = root; s.push (null); while (p != null) visit(p); /访问结点 if (p-rightchild != null) s.push (p- rightchild); /预留右指针在栈中5555 if (p-leftchild != null) p = p-leftchild;/进左子树 else s.pop(p);/左子树为空 ;template void binarytree:inorder (void (*visit) (bintreenode *t) stackbintreenode* s; 利用栈的中序

40、遍历非递归算法利用栈的中序遍历非递归算法5656acdebaadaa左空左空 退栈退栈访问访问左空左空 退栈退栈访问访问退栈退栈访问访问左空左空ec退栈访问退栈访问cc右空右空 退栈访问退栈访问 栈空结束栈空结束abcde利用栈的中序遍历非递归算法利用栈的中序遍历非递归算法5757 bintreenode *p = root; do while (p != null) /遍历指针向左下移动 s.push (p); /该子树沿途结点进栈 p = p-leftchild; if (!s.isempty() /栈不空时退栈 s.pop (p); visit (p);/退栈, 访问 p = p-rig

41、htchild;/遍历指针进到右子女 while (p != null | !s.isempty ();5858n在后序遍历过程中所用栈的结点定义在后序遍历过程中所用栈的结点定义template struct stknode bintreenode *ptr; /树结点指针 enum tag l, r; /退栈标记 stknode (bintreenode *n = null) : ptr(n), tag(l) /构造函数;ntag = l, 表示从左子树退回还要遍历右子树表示从左子树退回还要遍历右子树; tag = r，表示从右子树退回要访问根结点。，表示从右子树退回要访问根结点。 ptr

42、tagl,r 利用栈的后序遍历非递归算法利用栈的后序遍历非递归算法5959alblalbraldlbraldrbralbralalarelclarerclarclarcrararabcde6060后序遍历的非递归算法后序遍历的非递归算法 template void binarytree:postorder (void (*visit) (bintreenode *t) stackstknode s; stknode w; bintreenode * p = root; /p是遍历指针 do while (p != null) w.ptr = p; w.tag = l; s.push (w);

43、p = p-leftchild; int continue1 = 1; /继续循环标记, 用于r6161 while (continue1 & !s.isempty () s.pop (w); p = w.ptr; switch (w.tag) /判断栈顶的tag标记 case l: w.tag = r; s.push (w); continue1 = 0; p = p-rightchild; break; case r: visit (p); break; while (!s.isempty ();/继续遍历其他结点 cout endl;6262n层次序遍历二叉树就是从根结点开始，按

44、层次层次序遍历二叉树就是从根结点开始，按层次逐层遍历，如图：逐层遍历，如图：遍历顺序遍历顺序abcdef层次序遍历二叉树的算法层次序遍历二叉树的算法6363n这种遍历需要使用一个这种遍历需要使用一个先进先出的队列先进先出的队列，在，在处理上一层时，将其下一层的结点直接进到处理上一层时，将其下一层的结点直接进到队列（的队尾）。在上一层结点遍历完后，队列（的队尾）。在上一层结点遍历完后，下一层结点正好处于队列的队头，可以继续下一层结点正好处于队列的队头，可以继续访问它们。访问它们。n算法是非递归的。算法是非递归的。6464abcdeqa访问访问a, 进队进队qa出队出队访问访问b, 进队进队访问访

45、问c, 进队进队bcqb出队出队访问访问d, 进队进队cdqc出队出队访问访问e, 进队进队deqd出队出队eqe出队出队6565层次序遍历的（非递归）算法层次序遍历的（非递归）算法template void binarytree:levelorder (void (*visit) (bintreenode *t) if (root = null) return; queuebintreenode * q; bintreenode *p = root; visit (p); q.enqueue (p); while (!q.isempty () q.dequeue (p); if (p-lef

46、tchild != null) 6666 visit (p-leftchild); q.enqueue (p-leftchild); if (p-rightchild != null) visit (p-rightchild); q.enqueue (p-rightchild); ;6767二叉树的计数二叉树的计数n二叉树遍历的结果是将一个非线性结构中二叉树遍历的结果是将一个非线性结构中的数据通过访问排列到一个的数据通过访问排列到一个线性序列线性序列中。中。n前序序列：前序序列：a b d c e 特点是第一个访问的特点是第一个访问的a一定是树根，只要左子树非空，后面紧跟一定是树根，只要左子树

47、非空，后面紧跟的的b 一定是根的左子女，一定是根的左子女，n中序序列：中序序列：b d a e c 特点是树特点是树根根 a 把整个中序分成两部分，把整个中序分成两部分， a 左侧子序列是根的左侧子序列是根的左子树左子树上上的结点数据，右侧子序列是根的结点数据，右侧子序列是根的右子树上的结点数据。的右子树上的结点数据。abcde6868n由二叉树的前序序列和中序序列可唯一地确由二叉树的前序序列和中序序列可唯一地确定一棵二叉树。定一棵二叉树。n例例, 前序序列前序序列 a b h f d e c k g 和中序和中序序列序列 h b d f a e k c g , 构造二叉树过构造二叉树过程如下

48、：程如下：hbdfekcgaekcgabhdf6969前序序列前序序列 a b h f d e c k g kcgekcgabhdfekcgabhfdeabhfdeabhfdckg7070n如果前序序列固定不变，给出不同的中序序如果前序序列固定不变，给出不同的中序序列，可得到不同的二叉树。列，可得到不同的二叉树。6123457896123758497171n例如例如, 有有 3 个数据个数据 1, 2, 3 ，可得，可得 5 种不同的种不同的二叉树。它们的前序排列均为二叉树。它们的前序排列均为 123，中序序列，中序序列可能是可能是 321，231，213，132，123。n前序序列为前序序列

49、为 123，中序序列为，中序序列为 312 的二叉树不的二叉树不存在。存在。1231231231231237272有有0个个, 1个个, 2个个, 3个结点的不同二叉树如下个结点的不同二叉树如下b0 =1b1 =1b2 =2b3 =5 b4 =147373!)!(211112nnnnnbcnnn计算具有计算具有n n个结点的不同二叉树的棵数个结点的不同二叉树的棵数1101niininbbb512345641131363cb141234567851141484cb7474线索化二叉树线索化二叉树 (threaded binary tree)(threaded binary tree)n又称为穿线

50、树。又称为穿线树。n通过二叉树的遍历，可将二叉树中所有结点通过二叉树的遍历，可将二叉树中所有结点的数据排列在一个线性序列中，可以找到某的数据排列在一个线性序列中，可以找到某数据在这种排列下它的前驱和后继。数据在这种排列下它的前驱和后继。n希望不必每次都通过遍历找出这样的线性序希望不必每次都通过遍历找出这样的线性序列。只要事先做预处理，列。只要事先做预处理，将某种遍历顺序下将某种遍历顺序下的前驱、后继关系记在树的存储结构中的前驱、后继关系记在树的存储结构中，以，以后就可以高效地找出某结点的前驱、后继。后就可以高效地找出某结点的前驱、后继。7575线索线索 (thread)(thread)增加前驱

51、增加前驱pred指针和后继指针和后继succ指针的二叉树指针的二叉树pred leftchild data rightchild succabcdepredpredpredsuccsuccsuccdaebcrootpredpredpredpredsuccsuccsuccsucc7676n这种设计的缺点是每个结点增加两个指针，这种设计的缺点是每个结点增加两个指针，当结点数很大时存储消耗较大。当结点数很大时存储消耗较大。n改造树结点，将改造树结点，将 pred 指针和指针和 succ 指针压缩指针压缩到到 leftchild 和和 rightchild 的空闲指针中，并的空闲指针中，并增设两个标志

52、增设两个标志 ltag 和和 rtag，指明指针是指示，指明指针是指示子女还是前驱后继。后者称为线索。子女还是前驱后继。后者称为线索。nltag (或或rtag) = 0，表示相应指针指示左子女，表示相应指针指示左子女（或右子女结点）；当（或右子女结点）；当ltag (或或rtag) = 1, 表示表示相应指针为前驱（或后继）线索。相应指针为前驱（或后继）线索。leftchild ltag data rtag rightchild 7777leftchild ltag data rtag rightchild abcdepredpredpredsuccsuccsuccdaebcrootpred

53、predsuccsucc0000111111线索化二叉树及其链表表示线索化二叉树及其链表表示7878线索化二叉树的类定义线索化二叉树的类定义template struct threadnode /线索二叉树的结点类 int ltag, rtag; /线索标志 threadnode *leftchild, *rightchild; /线索或子女指针 t data; /结点数据 threadnode ( const t item) /构造函数 : data(item), leftchild (null), rightchild (null), ltag(0), rtag(0) ;7979templ

54、ate class threadtree /线索化二叉树类protected: threadnode *root;/树的根指针 void createinthread (threadnode *current, threadnode *& pre); /中序遍历建立线索二叉树 threadnode *parent (threadnode *t); /寻找结点t的双亲结点public: threadtree () : root (null) /构造函数8080 void createinthread(); /建立中序线索二叉树 threadnode *first (threadnode

55、*current);/寻找中序下第一个结点 threadnode *last (threadnode *current);/寻找中序下最后一个结点 threadnode *next (threadnode *current);/寻找结点在中序下的后继结点 threadnode *prior (threadnode *current);/寻找结点在中序下的前驱结点 ;8181通过中序遍历建立中序线索化二叉树通过中序遍历建立中序线索化二叉树template void threadtree:createinthread () threadnode *pre = null; /前驱结点指针 if (r

56、oot != null) /非空二叉树, 线索化 createinthread (root, pre); /中序遍历线索化二叉树 pre-rightchild = null; pre-rtag = 1; /后处理中序最后一个结点 ;8282template void threadtree:createinthread (threadnode *current, threadnode *& pre) /通过中序遍历, 对二叉树进行线索化 if (current = null) return; createinthread (current-leftchild, pre);/递归, 左子树

57、线索化 if (current-leftchild = null) /建立当前结点的前驱线索 current-leftchild = pre; current-ltag = 1; 8383 if (pre != null & pre-rightchild = null) /建立前驱结点的后继线索 pre-rightchild = current; pre-rtag = 1; pre = current; /前驱跟上,当前指针向前遍历 createinthread (current-rightchild, pre); /递归, 右子树线索化;84840 a 0 0 b 0 0 c 0 0

58、 d 0 0 e 0 rootpre = nullcurrent85850 a 0 1 b 0 0 c 0 0 d 0 0 e 0 rootpre = nullcurrent86860 a 0 1 b 0 0 c 0 1 d 0 0 e 0 rootprecurrent87870 a 0 1 b 0 0 c 0 1 d 1 0 e 0 rootprecurrent88880 a 0 1 b 0 0 c 0 1 d 1 1 e 0 rootprecurrent89890 a 0 1 b 0 0 c 0 1 d 1 1 e 1 rootprecurrent90900 a 0 1 b 0 0 c 1

59、 1 d 1 1 e 1 rootpre后处理9191if (current-rtag =1) 后继为后继为current-rightchildelse /current-rtag = 0 后继为当前结点右子树后继为当前结点右子树 的中序下的第一个结点的中序下的第一个结点 寻找当前结点在中序寻找当前结点在中序下的后继下的后继abdecfhikgj9292寻找当前结点在中序寻找当前结点在中序下的前驱下的前驱if (current-ltag = 1) 前驱为前驱为current-leftchild else /current-ltag = 0 前驱为当前结点左子树前驱为当前结点左子树 中序下的最后

60、一个结点中序下的最后一个结点 abdecfhikgjl9393在中序线索化二叉树中部分在中序线索化二叉树中部分成员函数的实现成员函数的实现template threadnode * threadtree : first (threadnode * current) /函数返回以*current为根的线索化二叉树中的中/序序列下的第一个结点 threadnode * p = current; while (p-ltag = 0) p = p-leftchild; return p;9494template threadnode * threadtree : next (threadnode * current) /函数返回在线索化二叉树中结点*current在中序/下的后继结点 threadnode *p = current-rightchild; if (current-rtag = 0) return first (p);