Chapter 10 BINARY TREES 1. General Binary trees 2. Binary Search Trees 3. Building a Binary Search Tree I4. Height Balance: AVL Trees I5. Splay Trees I6. Pointers and Pitfalls
Chapter 10 BINARY TREES 1. General Binary Trees 2. Binary Search Trees 3. Building a Binary Search Tree 4. Height Balance: AVL Trees 5. Splay Trees 6. Pointers and Pitfalls
10.1 Binary Trees 1. Definitions DEFINITION A binary tree is either empty, or it consists of a node called the root together with two binary trees called the left subtree and the right subtree of the root (c)left subtree isn't empty (d)right subtree isn't empty d O (a) Empty (b)only root △ △△△ Basic shaper of Binary tree (e)both left right are not empty
10.1 Binary Trees DEFINITION A binary tree is either empty, or it consists of a node called the root together with two binary trees called the left subtree and the right subtree of the root. 1. Definitions
2. Traversal of Binary Trees postorder At a given node there are three Ho in some order: Visit the node itself ere ts left subtree (L); traverse its rib sukeVA. Ty Are are six ways to arrange these tasks VLR LVR RV VRL RVL RLV By standard convention, these are reduced to three by considering only the ways in which the left subtree is traversed before the right These three names are chosen according to the step at which the given node is visited
2. Traversal of Binary Trees At a given node there are three tasks to do in some order: Visit the node itself (V); traverse its left subtree (L); traverse its right subtree (R). There are six ways to arrange these tasks: VLR LVR LRV VRL RVL RLV By standard convention, these are reduced to three by considering only the ways in which the left subtree is traversed before the right. postorder preorder inorder These three names are chosen according to the step at which the given node is visited
With preorder traversal we first visit a node, then traverse its left subtree, and then traverse its right subtree With inorder traversal we first traverse the left subtree, then visit the node, and then traverse its right subtree. With postorder traversal we first traverse the left subtree, then traverse the right subtree, and nally visit the node See pg 432-434
◆With preorder traversal we first visit a node, then traverse its left subtree, and then traverse its right subtree. ◆With inorder traversal we first traverse the left subtree, then visit the node, and then traverse its right subtree. ◆With postorder traversal we first traverse the left subtree, then traverse the right subtree, and nally visit the node. See pg.432-434
Expression tree b b Epression: a+b logx n! a(bxc)(a< b)or(c< d) Preorder: +a b log x! a×bcor<ab<cd nordel a +b log x ni a-bxc a< b or c< d Postorder: a b+ x log n! a bcx- a b< cd < or
Expression tree
x=(-b+(b↑24×axc)↑0.5)/(2×a)
x = (-b+(b↑2-4×a×c)↑0.5) / (2×a)
3. Linked implementation of Binary Trees Node structure of Binary Trees example data left right Ron Amy Ann
3. Linked implementation of Binary Trees Node structure of Binary Trees example
Linked Binary Trees Specifications Binary trees class 二叉树根结点指针 template class Binary tree i public ∥ Add methods here. protected l/ Add auxiliary function p/ototypes here Binary node *root
Linked Binary Trees Specifications template class Binary_tree { public: // Add methods here. protected: // Add auxiliary function prototypes here. Binary_node *root; }; Binary trees class 二叉树根结点指针
Binary node class 指向右孩子的指针 template struct Binary node I Entry data; Binary_ node *left Binary_ node *right Binary_ node Binary_ node(const Entry x);
template struct Binary_node { Entry data; Binary_node *left; Binary_node *right; Binary_node( ); Binary_node(const Entry & x); }; Binary node class 指向右孩子的指针 指向左孩子的指针 数据域
Inorder traversal: 调田递旧由序 递归中序遍历函数 template 多一个参数 void Binary-treeEntry?:inorder(void (*visit)(Er &) i recursive inorder (root, visit);] template void Binary_treEntry> recursive inorder(Binary node *sub root, void visit)(Entry &) / Pre: sub_ root is either NULL or points to a subtree of the inary_tree Post: The subtree has been traversed in inorder sequence. * Iif (sub root E NULL i recursive inorder(sub root->left, visit) Visit)(sub root->data); recursive_inorder(sub root->right, visit);
template void Binary_tree::inorder(void (*visit)(Entry &)) { recursive_inorder(root, visit); } template void Binary_tree:: recursive_inorder(Binary_node *sub_root, void (*visit)(Entry &)) /* Pre: sub_root is either NULL or points to a subtree of the inary_tree. Post: The subtree has been traversed in inorder sequence. */ { if (sub_root != NULL) { recursive_inorder(sub_root->left, visit); (*visit)(sub_root->data); recursive_inorder(sub_root->right, visit); } } Inorder traversal: method 函数参数 (访问数据) 调用递归中序 递归中序遍历函数 遍历函数 多一个参数