1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
|
#include <iostream>
using namespace std;
// Code Fragment: LinkedBinaryTree1
template <typename Object>
class LinkedBinaryTree {
protected:
// ... (insert Node definition here)
//Code Fragment: Node
struct Node { // a node in the tree
Object element; // the element
Node* parent; // parent
Node* left; // left child
Node* right; // right child
Node() : element(Object()) // default constructor
{ parent = left = right = NULL; }
Node* sibling() const { // get our sibling
return (this == parent->left ? parent->right : parent->left);
}
};
typedef Node* NodePtr; // a node pointer
public:
// ... (insert Position definition here)
//Code Fragment: Position
class Position { // position in the tree
private:
NodePtr node; // pointer to the node
public:
Position(NodePtr n = NULL) // constructor
{ node = n; }
Object& element() const // get element
{ return node->element; }
bool isNull() const // null position?
{ return node == NULL; }
friend class LinkedBinaryTree; // allow access
};
private: // member data
NodePtr theRoot; // pointer to the root
int sz; // number of nodes
protected: // protected utilities
// ... (insert LinkedBinaryTree utilities here)
//Code Fragment: LinkedBinaryTree2
// ... (utilities for LinkedBinaryTree)
NodePtr nodePtr(const Position& v) const // convert to NodePtr
{ return v.node; }
bool isExternal(NodePtr n) const // is node external?
{ return (n->left == NULL && n->right == NULL); }
bool isInternal(NodePtr n) const // is node internal?
{ return ! isExternal(n); }
bool isRoot(NodePtr n) const // is node the root?
{ return (n == theRoot); }
void setRoot(NodePtr r) // make r the root
{ theRoot = r; r->parent = NULL; }
void replaceElement(NodePtr n, const Object& o) // replace element
{ n->element = o; }
void swapElements(NodePtr n, NodePtr w) { // swap elements
Object temp = w->element;
w->element = n->element;
n->element = temp;
}
void expandExternal(NodePtr n) { // expand external node
n->left = new Node; n->left->parent = n;
n->right = new Node; n->right->parent = n;
sz += 2;
}
NodePtr removeAboveExternal(NodePtr n) { // remove n and parent
NodePtr p = n->parent;
NodePtr s = n->sibling();
if (isRoot(p)) setRoot(s); // p was root; now s is
else {
NodePtr g = p->parent; // the grandparent
if (p == g->left) g->left = s; // replace parent by sibling
else g->right = s;
s->parent = g;
}
delete n; delete p; // delete removed nodes
sz -= 2; // two fewer nodes
return s;
}
public:
LinkedBinaryTree() // constructor
{ theRoot = new Node; sz = 1; }
int size() const // size of tree
{ return sz; }
bool isEmpty() const // is tree empty?
{ return (sz == 0); }
Position root() const // returns root
{ return Position(theRoot); }
Position leftChild(const Position& v) const // returns left child
{ return Position(nodePtr(v)->left); }
Position rightChild(const Position& v) const // returns right child
{ return Position(nodePtr(v)->right); }
// ... parent(), and sibling() are omitted but similar)
bool isRoot(const Position& v) const // is v the root?
{ return isRoot(nodePtr(v)); }
bool isInternal(const Position& v) const // is v internal?
{ return isInternal(nodePtr(v)); }
bool isExternal(const Position& v) const // is v external?
{ return isExternal(nodePtr(v)); }
void replaceElement(const Position& v, const Object& o)
{ replaceElement(nodePtr(v), o); } // replace element
void swapElements(const Position& v, const Position& w)
{ swapElements(nodePtr(v), nodePtr(w)); } // swap elements
void expandExternal(const Position& v)
{ expandExternal(nodePtr(v)); } // expand external node
Position removeAboveExternal(const Position& v) // remove v and parent
{ return Position(removeAboveExternal(nodePtr(v))); }
// ... (housekeeping and iterator functions omitted)
};
class Int {
public:
Int() { counter++; num = counter; }
private:
static int counter;
int num;
friend ostream& operator<<(ostream& out, Int i);
};
ostream& operator<<(ostream& out, Int i)
{ out << i.num << " ";
return out;
}
typedef LinkedBinaryTree<Int> Tree;
typedef Tree::Position Position;
void binaryInorderPrint(const Tree& T, const Position& v)
{ if (T.isInternal(v)) // visit left child
binaryInorderPrint(T, T.leftChild(v));
cout << v.element(); // print element
if (T.isInternal(v)) // visit right child
binaryInorderPrint(T, T.rightChild(v));
}
int Int::counter = 0;
int main()
{ LinkedBinaryTree<Int> btree;
btree.expandExternal(btree.root());
binaryInorderPrint(btree, btree.root());
cout << endl;
btree.expandExternal(btree.leftChild(btree.root()));
binaryInorderPrint(btree, btree.root());
return 0;
}
| |
