Microsoft PowerPoint - 6-.pptx

Size: px

Start display at page:

Download "Microsoft PowerPoint - 6-.pptx"

悦措云
5 years ago
Views:

1 基本概念树的存储结构树的线性表示树的遍历二叉树二叉树的存储表示二叉树的各种遍历线索化二叉树堆计算二叉树的数目二叉树的应用 : 霍夫曼树和霍夫曼编码本章小结

2 6.1 基本概念树是由一个或多个结点组成的有限集 T, 它满足下面两个条件 : 有一个特定的结点, 称之为根结点 ; 其余的结点分成 m (m 0) 个互不相交的有限集 T 0, T 1,, T m-1 其中每个集合又都是一棵树, 称 T 0, T 1,, T m-1 为根结点的子树特点 : 除根结点外每个结点有且仅有一个直接前驱, 但可以有 0 或多个直接后继 2

3 树的定义树是由 n (n 0) 个结点组成的有限集合如果 n=0, 称为空树 ; 如果 n>0, 则有一个特定的称之为根 (root) 的结点, 它只有直接后继, 但没有直接前驱 ; 除根以外的其它结点划分为 m (m 0) 个互不相交的有限集合 T 0, T 1,, T m-1, 每个集合又是一棵树, 并且称之为根的子树 3

4 树的特点每棵子树的根结点有且仅有一个直接前驱, 但可以有 0 个或多个直接后继 A 0 层 E B F C G H D I J 1 层 2 层 height = 3 K L M 3 层 4

5 与树有关的概念结点的次数 ( 度数扇出 ): 一个结点的子树个数树的次数 ( 度数 ): 树中各结点次数的最大值 m 次完全树 : 树 T 中非叶子结点的次数都为 m 定义一棵树的根结点所在的层次为 0, 而其它结点的层次等于它的父结点的层次加 1 树的高度 : 树中层次最大的结点的层次 5

6 其它有关概念双亲孩子兄弟结点路径森林祖先约定结点 k i 的祖先不包括结点 k i 本身后代约定结点 k i 的后代不包括结点 k i 本身如果给树中的每个结点的每棵子树规定好它们的序号, 那么称此树为有序树 6

7 结点 (node) 包含数据项及指向其它结点的分支结点的度 (degree) 结点所拥有的子树棵数叶 (leaf) 结点即度为 0 的结点, 又称为终端结点分支 (branch) 结点除叶结点之外的其它结点, 又称为非终端结点子女 (child) 结点若结点 x 有子树, 则子树的根结点即为结点 x 的子女双亲 (parent) 结点若结点 x 有子女, 则它即为子女的双亲兄弟 (sibling) 结点同一双亲的子女互称为兄弟祖先 (ancestor) 结点从根结点到该结点所经分支上的所有结点子孙 (descendant) 结点某一结点的子女, 以及这些子女的子女都是该结点的子孙 7

8 结点所处层次 (level) 简称结点层次, 即从根到该结点所经路径上的分支条数 ( 树中任一结点的层次为其双亲结点层次加 1) 树的深度 (depth) 树中结点所处的最大层次 ( 空树深度为 0, 只有一个根结点的树的深度为 1) 树的高度 (height) 高度与深度计算方向不同, 但数值相等树的度 (degree) 树中结点的度的最大值有序树树中结点的各棵子树 T 0, T 1, 是有次序的, 其中 T 0 为根的第 1 棵子树,T 1 为根的第 2 棵子树无序树树中结点的各棵子树之间的次序是不重要的, 可以互相交换位置森林为 m 棵树的集合若删去一棵非空树的根结点, 树就变成森林 ; 若增加一个根结点, 让森林中每一棵树的根结点都变成它的子女, 则森林就变成一棵树 8

9 结点子女祖先树的度结点的度双亲子孙树的深度分支结点叶结点兄弟结点层次树高度森林 A 0 层 E B F C G H D I J 1 层 2 层 height = 3 K L M 3 层 9

