DOC PREVIEW
MASON CS 310 - Binary Trees

This preview shows page 1-2-3-4-5 out of 16 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CS 310 Binary Trees, Page 1'&$%Binary Trees• Unlike previous data structures, trees are nonlinear.• A binary tree is a finite set of nodes. The set might be empty(no nodes, which is called the empty tree). But if the tree isnot empty, it follows the following rules:1. There is a distinguished node, called the root.2. Each node may be associated with two child nodes, calledthe left child and the right child.3. Each node, except the root, has exactly one parent; the roothas no parent.CS 310 Binary Trees, Page 2'&$%ExamplesABCDEFGCS 310 Binary Trees, Page 3'&$%147 2539480910CS 310 Binary Trees, Page 4'&$%ABCDCS 310 Binary Trees, Page 5'&$%CS 310 Binary Trees, Page 6'&$%Terminology• leaf (terminal) – node with no children• parent, child, sibling, ancestor, descendant• level of a node – root at level 1, the child(ren) of root at level2, and so forth.• height of a tree – the maximum level of any of its nodes• full binary trees – every leaf is at the same level and everynon-leaf node has two children• complete binary trees – a complete binary tree of height K is afull binary tree of height K − 1 plus a set of leaves at level Koccupying the leftmost positions.CS 310 Binary Trees, Page 7'&$%Binary Tree Properties• The maximum number of nodes on level i of a binary tree is2i−1, i ≥ 1• The maximum number of nodes in a binary tree of height K is2K− 1, k ≥ 1• The minimum number of nodes in a binary tree of height K is ?CS 310 Binary Trees, Page 8'&$%Another Definition: Recursive ThinkingA binary tree is a finite set of nodes which is either empty orconsists of a root and two disjoint binary trees, called the leftsubtree and the right subtree.CS 310 Binary Trees, Page 9'&$%Pointer RepresentationAB CD E F GH I JCS 310 Binary Trees, Page 10'&$%C++ Implementationstruct Binary_node {int data;Binary_node *left;Binary_node *right;Binary_node() { data = 0; left = right = NULL; }Binary_node (const int x){ data = x; left = right = NULL; }};Collapsing the two constructors using default parameter value:Binary node (const int x =0){ data = x; left = right = NULL; };CS 310 Binary Trees, Page 11'&$%class Binary_tree {private:Binary_node* root;// We may need to add auxiliary functions later on.public:Binary_tree () { root=NULL; }~Binary_tree ();bool empty() const { return root==NULL; }int height() const;void insert (const int); // not discussed in this talk// Tree traversal methodsvoid preorder ();void inorder ();void postorder ();};CS 310 Binary Trees, Page 12'&$%Computing Tree HeightFirst, we add an auxiliary (and private) function:int Binary_tree::height (Binary_node *r){if (r == NULL) return 0;}CS 310 Binary Trees, Page 13'&$%Visiualing Recuisive ComputationLet us consider the tree on page 3.height (→ 14) {height (→ 7) {height (→ 0) {height (NULL) ⇒ 0height (NULL) ⇒ 0} ⇒ 1height (→ 48) {height (NULL) → 0height (→ 9) {height (NULL) ⇒ 0height (NULL) ⇒ 0} ⇒ 1} ⇒ 2} ⇒ 3height (→ 25) {height (NULL) ⇒ 0height (→ 39) {height (→ 10) { . . . } ⇒ 1height (NULL) ⇒ 0} ⇒ 2} ⇒ 3} ⇒ 4CS 310 Binary Trees, Page 14'&$%The public height() function simply calls upon its privatecounterpart to get the real job done.int Binary_tree::height (){return height (root);}CS 310 Binary Trees, Page 15'&$%Traversals• Inorder – left subtree, root, right subtree• Preorder – root, left subtree, right subtree• Postorder – left subtree, right subtree, rootCS 310 Binary Trees, Page 16'&$%Inordervoid Binary_tree::inorder (Binary_node* p){if (p != NULL){inorder (p->left);cout << p->data << ’\n’;inorder (p->right);}}CS 310 Binary Trees, Page 17'&$%Preordervoid Binary_tree::preorder (Binary_node* p){if (p != NULL){cout << p->data << ’\n’;preorder (p->left);preorder (p->right);}}CS 310 Binary Trees, Page 18'&$%Postordervoid Binary_tree::postorder (Binary_node* p){if (p != NULL){postorder (p->left);postorder (p->right);cout << p->data << ’\n’;}}CS 310 Binary Trees, Page 19'&$%ExamplesLet use the tree shown on page 3.• inorder:• preorder:• postorder:And the tree shown in page 9.• inorder:• preorder:• postorder:CS 310 Binary Trees, Page 20'&$%Binary Search TreeA binary search tree is a binary tree that is either empty orsatisfies the following conditions:• The root is greater than all nodes in its left subtree.• The root is less than all nodes in its right subtree.• The left and right subtrees are also binary search trees.We do not allow identical nodes.CS 310 Binary Trees, Page 21'&$%Examples7101312710131232 45814CS 310 Binary Trees, Page 22'&$%C++ Implementationclass Search_tree {private:Binary_node* root;// We may need to add auxiliary functions later on.public:Search_tree () { root=NULL; }~Search_tree ();void search (const int) const;void insert (const int);void remove (const int);// height, empty, traversals, etc.};CS 310 Binary Trees, Page 23'&$%Searching in a BSTAgain, the public search function simply calls an auxiliary, privatefunction, using root as the first parameter.bool Search_tree::search (Binary_node *p, int k){}CS 310 Binary Trees, Page 24'&$%Insertion into A BSTbool Search_tree::insert (Binary_node*& p, int k){}CS 310 Binary Trees, Page 25'&$%ExampleDraw the BST resulted from inserting the sequence 25, 49, 30, 8,66, 33, 45, 79, 12, and 29.Do the same for 0, 1, 2, 3, 4, and 5.CS 310 Binary Trees, Page 26'&$%Deleting from A BSTCase 2: No Left Child32 4101312865Case 1: No Children32 4101312865CS 310 Binary Trees, Page 27'&$%Case 4: Two ChildrenCase 3: No Right Child32 410131286532 4101312865CS 310 Binary Trees, Page 28'&$%bool Search_tree::remove (Binary_node*& root, int target){// Search for targetif (root == NULL)return false;if (root->data > target)return remove (root->left, target);if (root->data < target)return remove (root->right, target);CS 310 Binary Trees, Page 29'&$%// root->_data == target (target found)// Let us see how many children the root hasif (root->left==NULL){root = root->right;return true;}if (root->right==NULL){root = root->left;return true;}CS 310 Binary Trees, Page 30'&$%// root has two childrenBinary_node* p = root->left;while (p->right != NULL)p = p->right;int tmp = p->data;p->data = root->data;r->data = tmp;return remove (root->left, target);} /* end of remove */CS 310 Binary Trees, Page 31'&$%Handling Two-Children Cases without CopyingBinary_node* p = root->left;while (p->right != NULL){p = p->right;}ListNode*


View Full Document

MASON CS 310 - Binary Trees

Download Binary Trees
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Binary Trees and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Binary Trees 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?