第五章 树与二叉树 树和森林的概念树和森林的概念 二叉树二叉树 二叉树遍历二叉树遍历 线索化二叉树线索化二叉树 树与森林树与森林 堆堆 HuffmanHuffman树树1树和森林的概念有根树： 一棵有根树 T，简称为树，它是n (n0) 个 结点的有限集合。当n = 0时，T 称为空树； 否则，T 是非空树，记作 2DACBIJHGFEMLKu r 是一个特定的称为根(root)的结点，它只 有直接后继，但没有直接前驱；u根以外的其他结点划分为 m (m 0) 个互不 相交的有限集合T1, T2, , Tm，每个集合又 是一棵树，并且称之为根的子树。u每棵子树的根结点有且仅有一个直接前驱 ，但可以有0个或多个直接后继。3树的基本术语子女：若结点的子树非空，结点子树的根即 为该结点的子女。双亲（父亲）：若结点有子女，该结点是子 女的双亲（父亲）。兄弟：同一结点的子女互称为兄弟。度：结点的子女个数即为该结点的度；树中 各个结点的度的最大值称为树的度。4分支结点：度不为0的结点即为分支结点， 亦称为非终端结点。叶结点：度为0的结点即为叶结点，亦称为 终端结点。祖先：根结点到该结点的路径上的各个结点 都是该结点的祖先。子孙：某结点的所有下属结点，都是该结点 的子孙。5结点的层次：规定根结点在第一层，其子女 结点的层次等于它的层次加一。以下类推。深度：结点的深度即为结点的层次；离根最 远结点的层次即为树的深度。1层2层4层3层depth = 4DACBIJHGFEMLKheight = 46高度：规定叶结点的高度为1，其双亲结点的高 度等于它的高度加一。树的高度：等于根结点的高度，即根结点所有 子女高度的最大值加一。有序树：树中结点的各棵子树 T0, T1, 是有次 序的，即为有序树。无序树：树中结点的各棵子树之间的次序是不 重要的，可以互相交换位置。森林：森林是m（m0）棵树的集合。 7树的抽象数据类型template class Tree /对象: 树是由n (0) 个结点组成的有限集合。在 /类界面中的 position 是树中结点的地址。在顺序 /存储方式下是下标型, 在链表存储方式下是指针 /型。T 是树结点中存放数据的类型, 要求所有结 /点的数据类型都是一致的。 public:Tree (); Tree (); 8BuildRoot (const T /建立树的根结点position FirstChild(position p);/返回 p 第一个子女地址, 无子女返回 0position NextSibling(position p);/返回 p 下一兄弟地址, 若无下一兄弟返回 0position Parent(position p);/返回 p 双亲结点地址, 若 p 为根返回 0T getData(position p);/返回结点 p 中存放的值bool InsertChild(position p, T/在结点 p 下插入值为 value 的新子女, 若插/入失败, 函数返回false, 否则返回true9bool DeleteChild (position p, int i);/删除结点 p 的第 i 个子女及其全部子孙结/点, 若删除失败, 则返回false, 否则返回truevoid DeleteSubTree (position t);/删除以 t 为根结点的子树bool IsEmpty ();/判树空否, 若空则返回true, 否则返回falsevoid Traversal (void (*visit)(position p); /遍历以 p 为根的子树 ; 10二叉树的五种不同形态二叉树的五种不同形态LLRR二叉树 (Binary Tree)二叉树的定义 一棵二叉树是结点的一个有限集合，该集合 或者为空，或者是由一个根结点加上两棵分 别称为左子树和右子树的、互不相交的二叉 树组成。11二叉树的性质性质1 若二叉树结点的层次从 1 开始, 则在 二叉树的第 i 层最多有 2i-1 个结点。( i1)证明用数学归纳法性质2 深度为 k 的二叉树最少有 k 个结点， 最多有 2k-1个结点。( k1 )因为每一层最少要有1个结点，因此，最少 结点数为 k。最多结点个数借助性质1：用 求等比级数前k项和的公式20 +21 +22 + +2k-1 = 2k-112性质3 对任何一棵二叉树，如果其叶结点有 n0 个, 度为 2 的非叶结点有 n2 个, 则有n0n21若设度为 1 的结点有 n1 个，总结点数为n，总边数为e，则根据二叉树的定义，n = n0+n1+n2 e = 2n2+n1 = n-1因此，有 2n2+n1 = n0+n1+n2-1n2 = n0-1 n0 = n2+1 13定义1 满二叉树 (Full Binary Tree) 深度为 k的满二叉树是有2k -1个结点的二叉 树。定义2 完全二叉树 (Complete Binary Tree) 若设二叉树的深度为 k，则共有 k 层。除第 k 层外，其它各层 (1k-1) 的结点数都达到 最大个数，第k层从右向左连续缺若干结点 ，这就是完全二叉树。14性质4 具有 n (n0) 个结点的完全二叉树的 深度为 log2(n+1) 设完全二叉树的深度为k，则有2k-1-1 1, 则 i 的双亲为i2 若2*i class BinaryTree /对象: 结点的有限集合, 二叉树是有序树 public:BinaryTree ();/构造函数BinaryTree (BinTreeNode *lch, BinTreeNode *rch, T item);/构造函数, 以item为根, lch和rch为左、右子/树构造一棵二叉树int Height ();/求树深度或高度int Size ();/求树中结点个数17bool IsEmpty ();/判二叉树空否？ BinTreeNode *Parent (BinTreeNode *t); /求结点 t 的双亲BinTreeNode *LeftChild (BinTreeNode *t);/求结点 t 的左子女BinTreeNode *RightChild (BinTreeNode *t); /求结点 t 的右子女bool Insert (T item);/在树中插入新元素bool Remove (T item);/在树中删除元素bool Find (T/判断item是否在树中bool getData (T/取得结点数据18BinTreeNode *getRoot ();/取根void preOrder (void (*visit) (BinTreeNode *t); /前序遍历, visit是访问函数void inOrder (void (*visit) (BinTreeNode *t); /中序遍历, visit是访问函数void postOrder (void (*visit) (BinTreeNode *t); /后序遍历, (*visit)是访问函数void levelOrder (void (*visit)(BinTreeNode *t); /层次序遍历, visit是访问函数 ;19完全二叉树 一般二叉树 的顺序表示 的顺序表示二叉树的顺序表示11 2 3 4 5 6 7 8 9 10 141 2 3 4 6 7 8 9 12 1424891056731237648912510 1113201371531极端情形: 只有右单支的二叉树137153121二叉树结点定义：每个结点有3个成员，data 域存储结点数据，leftChild和rightChild分别 存放指向左子女和右子女的指针。leftChild data rightChilddataleftChildrightChild二叉链表二叉树的链表表示（二叉链表）22leftChild data parent rightChildparentdataleftChildrightChild三叉链表二叉树的链表表示（三叉链表）每个结点增加一个指向双亲的指针parent， 使得查找双亲也很方便。23二叉树链表表示的示例二叉树链表表示的示例 AAABBBCCCDDDFFFEEErootrootroot二叉树 二叉链表 三叉链表24三叉链表的静态结构三叉链表的静态结构ABCDFErootdata parent leftChild rightChild0 1 2 3 4 5A -1 1 -1 B 0 2 3 C 1 -1 -1 D 1 4 5 E 3 -1 -1 F 3 -1 -125二叉树的类定义template struct BinTreeNode /二叉树结点类定义T data; /数据域BinTreeNode *leftChild, *rightChild;/左子女、右子女链域BinTreeNode () /构造函数 leftChild = NULL; rightChild = NULL; BinTreeNode (T x, BinTreeNode *l = NULL, BinTreeNode *r = NULL) data = x; leftChild = l; rightChild = r; ; 26template class BinaryTree /二叉树类定义 public:BinaryTree () : root (NULL) /构造函数BinaryTree (T value) : RefValue(value), root(NULL) /构造函数BinaryTree (BinaryTree /复制构造函数BinaryTree () destroy(root); /析构函数bool IsEmpty () return root = NULL;/判二叉树空否int Height () return Height(root); /求树高度int Size () return Size(root); /求结点数27BinTreeNode *Parent (BinTreeNode *t) return (root = NULL | root = t) ?NULL : Parent (root, t); /返回双亲结点BinTreeNode *LeftChild (BinTreeNode *t) return (t != NULL)？t-leftChild : NULL; /返回左子女BinTreeNode *RightChild (BinTreeNode *t) return (t != NULL)？t-rightChild : NULL; /返回右子女BinTreeNode *getRoot () const return root; /取