1Binary Trees A binary tree is made up of a finite set of nodes that is either empty or consists of a node called the root together with two binary trees, called the left and right subtrees, which are disjoint from each other and from the root.2Binary Tree ExampleNotation: Node, edge, path, children, parent, ancestor, descendant, depth, level, height, subtree , leaf node, internal node.3Full and Complete Binary TreesFull binary tree: Each node is either a leaf or internal node with exactly two non-empty children.Complete binary tree: If the height of the tree is d, then all levels except possibly level d-1 are completely full. The bottom level has all nodes to the left side.4Full Binary Tree TheoremTheorem1: The number of leaves in a non-empty full binary tree is one more than the number of internal nodes.Theorem2: The number of null subtrees in a non-empty binary tree is one more than the number of nodes in the tree.5Data Structures and Algorithms6A Binary Tree Node ADTTemplate class BinNode public: virtual Elem& val( ) =0; virtual void setVal( const Elem& ) = 0; virtual BinNode* left( ) const = 0; virtual void setLeft( BinNode* ) = 0; virtual BinNode* right( ) const = 0; virtual void setRight( BinNode* ) = 0; virtual bool isLeaf( ) = 0;7Traversals (1)Any process for visiting the nodes in some order is called a traversal.Any traversal that lists every node in the tree exactly once is called an enumeration of the trees nodes.8Traversals (2)Preorder traversal: Visit each node before visiting its children.Postorder traversal: Visit each node after visiting its children.Inorder traversal: Visit the left subtree, then the node, then the right subtree.9Traversals (2)Preorder traversal: A B D C E G F H IPostorder traversal: D B G E H I F C AInorder traversal: B D A G E C H F IExample:Exercise:Postorder traversal: D E C B H G F AInorder traversal: B D C E A F H G10Traversals (3)template / Good implementationvoid preorder(BinNode* subroot) if (subroot = NULL) return; / Empty visit(subroot); / Perform some action preorder(subroot-left(); preorder(subroot-right();template / Bad implementationvoid preorder2(BinNode* subroot) visit(subroot); / Perform some action if (subroot-left() != NULL) preorder2(subroot-left(); if (subroot-right() != NULL) preorder2(subroot-right();11Traversal Example/ Return the number of nodes in the treetemplate int count(BinNode* subroot) if (subroot = NULL) return 0; / Nothing to count return 1 + count(subroot-left() + count(subroot-right();12Binary Tree Implementation (1)13Binary 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 childpublic: BinNodePtr() lc = rc = NULL; BinNodePtr(Elem e, BinNodePtr* l =NULL, BinNodePtr* r =NULL) it = e; lc = l; rc = r; 14Binary 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; inline BinNode* right() const return rc; void setRight(BinNode* b) rc = (BinNodePtr*)b; bool isLeaf() return (lc = NULL) & (rc = NULL); ;15Binary Tree Implementation (2)16Union Implementation (1)enum Nodetype leaf, internal;class VarBinNode / Generic node classpublic: Nodetype mytype; / Store type for node union struct / Internal node VarBinNode* left; / Left child VarBinNode* right; / Right child Operator opx; / Value intl; Operand var; / Leaf: Value only ;17Union Implementation (2) / Leaf constructor VarBinNode(const Operand& val) mytype = leaf; var = val; / Internal node constructor VarBinNode(const Operator& op, VarBinNode* l, VarBinNode* r) mytype = internal; intl.opx = op; intl.left = l; intl.right = r; bool isLeaf() return mytype = leaf; VarBinNode* leftchild() return intl.left; VarBinNode* rightchild() return intl.right; ;18Union Implementation (3)/ Preorder traversalvoid traverse(VarBinNode* subroot) if (subroot = NULL) return; if (subroot-isLeaf() cout Leaf: “ var n; else cout Internal: “ intl.opx leftchild(); traverse(subroot-rightchild(); 19Inheritance (1)class VarBinNode / Abstract base classpublic: virtual bool isLeaf() = 0;class LeafNode : public VarBinNode / Leafprivate: Operand var; / Operand valuepublic: LeafNode(const Operand& val) var = val; / Constructor bool isLeaf() return true; Operand value() return var; ;20Inheritance (2)/ Internal nodeclass IntlNode : public VarBinNode private: VarBinNode* left; / Left child VarBinNode* right; / Right child Operator opx; / Operator valuepublic: IntlNode(const Operator& op, VarBinNode* l, VarBinNode* r) opx = op; left = l; right = r; bool isLeaf() return false; VarBinNode* leftchild() return left; VarBinNode* rightchild() return right; Operator value() return opx; ;21Inheritance (3)/ Preorder traversalvoid traverse(VarBinNode *subroot) if (subroot = NULL) return; / Empty if (subroot-isLeaf() / Do leaf node cout Leaf: value() endl; else / Do internal node cout Internal: value() leftchild(); traverse( (IntlNode *)subroot)-rightchild(); 22Composite (1)class VarBinNode / Abstract base classpublic: virtual bool isLeaf() = 0; virtual void trav() = 0;class LeafNode : public VarBinNode / Leaf private: Operand var; / Operand valuepublic: LeafNode(const Operand& val) var = val; / Constructor bool isLeaf() return true; Operand value() return var; void trav() cout Leaf: value() endl; ;23Composite (2)class IntlNode : public VarBinNode private: VarBinNode* lc; / Left child VarBinNode* rc; / Right child Operator opx; / Operator valuepublic: IntlNode(const Operator& op, VarBinNode* l, VarBinNode* r) opx = op; lc = l; rc = r; bool isLeaf() return false; VarBinNode* left() return lc; VarBinNode* right() return rc; Operator value() return opx; void trav() cout Internal: value() trav(); if (right() != NULL) right()-trav(); ;24Composite (3)/ Preorder traversalvoid traverse(VarBinNode *root) if (root != NULL) root-trav();25Space Overhead (1)From the Full Binary Tree Theorem:Half of the pointers are null.If leaves store only data, then overhead depends on whether the tree is full.Ex: All nodes the same, with two pointers to children:Total space required is (2p + d)nOverhead: 2pnIf p = d, this means 2p/(2p + d) = 2/3 overhead.26Space Overhead (2)Eliminate pointers from the leaf nodes: n/2*(2p) p n/2*(2p) + dn p + dThis is 1/2 if p = d.2p/(2p + d) if data only at leaves 2/3 overhead.Note that some method is needed to distinguish leaves from internal nodes.=27Array Implementation (1)Position012345678910 11Parent-00112233445Left Child1357911-Right Child246810-Left Sibling-1-3-5-7-9-Right Sibling-2-4-6-8- 10-28Array Implementation (1)Parent (r) = (r - 1) / 2 if r 0 and r n.Leftchild(r) = 2r + 1 if 2r+1 n.Rightchild(r) = 2r + 2 if 2r +2 0 and r n.Rightsibling(r) = r + 1 if r is odd, r +1 n.29Binary Search TreesBST Property: All elements stored in the left subtree of a node with value K have values = K.30BST ADT(1)/ BST implementation for the Dictionary ADTtemplate class BST : public Dictionary private: BinNode* root; / Root of the BST int nodecount; / Number of nodes void clearhelp(BinNode*); BinNode* inserthelp(BinNode*, const Elem&); BinNode* deletemin(BinNode*,BinNode*&); BinNode* removehelp(BinNode*, const Key&, BinNode*&); bool findhelp(BinNode*, const Key&, Elem&) const; void printhelp(BinNode*, int) const;31BST ADT(2)public: BST() root = NULL; nodecount = 0; BST() clearhelp(root); void clear() clearhelp(root); root = NULL; nodecount = 0; bool insert(const Elem& e) root = inserthelp(root, e); nodecount+; return true; bool remove(const Key& K, Elem& e) BinNode* t = NULL; root = removehelp(root, K, t); if (t = NULL) return false; e = t-val(); nodecount-; delete t; return true; 32BST ADT(3) bool removeAny(Elem& e) / Delete min value if (root = NULL) return false; / Empty BinNode* t; root = deletemin(root, t); e = t-val(); delete t; nodecount-; return true; bool find(const Key& K, Elem& e) const return findhelp(root, K, e); int size() return nodecount; void print() const if (root = NULL) cout The BST is empty.n; else printhelp(root, 0); 33BST Searchtemplate bool BST: findhelp(BinNode* subroot, const Key& K, Elem& e) const if (subroot = NULL) return false; else if (KEComp:lt(K, subroot-val() return findhelp(subroot-left(), K, e); else if (KEComp:gt(K, subroot-val() return findhelp(subroot-right(), K, e); else e = subroot-val(); return true; 34BST Insert (1)35BST Insert (2)template BinNode* BST: inserthelp(BinNode* subroot, const Elem& val) if (subroot = NULL) / Empty: create node return new BinNodePtr(val,NULL,NULL); if (EEComp:lt(val, subroot-val() subroot-setLeft(inserthelp(subroot-left(), val); else subroot-setRight( inserthelp(subroot-right(), val); / Return subtree with node inserted return subroot;36Remove Minimum Valuetemplate BinNode* BST:deletemin(BinNode* subroot, BinNode*& min) if (subroot-left() = NULL) min = subroot; return subroot-right(); else / Continue left subroot-setLeft( deletemin(subroot-left(), min); return subroot; 37BST Remove (1)38BST Remove (2)template BinNode* BST:removehelp(BinNode* subroot, const Key& K, BinNode*& t) if (subroot = NULL) return NULL; else if (KEComp:lt(K, subroot-val() subroot-setLeft( removehelp(subroot-left(), K, t); else if (KEComp:gt(K, subroot-val() subroot-setRight( removehelp(subroot-right(), K, t);39BST Remove (3) else / Found it: remove it BinNode* temp; t = subroot; if (subroot-left() = NULL) subroot = subroot-right(); else if (subroot-right() = NULL) subroot = subroot-left(); else / Both children are non-empty subroot-setRight( deletemin(subroot-right(), temp); Elem te = subroot-val(); subroot-setVal(temp-val(); temp-setVal(te); t = temp; return subroot;40HeapsHeap: Complete binary tree with the heap propertyMin-heap: All values less than child values.Max-heap: All values greater than child values.The values are partially ordered.Heap representation: Normally the array-based complete binary tree representation.41Building the Heap (1)(4-2) (4-1) (2-1) (5-2) (5-4) (6-3) (7-6) (7-5)42Building the Heap (2)(7-3),(5-2), (7-1), (6-1)43Heap ADTtemplate class maxheapprivate: Elem* Heap; / Pointer to the heap array int size; / Maximum size of the heap int n; / Number of elems now in heap void siftdown(int); / Put element in placepublic: maxheap(Elem* h, int num, int max); int heapsize() const; bool isLeaf(int pos) const; int leftchild(int pos) const; int rightchild(int pos) const; int parent(int pos) const; bool insert(const Elem&); bool removemax(Elem&); bool remove(int, Elem&); void buildHeap();44Siftdown (1)For fast heap construction:Work from high end of array to low end.Call siftdown for each item.Dont need to call siftdown on leaf nodes.template void maxheap:siftdown(int pos) while (!isLeaf(pos) int j = leftchild(pos); int rc = rightchild(pos); if (rcn) & Comp:lt(Heapj,Heaprc) j = rc; if (!Comp:lt(Heappos, Heapj) return; swap(Heap, pos, j); pos = j;45Siftdown (2)46Buildheap CostCost for heap construction: log n (i - 1) n/2i n. i=147Remove Max Valuetemplate bool maxheap: removemax(Elem& it) if (n = 0) return false; / Heap is empty swap(Heap, 0, -n); / Swap max with end if (n != 0) siftdown(0); it = Heapn; / Return max value return true;48Priority QueuesA priority queue stores objects, and on request releases the object with greatest value.Example: Scheduling jobs in a multi-tasking operating system.The priority of a job may change, requiring some reordering of the jobs.Implementation: Use a heap to store the priority queue.To support priority reordering, delete and re-insert. Need to know index for the object in question.49template bool maxheap:remove(int pos, Elem& it) if (pos = n) return false; swap(Heap, pos, -n); while (pos != 0) & (Comp:gt(Heappos, Heapparent(pos) swap(Heap, pos, parent(pos); pos = parent(pos); siftdown(pos); it = Heapn; return true;50Huffman Coding TreesASCII codes: 8 bits per character.Fixed-length coding.Can take advantage of relative frequency of letters to save space.Variable-length codingBuild the tree with minimum external path weight.ZKFCUDLE27243237424212051Huffman Tree Construction (1)52Huffman Tree Construction (2)53Assigning CodesLetter FreqCodeC321110D42101E1200M2411111K7111101L42110U37100Z211110054Coding and Decoding A set of codes is said to meet the prefix property if no code in the set is the prefix of another.Code for DEED: 101 0 0 101Decode 1011001110111101:1011001110111101: DUCK55CostExpected cost per letter:(1*120+3*121+4*32+5*24+6*9)/306 = 785/306 = 2.57LetterFreqCodeBitsC3211104D421013E12001M24111115K71111016L421103U371003Z2111100656Huffman Coding Trees ADT(1)template class HuffNode /Node abstract base classpublic: virtual int weight() = 0; virtual bool isLeaf() = 0; virtual HuffNode* left() const = 0; virtual void setLeft(HuffNode*) = 0; virtual HuffNode* right() const = 0; virtual void setRight(HuffNode*) = 0;57Huffman Coding Trees ADT(2)template /leaf node subclassclass LeafNode: public HuffNode private: Freqpair* it; /Frequency pairpublic: LeafNode(const Elem& val, int freq) /constructor it = new Freqpair(val,freq); int weight() return it-weight(); /Return frequency Freqpair* val() return it; bool isLeaf() return true; 58Huffman Coding Trees ADT(3) virtual HuffNode* left() const return NULL; virtual void setLeft(HuffNode*) virtual HuffNode* right() const return NULL; virtual void setRight(HuffNode*) ;59Huffman Coding Trees ADT(4)template /Internal node subclassclass IntlNode: public HuffNode private: HuffNode* lc; /left child HuffNode* rc; /right child int wgt; /Subtree weightpublic: IntlNode(HuffNode * l; HuffNode * r) wgt = l-weight() + r-weight(); lc = l; rc = r; int weight() return wgt; /Return frequency60Huffman Coding Trees ADT(5) bool isLeaf() return false; HuffNode* left() const return lc; void setLeft(HuffNode* b) lc = (HuffNode*)b; HuffNode* right() const return rc; void setRight(HuffNode* b) rc = (HuffNode*)b; ;61Huffman Coding Trees ADT(6)template class FreqPair /An element / frequency pairprivate: elem it; /An element of some sort int freq;public: FreqPair(const Elem& e, int f) /Constructor it = e; freq = f; FreqPair() /Destructor int weight() return freq; /Return the weight Elem& val() return it; /Return the element;62Huffman Coding Trees ADT(7)template class HuffTree private: HuffNode* theRoot;public: HuffTree(Elem& val, int freq) theRoot = new LeafNode(val,freq); HuffTree(HuffTree* l, HuffTree* r) theRoot = new IntlNode(l-root(), r-root(); HuffTree() HuffNode* root() return theRoot; int weight() return theRoot-weight(); ;63Huffman Coding Trees ADT(8)template class HHCompare public: static bool lt(HuffTree* x, HuffTree* y) return x-weight() weight(); static bool eq(HuffTree* x, HuffTree* y) return x-weight() = = y-weight(); static bool gt(HuffTree* x, HuffTree* y) return x-weight() y-weight(); ;64Huffman Coding Trees ADT(9)template HuffTree*buildHuff(SLListHuffTree*,HHCompare * f1) HuffTree* temp1, *temp2, *temp3; for (f1-setStart(); f1-leftLength()+f1-rightLength()1; f1-setStart() /While at least two items left f1-remove(temp1); /Pull first two trees off the list f1-remove(temp2); temp3 = new HuffTree(temp1, temp2); f1-insert(temp3); /Put the new tree back on list delete temp1; /Must delete the remnants delete temp2; / of the trees we created return temp3;651. 二叉树的定义二叉树的定义定义：定义：是是n（n0）个结点的有限集合，由一个根结点以及两棵互不相交的、）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为分别称为左子树左子树和和右子树右子树的二叉树组成的二叉树组成 。逻辑结构：逻辑结构： 一对二（一对二（1：2） 基本特征基本特征: 每个结点最多只有两棵子树（不存在度大于每个结点最多只有两棵子树（不存在度大于2 2的结点）；的结点）； 左子树和右子树次序不能颠倒（有序树）。左子树和右子树次序不能颠倒（有序树）。基本形态：基本形态： 具有具有具有具有3 3 3 3个结点的二叉树可能有几种不同形态？个结点的二叉树可能有几种不同形态？个结点的二叉树可能有几种不同形态？个结点的二叉树可能有几种不同形态？5种种 662. 二叉树的性质二叉树的性质 性质性质1:1: 在二叉树的第在二叉树的第i i层上至多有层上至多有2 2 2 2i i i i个结点（个结点（i0i0）。）。性质性质2:2: 深度为深度为k k的二叉树至多有的二叉树至多有2 2 2 2k k k k-1-1-1-1个结点（个结点（k0k0）。）。性质性质3:3: 对完全二叉树，若从上至下、从左至右编号，则编号对完全二叉树，若从上至下、从左至右编号，则编号为为i 的结点，其左孩子编号必为的结点，其左孩子编号必为2i，其右孩子编号必为，其右孩子编号必为2i1；其双亲的编号必为其双亲的编号必为i/2（i1 时为根时为根, ,除外除外）。）。 673. 二叉树的存储结构二叉树的存储结构一、顺序存储结构一、顺序存储结构按按二二叉叉树树的的结结点点“自自上上而而下下、从从左左至至右右”编编号号，用用一组连续的存储单元存储。一组连续的存储单元存储。A AB BC CD DE EF FG GH HI I012345678A AB BC CGGE EI ID DHHF F问：顺序存储后能否复原成唯一对应的二叉树形状？问：顺序存储后能否复原成唯一对应的二叉树形状？答：答：若是若是完全二叉树则可以做到唯一复原完全二叉树则可以做到唯一复原。 而且有规律：下标值为而且有规律：下标值为i i的双亲，其左孩子的下标值必为的双亲，其左孩子的下标值必为 2i+12i+1，其右孩子的下标值必为，其右孩子的下标值必为2i2i2 2（即性质（即性质5 5） 例如，对应例如，对应22的两个孩子必为的两个孩子必为55和和6,6,即即C C的左孩子必的左孩子必 是是F,F,右孩子必为右孩子必为G G。68不是完全二叉树怎么办？不是完全二叉树怎么办？答：答：一律转为完全二叉树！一律转为完全二叉树！将各层空缺处统统补上将各层空缺处统统补上“虚结点虚结点”，其内容为空。，其内容为空。A AB B C C D D E E012345678.15ABECD缺点：缺点：浪费空间；浪费空间；插入、删除不便插入、删除不便 69二、链式存储结构二、链式存储结构 用二叉链表即可方便表示用二叉链表即可方便表示。一般从根结点开始存储。一般从根结点开始存储。（相应地，访问树中结点时也只能从根开始）（相应地，访问树中结点时也只能从根开始）注：注：如果需要倒查某结点的双亲，可以再增加一个双亲如果需要倒查某结点的双亲，可以再增加一个双亲域（直接前趋）指针，将二叉链表变成三叉链表。域（直接前趋）指针，将二叉链表变成三叉链表。datadataleft_childleft_childright_childright_childdatadataleft_childleft_childright_childright_child例：例： ABECD A AB B D D C C E E 704、遍历二叉树（、遍历二叉树（Traversing Binary Tree）遍历定义遍历定义指按某条搜索路线遍访每个结点且不重复（又称周游）。指按某条搜索路线遍访每个结点且不重复（又称周游）。遍历用途遍历用途它是树结构插入、删除、修改、查找和排序运算的前提，它是树结构插入、删除、修改、查找和排序运算的前提， 是二叉树一切运算的基础和核心。是二叉树一切运算的基础和核心。 遍历规则遍历规则v二叉树由根、左子树、右子树构成，定义为二叉树由根、左子树、右子树构成，定义为D、 L、RvD、 L、R的组合定义了六种可能的遍历方案：的组合定义了六种可能的遍历方案： LDR, LRD, DLR, DRL, RDL, RLDv若限定先左后右若限定先左后右，则有三种实现方案：，则有三种实现方案： DLR LDR LRD先先 (根根)序遍历序遍历 中中 (根根)序遍历序遍历 后后(根根)序遍历序遍历 先序先序遍历的结果是：遍历的结果是：中序中序遍历的结果是：遍历的结果是：后序后序遍历的结果是：遍历的结果是：例例1： A B CD EA B D E CA B D E CD B E A CD B E A CD E B C AD E B C A遍历的算法实现：遍历的算法实现：用递归形式用递归形式715. 5. 二叉查找树二叉查找树特点：特点：“左小右大左小右大”，按中序遍历得到有小到大的排列，按中序遍历得到有小到大的排列检索检索(find) 折半查找折半查找插入插入(insert) 通过折半查找找到插入的位置（插入某个叶结点或在待插入方向上通过折半查找找到插入的位置（插入某个叶结点或在待插入方向上没有子结点的分支结点）没有子结点的分支结点）删除最小值结点删除最小值结点(deletemin) 删除整个树中最左边的结点，同时将其父结点中原来指向被删结点删除整个树中最左边的结点，同时将其父结点中原来指向被删结点的指针改为指向其右子结点。的指针改为指向其右子结点。删除给定值结点删除给定值结点(remove)若被删除节点的左右子结点非空，则用其右若被删除节点的左右子结点非空，则用其右子树中的最大节点取代被删除结点。子树中的最大节点取代被删除结点。主要操作主要操作优点：优点：提高检索、插入、删除等操作的效率，平均情况下提高检索、插入、删除等操作的效率，平均情况下(log n).726. 6. 堆与优先队列堆与优先队列1）堆）堆这种数据结构是实现这种数据结构是实现优先队列优先队列（按重要性或优先级来组织按重要性或优先级来组织的对象的对象）的一种较好的方法。）的一种较好的方法。2）堆的特点：）堆的特点：父大子小父大子小最大值堆最大值堆 父小子大父小子大最小值堆最小值堆3）堆的构建（最大值堆）：）堆的构建（最大值堆）：比较左右两个子结点的大小，若其比较左右两个子结点的大小，若其中较大的值大于父结点的值，则用具有较大值的子结点替换父结中较大的值大于父结点的值，则用具有较大值的子结点替换父结点。点。737.7.哈夫曼树及其应用哈夫曼树及其应用1.Huffman算法的思路：算法的思路： 权值大的结点用短路径，权值小的结点用长路径。权值大的结点用短路径，权值小的结点用长路径。2. 构造构造Huffman树的步骤：树的步骤： 对权值的合并、删除与替换对权值的合并、删除与替换3. Huffman编码规则：编码规则： 左左“0 0” 右右“1 1”，是一种前缀码，是一种前缀码也称为最小冗余编码、紧致码，等等，它是数据压缩学也称为最小冗余编码、紧致码，等等，它是数据压缩学的基础。的基础。74怎样生成怎样生成Huffman树？树？ 步骤如下：步骤如下：(1) 由给定的由给定的 n 个权值个权值w1, w2, , wn构成构成n棵二叉树的集合棵二叉树的集合（即森林）（即森林）F = T1, T2, , Tn ，其中每棵二叉树，其中每棵二叉树 Ti 中中只只有一个带权为有一个带权为 wi 的根结点，其左右子树均空。的根结点，其左右子树均空。(2) 在在F 中选取两棵根结点的权值最小的树中选取两棵根结点的权值最小的树 做为左右子树构做为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。左右子树上根结点的权值之和。(3) 在在F 中删去这两棵树，同时将新得到的二叉树加入中删去这两棵树，同时将新得到的二叉树加入 F中中。(4) 重复重复(2) 和和(3) , 直到直到 F 只含一棵树为止。这棵树便是赫夫只含一棵树为止。这棵树便是赫夫曼树。曼树。