Additional binary tree
operations
Copying binary trees
can modify the postorder traversal algorithm
2
testing equality
determine the equality of two binary trees
– equivalent if two binary trees have the same topology and
the identical data
topology: every branch in one tree corresponds to a branch in
the second tree in the same order
3
The satisfiability problem
the formulas of the propositional calculus
– a variable is an expression
– if x and y are expressions, x ∧ y, x ∨ y, ￢ x are
expressions
– can use parentheses to alter the normal order of evaluation
– x1 ∨ (x2 ∧ ￢ x3)
the satisfiability problem for formulas of propositional
calculus
– ask whether or not there is an assignment of values to the
variables that causes the value of the expression to be true
4
The satisfiability problem (Cont.)
– (x1 ∧ ￢ x2) ∨ ( ￢ x1 ∧ x3) ∨ ￢ x3
let (x1, x2, x3) take on all possible combinations of true and false
check the formula for each combination
to evaluate an expression, need to traverse its tree in postorder
5
The satisfiability problem (Cont.)
– define this node structure in C
– True and False : constants
typedef enum {not,and,or,true,false} logical;
typedef struct node *treePointer;
typedef struct node {
treePointer leftChild;
logical data;
short int value;
treePointer rightChild;
}; 6
The satisfiability problem (Cont.)
7
Threaded binary trees
Threads
there are more 0-links than actual pointers
– n + 1 0-links and 2n total links where # of nodes
in n
replace the 0-links by pointers, called threads
1) replace the rightChild field(value = 0) in node p
by the inorder successor of p
2) replace the leftChild(value = 0) at node p by the
inorder predecessor of p
9
Threads (Cont.)
distinguish between threads and normal pointers
– add two boolean fields, leftThread and rightThread
– if tleftThread == TRUE, then tleftChild is a thread
10
Threads (Cont.)
assume a head node for all threaded binary
trees
– the original tree is the left subtree of the head
node
11
Threads (Cont.)
12
Inorder traversal of a threaded
binary tree
if xrightThread == true,
then the inorder successor of x is xrightChild
if xRightThread == false,
then the inorder successor of x is obtained by
following a path of left-child links from the right child
of x until a node with leftThread == true
13
Inorder traversal of a threaded binary
tree (Cont.)
14
Inserting a node into a threaded
binary tree
how to make insertions into a threaded tree
the case of inserting r as the right child of a
node s
– if s has an empty right subtree, then a simple
insertion
– if s has non-empty right subtree, then make this right
subtree
as the right subtree of r
15
Inserting a node into a threaded binary
tree (Cont.)
16
Inserting a node into a threaded binary
tree (Cont.)
17