10 树类定义 template <class Type> class Tree { // 对象 : 树是由 n (>=0) 个结点组成的有限集合 // 在类界面中的 position 是树中结点的地址 // 在顺序存储方式下是下标型, 在链表存储方式下是指针型 // Type 是树结点中存放数据的类型 // 要求所有结点的数据类型都是一致的 public: Tree( ); // 构造函数, 生成树的结构并初始化 ~Tree( ); // 析构函数, 释放所占存储 position Root( ); // 返回树的根结点地址, 若树为空, 则返回 0 10

11 BuildRoot(const Type &value); // 建立树的根结点 position FirstChild(position p); // 返回结点 p 的第一个子女的地址, 若无子女则返回 0 position NextSibling(position p, position v); // 返回结点 p 的子女 v 的下一兄弟地址, 若无兄弟则返回 0 position Parent(position p); // 返回结点 p 的双亲结点地址, 若 p 为根结点, 则返回 0 Type GetData(position p); // 函数返回结点 p 中存放的值 Type Retrieve(position p); // 函数返回结点 p 中存放的值 11

12 }; bool InsertChild(const position p, const Type &value); // 在结点 p 下插入数据为 value 的新子女结点 // 若结构中结点已满, 则不能插入, 函数返回 true // 若插入成功, 则函数返回 false bool DeleteChild(position p, int i); // 删除结点 p 的第 i 个子女及其全部子孙结点 // 若该结点的第 i 个子女结点不存在, 则函数返回 false // 若删除成功, 则函数返回 true void DeleteSubTree(position t); // 删除以 t 为根结点的子树 bool IsEmpty( ); // 判断树空否, 若树结点数为 0, 则返回 true, 否则返回 false void Traversal(void (*visit) (position p)); // 遍历,visit 是用户自编的访问结点 p 数据的函数

13 子女链表表示法 6.2 树的存储结构把一个结点用两个部分表示, 数据部分存放结点的数据 ( 关键字 ), 指针部分存放指向子结点的指针由于可能存在多个子结点, 因此也就需要存放多个指针实际应用中常常限定指针最多为 m 个, 这种方法的缺点是 m 不容易确定 13

14 一棵树中每个结点具有的子树棵数可能不尽相同, 因此如果用链接指针指示子树根结点的地址, 每个结点所需的链接指针各不相同采用变长结点的方式, 为各个结点设置不同数目的指针域, 将给存储管理带来很多麻烦 14

15 第一种解决方案等数量的链域根据树的度 d 为每个结点设置 d 个指针域 data child 1 child 2 child 3 child d 采用多重链表作为固定长结点的链表形式由于树中有许多结点的度小于 d, 造成许多空指针域, 空间浪费较大 d 越大, 空间浪费越多优点在于 : 管理容易 15

16 A B C D E F G 空链域 2n+1 个 A B C D E F G 16

17 第二种解决方案左子女 -- 右兄弟表示法, 为一种二叉树表示法由于 d=2, 则为最节省空间的树的存储表示, 每个结点由 3 个域组成 data firstchild nextsibling 若要检测某一结点的所有子女, 只需先通过结点的 firstchild 指针, 找到其第一个子女, 再通过该子女结点的 nextsibling 指针找到其下一兄弟, 依此类推, 找到其它兄弟, 直到 nextsibling 指针为空, 检测结束 17

18 树的左子女 - 右兄弟表示 B A A B C D E F G E F C G D 18

19 双亲表示法在这种方法中, 每个结点同样由两个部分构成, 第一个部分仍然是数据, 第二个部分也是指针, 但指向双亲结点由于树中每个结点最多只有一个双亲, 因此每个结点只需要保存一个指针可根据双亲指针是否为空判断一个结点是否为根可根据需要规定结点的存放顺序, 例如按照先根遍历的次序等 19

20 双亲表示 A B C D E F G data parent A B C D E F G 利用一组连续的存储单元来存放树中的结点每个结点有两个域, 一个是 data 域, 用来存放数据元素, 一个是 parent 域, 用来存放指示其双亲结点位置的指针 20

21 广义表表示 A B C D E F G A C D B E F G 树的广义表表示叶结点 && 根结点 && 分支结点原子结点 && 表头结点 && 子表结点

22 6.3 树的线性表示两种树的线性表示树的层号表示树的括号表示 ( 广义表表示 ) 22

