Scribd
Upload
136 views

Additional Binary Tree Operations

The document discusses binary trees and the satisfiability problem. It introduces threaded binary trees as a way to reduce wasted space in binary trees by replacing unused child pointers with threads. It describes how to distinguish threads from normal pointers, perform an inorder traversal, and insert new nodes while maintaining the tree's threaded properties.

Uploaded by

Sang Hyeok Kim
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
136 views

Additional Binary Tree Operations

The document discusses binary trees and the satisfiability problem. It introduces threaded binary trees as a way to reduce wasted space in binary trees by replacing unused child pointers with threads. It describes how to distinguish threads from normal pointers, perform an inorder traversal, and insert new nodes while maintaining the tree's threaded properties.

Uploaded by

Sang Hyeok Kim
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
You are on page 1/ 17

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 tleftThread == TRUE, then tleftChild 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 xrightThread == true,
then the inorder successor of x is xrightChild

 if xRightThread == 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

You might also like