数据结构授课教学课件BinaryTrees

1、Binary Trees SpecificationsA binary tree is either empty, or it consists of:a node called the root.A binary tree called the left subtree of the root.A binary tree called the right subtree of the root.SpecificationsThe recursive definition of the tree gives its nature character:A none empty binary tr

2、ee is consist of 2 sub binary tree A sub binary tree is consist of 2 smaller binary tree.The empty tree will usually be the base case for recursive algorithms and will determine when the algorithm stops.Examples of binary tree With three nodes, 5 different kinds of binary treesWith two nodes, 2 diff

3、erent kinds of binary trees. (tree have the sequence)SpecificationsBinary tree has five shapes：(1) Empty Binary Tree(2) Only root node(3) Left subtree is null. (4) Right subtree is null. (5) left and right subtree are all not null. SpecificationsM: the root of the treeA and F: sibling.C, E, H: leave

4、s.Height of the tree: 4Depth of M=1Depth of A=2Depth of B=3Internal Nodes: A, B, D, F, G,IExternal Nodes: M, C, E, HMCEH0AFBDGI9Full Binary Tree and Complete Binary TreeFull Binary TreeComplete Binary TreeCharacteristics of a binary treeThere are at most 2i-1 nodes in level i.(i1）.There are at most

5、2k-1 nodes in a binary tree with depth k. (k1）.For a binary tree with n0 leaf nodes and n2 nodes with degree 2, then :n0 = n2 + 1If a binary tree with depth k and 2k-1 nodes, it is called full binary tree. Exercises(1)(1) Consider a binary tree T of depth k1, what is the maximum number of nodes in T

6、?(2) If a binary tree have n nodes, what is its minimal depth? What is its maximum depth?2k-1Mimimum:Maximum: nExercises(2)Consider a binary tree T of depth 5, what is the maximum number of nodes in T and minimum number of nodes?Minimum:5Maximum: 25-1=31Basic operations of binary treeOperations rela

7、ted to a binary tree:（1）Construction of a empty binary tree.（2）Check if a binary is empty.（3）Get the number of nodes of a binary tree.（4）Get the height of a binary tree.（5）Clear an existing binary tree.（6）Insert a node in a binary tree.（7）Delete a node in a binary tree.（8）Traverse a binary tree.Rela

8、ted to anapplicationTraversal of binary treeTraversal is moving through all the nodes of the binary tree, visiting each node once and only once in turn.Standard Traversal Orders:PreOrder(VLR): visiting a node V, traversing the left subtree L and traversing the right subtree R.InOrder(LVR): traversin

9、g the left subtree L, visiting the node V and then traversing the right subtree R.PostOrder(LRV): traversing the left subtree L, traversing the right subtree R and then visiting the node V.Example of traversal of binary tree(1)PreOrder(VLR): 1,2,3,4,5InOrder(LVR): 1,4.3,5,2PostOrder(LRV): 4,5,3,2,11

10、2354Example of traversal of binary tree(2)Expression Tree:Build up from the simple operands and operators of an arithmetical or logical expression.Place simple operands as the leaves of a binary treePlace operators as the interior nodes.+aba+bxloglog x!nn!Expression: a+b log x n!preOrde(VLR):+ab log

11、 x!ninOrder(LVR): a+b log x n!postOrder(LRV): ab+ x log n!Implementation of Binary TreeSequential implementationLinked implementationSequential implementation Sequential implementationof binary tree00 1 2 3 4 5 6 7 8 990 1 2 3 4 5 6 7 8 9137894562012543678Sequential implementationof Complete binary

12、treeSequential implementationStore data elements of a binary tree using contiguous storage units.Numbering a node in a full binary treeIf a node with number i is stored in location j, then, its left child is stored in unit 2i+1, its right child is stored in unit 2i+2; its parent node is stored in Sh

13、ortage:wasting spaceDifficult to change dynamicallyRandomly used to implement the binary tree.Link Implementation of Binary TreeLink Implementation of Binary Tree leftChild data rightChilddataleftChildrightChildLinked implementation of Binary Tree(1)TempleteStruct Binary_node / data members: Entry d

14、ata;Binary_node *left;Binary_node *right;/ constructors:Binary_node();Binary_node(const Entry &x);Binary_node(const Entry &x, Binary_node null, Binary_node null);/ Entry is specified as an actual type by client codeTemplate Class Binary_tree Public: Binary_tree(); bool empty() const; void preorder(v

15、oid (*visit)(entry &); void inorder(void (*visit)(entry &); void postorder(void (*visit)(entry &); int size() const; void clear(); int height(); Binary_tree(); void insert(const Entry &); Binary_tree(const Binary_tree &original);Binary_tree & operator = (const Binary_tree &original);Protected: / add

16、 auxiliary function prototypes here Binary_node *root;Basic methods for a Binary TreeTemplateBinary_tree:Binary_tree() /constructor root= NULL;TemplateBinary_tree:empty() const return root= NULL;TemplateBinary_tree:inorder(void (*visit) (Entry &) /visit is a function pointer recursive_inorder(root,

17、visit);Inorder traverseTempleteVoid Binary_tree: recursive_inorder(Binary_node *sub_root, void (*visit) (Entry &)/* Pre: sub_root is either NULL or points to a subtree of the binary_tree post: The subtree has been traversed in in order sequence uses: the function recursive_inorder recursively / if(s

18、ub_root!=NULL) recursive_inorder(sub_root-left,visit); (*visit)(sub_root-data); recursive_inorder(sub_root-right, visit); Preorder traverseTempleteVoid Binary_tree: recursive_preorder(Binary_node *sub_root, void (*visit) (Entry &)/* Pre: sub_root is either NULL or points to a subtree of the binary_t

19、ree post: The subtree has been traversed in in order sequence uses: the function recursive_inorder recursively / if(sub_root!=NULL) (*visit)(sub_root-data); recursive_inorder(sub_root-left,visit); recursive_inorder(sub_root-right, visit); Postorder traverseTempleteVoid Binary_tree: recursive_postord

20、er(Binary_node *sub_root, void (*visit) (Entry &)/* Pre: sub_root is either NULL or points to a subtree of the binary_tree post: The subtree has been traversed in in order sequence uses: the function recursive_inorder recursively / if(sub_root!=NULL) recursive_inorder(sub_root-left,visit); recursive

21、_inorder(sub_root-right, visit); (*visit)(sub_root-data); Binary Search TreesA binary search tree is a binary tree that is either empty or in which every node has a key(within its data entry) and satisfies the following conditions:The key of the root(if it exist) is greater than the key in any node

22、in the left subtree of the root.The key of the root (if it exists) is less than the key in any node in the right subtree of the root.The left and right subtrees of the root are again binary search trees.No two entries in a binary search tree may have equal keys.C+ Definition TemplateClass Search_tre

23、e: public Binary_tree Public: Error_code insert(const Record &new_data); Error_code remove(const Record &old_data); Error_code tree_search(record &target) const;Private: /add auxiliary function prototypes hereEach record has associate key.Tree searchSearch through a linked binary search tree for an

24、entry with a particular target key.TemplateError_code Search_tree:tree_search(Record &target) const Error_code result=success; Binary_node *found=search_for_node(root,target); if(found =NULL) result=not_present; else target=found-data; return;Tree SearchTemplate / recursion versionError_code Search_

25、tree: search_for_node(Binary_node* sub_root, const record &target) const if(sub_root =NULL | sub_root-data=target) return sub_root; else if(sub_root-dataright,target); else return search_for_node(sub_root-left,target); Tree SearchTemplate / non recursion versionError_code Search_tree: search_for_nod

26、e(Binary_node* sub_root, const record &target) const while(sub_root !=NULL & sub_root-data != target) if(sub_root-data right; else sub_root=sub_root-left; return sub_root; Insertion into a binary search treeProcedure: if a Record with a key already belongs to the Search_tree a code of duplicate_erro

27、r is returned. Otherwise, the new Record is inserted into the tree in such a way that the properties of a binary search tree are preserved A code of success is returned.The method insert should never be used with keys that are already sorted into order.Insertion into binary search treeInsert：e、b、d、f

28、、a、g and c。C+ implementationTemplate Error_code Search_tree:insert(const Record &new_data) return search_and_insert(root, new_data);C+ implementationTemplate Error_code Search_tree:search_and_insert(Binary_node * &sub_root, const record &new_data) if(sub_root=NULL) sub_root=new Binary_node(new_data)

29、; return success; else if(new_data data) return search_and_insert(sub_root-left,new_data); else if(new_data sub_root-data) return search_and_insert(sub_root-right,new_data);Else return duplicate_error;Delete a Record from a Binary Search TreeMust keep that after deletion, the binary is still a binar

30、y search tree.ProcedureIf the node to be deleted is a leaf, delete it directly and update the pointer of its parent node.If the node to be deleted have only one none empty subtree, than let this subtree substitute the node to be deleted and becomes the subtree of its parents.If the node has two none

31、 empty subtrees, use the immediate predecessor of the node under inorder traversal.Delete a Record From a Binary Search Treetemplate int Search_tree:remove_root(Binary_node*& sub_root) if ( sub_root = NULL ) return 0; Binary_node* to_delete=sub_root; if (sub_root-right=NULL) sub_root = sub_root-left

32、; else if (sub_root-left=NULL) sub_root = sub_root-right; else to_delete=sub_root-left; /search for immediate predecessor / of the node under inorder traversal. Binary_node* parent=sub_root; while (to_delete-right != NULL) parent = to_delete; to_delete = to_delete-right; sub_root-data = to_delete-da

33、ta; if ( parent=sub_root ) sub_root-left = to_delete-left; else parent-right = to_delete-left; delete to_delete; return 1; template int Search_tree:remove(const Entry& target) return search_and_destroy(root, target);template int Search_tree:search_and_destroy(Binary_node*& sub_root, const Entry& tar

34、get) if ( sub_root=NULL | sub_root-data = target ) return remove_root(sub_root); else if ( sub_root-data right, target); else search_and_destroy(sub_root-left, target);Build a binary search treeint main() Search_tree charTree; charTree.insert(e); charTree.insert(b); charTree.insert(d); charTree.inse

35、rt(f); charTree.insert(a); charTree.insert(g); charTree.insert(c); coutPREORDERendl; charTree.preorder(print); coutendlINORDERendl; charTree.inorder(print); cout endlPOSTORDERendl; charTree.postorder(print); coutendl; char key = d; if (charTree.tree_search(key) coutd foundendl; key = m; if (!charTre

36、e.tree_search(key) coutm not foundendl; coutDeleting.; key = d; charTree.remove(key); coutendl INORDERendl; charTree.inorder(print); coutendl;void print(char& x) coutx ;Performance Insert d, b, a, c, f, e and gInsert a, b, c, d, e, f and gPerformanceThe method insert can usually insert a new node into a random binary search tree with n nodes in O(logn) steps.It is possible, but extremely unlikely that a random tree may degenerate so that insertions require as many as n steps.If the keys are inserted in sorted order into an empty tree, this degenerate case will occur.AVL tre