23 树中结点的层号如果 k 是树中的一个结点, 那么为 k 规定一个整数 lev(k) 作为 k 的层号, 要求 : 如果 k 是 k 的子结点, 那么 lev(k ) >lev(k); 如果 k 和 k 都是 k 的子结点, 那么 lev(k ) =lev(k ); 层号与结点所在的层次含义不同, 结点的层次是唯一的, 而结点的层号则不然, 只要满足层号的两个条件的整数都可以作为结点的层号 23

24 树的层号表示树的层号表示是按前序写出树中全部结点, 并在结点之前带上结点的层号例如图 6-1 的树就可以表示成 : (0,k 0 ), (1,k 1 ), (2,k 2 ), (2,k 3 ), (1,k 4 ), (1,k 5 ), (2,k 6 ), (3,k 7 ) 24

25 广义表表示法广义表表示法是把根结点表示为广义表的表头对于每个结点 A,A 的每个子结点 C, 如果 C 是非叶子结点, 则在 A 表中有一个对应于 C 的子表结点, 对应子表的表头结点为 C; 如果 C 是叶子结点, 则在 A 表中有一个对应 C 的原子结点 k0(k1(k2,k3),k4,k5(k6(k7)))

26 6.4 树的遍历树的遍历是按一定顺序访问树中每个结点, 同时每个结点只能被访问一次树的遍历方式有多种, 常见的包括 : 树的前序遍历 ( 有的称为先根遍历 ) 树的后序遍历 ( 有的称为后根遍历 ) 树的层次遍历前序和后序遍历都属于深度优先遍历, 层次遍历又称为广度优先遍历对于有序树来说, 访问树中的结点时, 总是从左到右遍历各棵子树, 因此上述每一种遍历方法遍历所得到的结点序列都是唯一的 26

27 图 6-3 的各种遍历序列前序遍历 ABECFGHD 后序遍历 EBFHGCDA 层次遍历 ABCDEFGH 27

28 用递归实现树的前序遍历 #define MAXN 10 template <class Type> struct node { Type data; struct node *child[maxn]; }; template <class Type> class Tree { private: node <Type> *root; public: // 方法的声明, 具体内容见下一页 }; 28

29 m 次树前序遍历的递归实现 void preorder(node <Type> *t) { int m=maxn; if (t!=null) { cout<<t->data<<endl; for (int i=0; i<m; i++) preorder(t->child[i]); } } 29

30 m 次树前序遍历的非递归实现 void s_preorder(node<type> *t, intm) { Stack <node <Type> *> s(100); if (t==null) return; s.push(t); while (!s.isempty( )) { s.pop(&t); cout<<t->data<<endl; for (int i=m-1; i>=0; i--) if (t->child[i]!=null) s.push(t->child[i]); } } 30

31 程序 6-3 Tree 类的层次遍历 void levorder(node <Type> *t, int m) { node <Type> *p; Queue <node <Type> *> q; q.enqueue(t); while (!q.isempty( )) { q.dequeue(&p); cout<<p->data<<endl; for (int i=0; i<m; i++) if (p->child[i]!=null) q.enqueue(p->child[i]); } } 31

32 32

33 6.5 二叉树 (Binary Tree) 二叉树是一个有限的结点集合, 这个集合或者为空 ; 或者有一个根结点及表示根结点的左右子树的两个互不相交的结点集合所组成, 而根结点的左右子树也都是二叉树二叉树可以是空的, 空的二叉树不包含任何结点, 而一般的树至少有一个结点 33

34 二叉树的定义一棵二叉树是结点的一个有限集合, 该集合或者为空, 或者是由一个根结点加上两棵分别称为左子树和右子树的互不相交的二叉树组成二叉树的特点是每个结点最多有两个子女, 即二叉树中不存在度大于 2 的结点, 且二叉树的子树有左右之分, 其子树的次序不能颠倒 L R 二叉树的五种不同形态 L R 34

35 二叉树的性质性质 1 若二叉树的层次从 0 开始, 则在二叉树的第 i 层最多有 2 i 个结点 (i 0) [ 证明用数学归纳法 ] 性质 2 高度为 k 的二叉树最少有 k+1 个结点, 最多有 2 k+1-1 个结点 (k 0) [ 证明用求等比级数前 k 项和的公式 ] k =2 k

36 性质 3 对任何一棵二叉树, 如果其叶结点有 n 0 个, 度为 2 的非叶结点有 n 2 个, 则有 n 0 =n 2 +1 证明 : 若设度为 1 的结点有 n 1 个, 总结点个数为 n, 总边数为 e, 则根据二叉树的定义 : n=n 0 +n 1 +n 2 e=2n 2 +n 1 =n-1 因此, 有 2n 2 +n 1 =n 0 +n 1 +n 2-1 n 2 =n 0-1 n 0 =n

37 定义 1 满二叉树 (Full Binary Tree) 高度为 k 的满二叉树是有 2 k+1-1 个结点的二叉树, 其中每一层结点都达到了最大个数除最底层结点的度为 0 外, 其它各层结点的度都为 2 定义 2 完全二叉树 (Complete Binary Tree) 若设一棵具有 n 个结点的高度为 k 的二叉树, 其每一个结点都与高度为 k 的满二叉树树中编号为 1~n 的结点一一对应除第 h 层之外, 其它各层 (0 k-1) 的结点数都达到最大个数, 第 k 层从右向左连续缺若干结点 37

38 性质 4 具有 n (n 0) 个结点的完全二叉树的高度为 log 2 (n+1) -1 ( 证明 : 参见课本 )

39 性质 5 如将一棵有 n 个结点的完全二叉树自顶向下, 同一层自左向右连续给结点编号 0,1, 2,, n-1, 则有以下关系 : 如果 i= 0, 则结点 i 无双亲 ; 如果 i> 0, 则结点 i 的双亲为 (i -1)/2 如果 2 i+1 < n, 则结点 i 的左孩子为 2 i+1, 若 2 i+2 < n, 则结点 i 的右孩子为 2 i+2 如果 i 为偶数, 且 i 0, 则结点 i 的左兄弟为结点 i-1, 如果 i 为奇数, 且 i n-1, 则结点 i 的右兄弟为 i

40 二叉树类定义 template <class Type> class BinaryTree { public: BinaryTree( ); // 构造函数 BinaryTree(BinTreeNode <Type> *lch, BinTreeNode <Type> *rch, Type item); // 构造以 item 为根,lch 和 rch 为左右子树的二叉树 int Height( ); // 返回树的深度或高度 int Size( ); bool IsEmpty( ); // 判二叉树空否 BinTreeNode <Type> * Parent (BinTreeNode <Type> *current); 40

41 }; BinTreeNode <Type> * LeftChild (BinTreeNode <Type> *current); BinTreeNode <Type> * RightChild (BinTreeNode <Type> *current); bool Insert (Type item); bool Remove(Type item); bool Find(const Type &item) const; bool GetData(const Type &item) const; BinTreeNode <Type> * GetRoot( ) const; void PreOrdder(void (*visit) (BinTreeNode <Type> *p)); void InOrdder (void (*visit)(bintreenode <Type> *p)); void PostOrdder (void (*visit) (BinTreeNode <Type> *p)); void LevelOrdder (void (*visit) (BinTreeNode <Type> *p)); 41

42 把任意次树转换成相应的二叉树的方法把具有 m 个子结点 k 0,k 1,,k m-1 的结点 k 转换成以 k 0 作为结点 k 的左子结点, 并且 k i+1 作为 k i (i=0,1,,m-2) 的右子结点这种方法又称为左孩子右兄弟法树的先根遍历顺序与对应二叉树的前序遍历顺序相同树的后根遍历顺序与对应二叉树的中序遍历顺序相同 42

43 图 6-4 左孩子右兄弟转换方法的示意图 43

44 转换过程 : 图 6-5, 6-6,

45 转换成二叉树后的树的先根遍历的递归算法 void preorder( node<type> *t) { if(t!=null) { cout<<t->data<<endl; for(t=t->lchild; t!= NULL;t=t->rchild ) preorder(t); } }

46 转换成二叉树后的树的后根遍历的递归算法 void postorder( node<type> *t) { if(t!=null) { for(t=t->lchild; t!= NULL;t=t->rchild ) postorder(t); cout<<t->data<<endl; } }

47 T 1 T 2 T 3 A F H B C D G I J E 森林与二叉树的转换森林与二叉树的对应关系 K 3 棵树的森林 T 1 A T 2 F T 3 B G I C K D E H J B A C E 各棵树的二叉树表示 D G K F I H J 森林的二叉树表示 47

48 森林转化为二叉树 T=(T 0,T 1,,T m-1 ) 是由 m(m 0) 棵树构成的森林, 得到对应二叉树 β(t) 的方法如下 : 如果 m=0, 那么 β(t) 为空的二叉树 ; 如果 m>0, 那么 β(t) 的根结点就是 T 0 的根结点 ; β(t) 的根结点的左子树是 β(a 0, A 1,, A r-1 ), 其中 (A 0,A 1,,A r-1 ) 是 T 0 的根结点的子树 ;β(t) 的根结点的右子树是 β(t 1,,T m-1 ) 上述转换算法的逆转换可以把 T 2 转换回相应的森林 48

49 二叉树转换为森林如果二叉树为空, 对应的森林也为空如果二叉树非空, 则对应的森林中第一棵树的根为二叉树的根 ; 第一棵树的子树森林是由二叉树的根的左子树转换而来, 森林中其余的树组成的森林则由二叉树的根的右子树转换而成

50 程序 6-4 三次树转换为二叉树的程序 template <class Type> struct node3 { Type data; structnode3 *child[3]; }; typedef node3 <int> NODE3; template <class Type> struct node2 { Type data; structnode2 *lchild; structnode2 *rchild; }; typedef node2 <int> NODE2; NODE2 * beta(node3 *p, NODE3 *q, NODE3 *r) { NODE2 *t; if (p==null) return NULL; t=new NODE2( ); t->data=p->data; t->lchild=beta(p->child[0], p->child[1], p->child[2]); t->rchild=beta(q, r, NULL); return t; } 50

51 数组方式 6.6 二叉树的存储表示二叉树的顺序表示当在数据处理过程中, 二叉树的大小和形态不发生剧烈的动态变化时用一组连续的存储单元存储二叉树的数据元素用于表示完全二叉树的存储表示非常有效, 表示一般二叉树不很理想在树中进行插入和删除时, 为反映结点层次变动, 可能需要移动许多结点, 降低算法效率 51

1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 完全二叉树顺序表示 ( 最简单最省存储 ) **

52 完全二叉树顺序表示 ( 最简单最省存储 ) ** 对完全二叉树的所有结点按照层次次序自顶向下, 得到一个结点的线性序列, 按该序列将二叉树放在一维向量中 ** 利用完全二叉树的性质 5, 从一个结点的编号推算出其双亲子女兄弟等结点的编号, 找到这些结点 52

53 一般二叉树顺序表示 7 ** 对二叉树结点进行编号, 然后按其编号将它放到一维数组中 ** 在编号时, 若遇到空子树, 应在编号时假定有此子树进行编号, 而在顺序存储时留出相应位置, 由此找到其双亲子女兄弟结点的位置, 但可能消耗大量空间 53

54 极端情形 : 只有右单支的二叉树由于一般二叉树必须仿照完全二叉树那样存储, 可能会浪费很多存储空间, 单支树就是一个极端情况 ** 要求一个可存储 31 个结点的一维数组, 但只在其中几个位置放有结点数据, 其它大多数结点空间都未利用, 又不能压缩到一起, 造成很大空间浪费

55 链表方式二叉树的链表表示便于插入删除和修改 ; 数据不需移动 ; 只需修改指针 ; 可提高效率 55

56 leftchild data rightchild data leftchild rightchild 二叉链表 56

57 leftchild data parent rightchild data parent leftchild rightchild 三叉链表 57

58 root root root C D C D C D A A A B B B E F E F E 二叉树二叉链表三叉链表二叉树链表表示的示例 F 58

C root A B D E F 0 1 2 3 4 5 data parent leftchild rightchild A

59 C root A B D E F data parent leftchild rightchild A B C D E F 二叉树的的静态链表结构 59

60 二叉树类定义 template <class Type> class BinaryTree; template <class Type> class BinTreeNode { friend class BinaryTree <Type>; private: Type data; BinTreeNode <Type> *leftchild; BinTreeNode <Type> *rightchild; public: BinTreeNode( ) : leftchild(null), rightchild(null){ } BinTreeNode(Type item, BinTreeNode <Type> *left=null, BinTreeNode <Type> *right=null): data(item), leftchild(left), rightchild(right){ } 60

61 }; Type GetData( ) const { return data;} BinTreeNode <Type> * GetLeft( ) const { return leftchild;} BinTreeNode <Type> * GetRight( ) const { return rightchild;} void SetData (const Type &item) { data=item;} void SetLeft(BinTreeNode <Type> *L) { leftchild=l;} void SetRight(BinTreeNode <Type> *R) { rightchild=r;} 61

62 template <class Type> class BinaryTree { protected: BinTreeNode <Type> *root; Type RefValue; void CreateBinTree(istream &in, BinTreeNode <Type> *&subtree); bool Insert(BinTreeNode <Type> *&subtree, const Type &x); void Destroy(BinTreeNode <Type> *&subtree); bool Find(BinTreeNode <Type> *&SubTree, const Type &x) const; BinTreeNode <Type> * Copy(BinTreeNode <Type> *orignode); int Height(BinTreeNode <Type> *subtree); int Size(BinTreeNode <Type> *subtree); BinTreeNode <Type> * Parent(BinTreeNode <Type> *subtree, BinTreeNode <Type> *Parent); 62

63 BinTreeNode * Find(BinTreeNode <Type> *&subtree, const Type &x) const; void Traverse(BinTreeNode <Type> *&subtree, ostream &out); void PreOrder(BinTreeNode <Type> *&SubTree, void (*visit) (BinTreeNode <Type> *p)); void InOrder(BinTreeNode <Type> *&SubTree, void (*visit)(bintreenode <Type> *p)); void PostOrder(BinTreeNode <Type> *&SubTree, void (*visit)(bintreenode <Type> *p)); friend istream & operator >> (istream &in, BinaryTree <Type> &Tree); friend ostream & operator << (ostream &out, BinaryTree <Type> &Tree); 63

64 public: BinayTree( ) : root(null); BinayTree(Type value), RefValue(value), root(null) {} BinaryTree(BinaryTree <Type> &s); ~BinaryTree( ) { Dstroy(root); } bool IsEmpty( ) { return (root==null)?true : false;} BinTreeNode <Type> * Parent(BinTreeNode <Type> *current) {return(root==null root==current)? NULL : Parent(root, current); } BinTreeNode <Type> * LeftChild (BinTreeNode <Type> *current) {return(current!=null)?current->leftchild : NULL; } BinTreeNode <Type> * RightChild (BinTreeNode <Type> *current) {return(current!=null)?current->rightchild : NULL; } 64

65 }; int Height( ) { return Height(root); } int Size( ) { return Size(root); } BinTreeNode <Type> * GetRoot( ) const { return root;} void PreOrder (void (*visit) (BinTreeNode <Type> *p)) { PreOrder(root, visit); } void InOrder(void (*visit)(bintreenode <Type> *p)) { InOrder(root, visit); } void PostOrder(void (*visit) (BinTreeNode <Type> *p)) { PostOrder(root, visit); } void LevelOrder(void (*visit) (BinTreeNode <Type> *p)); int Insert(const Type item); BinTreeNode <Type> * Find(Type item) const; 65

66 二叉树部分成员函数的实现 template <class Type> void BinaryTree <Type> :: Destroy(BinTreeNode <Type> *subtree){ if (subtree!=null){ Destroy(subTree->leftChild); Destroy(subTree->rightChild); delete subtree; } } 66

67 template <class Type> BinTreeNode <Type> * BinaryTree <Type> :: Parent (BinTreeNode <Type> *subtree, BinTreeNode <Type> *current){ if (subtree==null) returnnull; if (subtree->leftchild==current subtree->rightchild==current) return subtree; BinTreeNode <Type> *p; if ((p=parent(subtree->leftchild, current))!=null) return p; else return Parent(subTree->rightChild, current); } 67

68 template <class Type> void BinaryTree <Type> :: Traverse(BinTreeNode <Type> *subtree, ostream &out){ // 私有函数 : 搜索并输出根为 subtree 的二叉树 if (subtree!=null){ out<<subtree->data<< ; Traverse(subTree->leftChild, out); Traverse(subTree->rightChild, out); } } 68

69 istream & operator >> (istream &in, BinaryTree <Type> &Tree){ // 重载操作 : 输入并建立一棵二叉树 Tree //in 是输入流对象 Type item; cout<< 构造二叉树 :\n ; // 打印标题 : 构造二叉树 cout<< 输入数据 ( 用 <<Tree.RefValue<< 结束 ): ; // 提示 : 输入数据 in>>item; // 输入,RefValue 是输入结束标志 while (item!=tree.refvalue){ // 判断是否结束输入 Tree.Insert(item); // 插入到树中 cout<< 输入数据 ( 用 <<Tree.RefValue<< 结束 ): ; in>>item; // 输入 } return in; } 69

70 ostream & operator << (ostream &out, BinaryTree <Type> &Tree){ out<< 二叉树的前序遍历 \n ; Tree.Traverse(Tree.root, out); out<<endl; return out; } 70

71 采用广义表建立二叉树广义表的表名放在表前, 表示树的根结点, 括号中是根的左右子树每个结点的左右子树用逗号隔开若仅有右子树没有左子树, 逗号不能省略在整个广义表表示输入的结尾加上一个特殊符号 ( 如 #, 存于 RefValue 中 ), 表示输入结束 A(B(D, E(G, )), C(, F))# 71

72 算法基本思想依次从保存广义表的字符串 ls 中输入字符若是字母则表示结点值, 建立新结点, 作为左子女 (k=1) 或右子女 (k=2) 链接到其父结点上若是左括号 (, 则表明子表开始, 将 k 置为 1; 若遇到的是右括号 ), 则表明子表结束若遇到逗号,, 则表示以左子女为根的子树处理完毕, 应接着处理以右子女为根的子树, 将 k 置为 2 如此处理, 直至读入结束符 # 为止使用一个栈, 在进入子表之前将根结点指针进栈, 以便括号内的子女链接之用, 在子表处理结束时退栈 72

73 void CreateBinTree(istream &in, BinTreeNode <char> *&BT) { // 从输入流 in 输入二叉树的广义表表示建立对应的二叉链表 Stack <BinTreeNode <char> *> s; BT=NULL; BinTreeNode <char> *p, *t; intk; charch; in>>ch; while (ch!=refvalue){ switch (ch) { case ( :s.push(p); k=1; break; case ) :s.pop(t); break; case, :k=2; break; default : p=new BinTreeNode(ch); if (BT==NULL) BT=p; else if (k==1){s.gettop(t); t->leftchild=p;} else { S.GetTop(t); t->rightchild=p;} } in>>ch; } }

74 6.7 二叉树的各种遍历树的遍历就是按某种次序访问树中的结点, 要求每个结点访问一次且仅访问一次设访问根结点记作 V, 遍历根的左子树记作 L, 遍历根的右子树记作 R, 则可能的遍历次序有前序 VLR 镜像 VRL 中序 LVR 镜像 RVL 后序 LRV 镜像 RLV 二叉树的层次遍历方法与一般有序树的几乎完全相同, 不再给出 74

75 中序遍历 (Inorder Traversal) 中序遍历二叉树算法的框架是 : 若二叉树为空, 则空操作 ; 否则中序遍历左子树 (L); + - / 访问根结点 (V); 中序遍历右子树 (R) a * e f 遍历结果 b - a+b*c-d-e/f c d 75

76 程序 6-6 中序遍历的递归算法 void r_midorder(node *t) { if(t!= NULL) { r_midorder(t->lchild); cout<<t->data<<endl; r_midorder(t->rchild); } }

77 二叉树递归的中序遍历算法 (C++ 形式 ) template <class Type> void BinaryTree <Type> :: InOrder(BinTreeNode <Type> *subtree, void (*visit) (BinTreeNode <Type> *p)) { if (subtree!=null){ InOrder(subTree->leftChild); visit(subtree->data); InOrder(subTree->rightChild); } } 77

78 前序遍历 (Preorder Traversal) 前序遍历二叉树算法的框架是 : 若二叉树为空, 则空操作 ; 否则访问根结点 (V); + - / 前序遍历左子树 (L); 前序遍历右子树 (R) a * e f 遍历结果 b - -+a*b-cd/ef c d 78

79 前序遍历的递归算法 void r_preorder(node *t) { if(t!= NULL) { cout<<t->data<<endl; r_preorder(t->lchild); r_preorder(t->rchild); } }

80 二叉树递归的前序遍历算法 (C++ 形式 ) template <class Type> void BinaryTree <Type> :: PreOrder(BinTreeNode <Type> *subtree, void (*visit) (BinTreeNode <Type> *p)) { if (subtree!=null){ visit(subtree->data); PreOrder(subTree->leftChild); PreOrder(subTree->rightChild); } } 80

81 后序遍历 (Postorder Traversal) 后序遍历二叉树算法的框架是 : 若二叉树为空, 则空操作 ; 否则后序遍历左子树 (L); + - / 后序遍历右子树 (R); 访问根结点 (V) a * e f 遍历结果 b - abcd-*+ef/- c d 81

82 后序遍历的递归算法 void r_posorder(node *t) { if(t!= NULL) { r_posorder(t->lchild); r_posorder(t->rchild); cout<<t->data<<endl; } }

83 二叉树递归的后序遍历算法 (C++ 形式 ) template <class Type> void BinaryTree <Type> :: PostOrder(BinTreeNode <Type> *subtree, void (*visit) (BinTreeNode <Type> *p)) { if (subtree!=null) { PostOrder(subTree->leftChild); PostOrder(subTree->rightChild); visit(subtree->data); } } 83

84 程序 6-5 非递归中序遍历算法 1. template <class Type > struct node { 2. Type data; struct node *lchild; struct node *rchild; }; 3. typedef node< int > NODE; 4. void s_midorder(node *t) { 5. Stack<NODE*> s(100); 6. while(t!= NULL!s.isEmpty()) { 7. while(t!= NULL) { 8. s.push(t) ; t = t->lchild; 9. } 10. if(!s.isempty()) { 11. s.pop( &t ); cout<<t->data<<endl; t = t->rchild; 12. } 13. } 14. } Q: 只要把上面程序中的输出语句调整到一个适当的位置上, 就能实现二叉树的前序遍历

85 另一种非递归前序遍历算法 1. template <class T> void BinaryTree<T> :: PreOrder( void(*visit)(bintreenode<t> *p)) { 2. stack <BinTreeNode<T>* > S; 3. BinTreeNode<T> * p; 4. S.Push ( root ); 5. while (!S.IsEmpty() ) { 6. S.Pop( p); 7. visit(p); 8. if ( p->rightchild!= NULL ) S.Push ( p- >rightchild ); 9. if ( p->leftchild!= NULL ) S.Push ( p->leftchild ); 10. } 11. }

86 二叉树遍历的思考 1. 后序遍历的非递归 2. 层次遍历的非递归 3. 数组存储方式下的各种遍历

<4D F736F F F696E74202D20536C FB5DACBC4D5C220CAF7D3EBB6FEB2E6CAF7205BBCE6C8DDC4A3CABD5D>

<4D F736F F F696E74202D20536C FB5DACBC4D5C220CAF7D3EBB6FEB2E6CAF7205BBCE6C8DDC4A3CABD5D> 第四章树二叉树森林树的基本概念二叉树定义主要特征存储结构 : 顺序链式遍历线索二叉树 : 基本概念构造树森林存储结构 : 树森林与二叉树的转换遍历 : 树森林应用二叉排序树 Huffman 树和哈夫曼编码树和有根树两种树 : 自由树有根树树 (Tree) 和森林的概念自由树无回路的连通图 : 一棵自由树 T f 可定义为一个二元组 T f = (V,