55class BinaryTreeNode
66{
77public:
8- BinaryTreeNode (void );
8+ BinaryTreeNode (void ) {
9+ m_right = nullptr ;
10+ m_left = nullptr ;
11+ };
912 BinaryTreeNode (int v) {
1013 m_value = v;
14+ m_right = nullptr ;
15+ m_left = nullptr ;
1116 };
12- int get_value () {
13- return m_value;
14- };
15-
17+
1618 // Setter Methods
19+ void set_value (int val) {
20+ m_value = val;
21+ };
1722 void setLeft (BinaryTreeNode* left){
1823 m_left = left;
1924 };
@@ -22,6 +27,9 @@ class BinaryTreeNode
2227 };
2328
2429 // Getter Methods
30+ int get_value () {
31+ return m_value;
32+ };
2533 BinaryTreeNode* getLeft (){
2634 return m_left;
2735 };
@@ -38,30 +46,30 @@ class BinaryTreeNode
3846class BinaryTree
3947{
4048public:
49+ BinaryTree (void );
4150 BinaryTree (int val)
4251 {
43- m_root = BinaryTreeNode (val);
52+ m_root = new BinaryTreeNode (val);
4453 };
45- ~BinaryTree (void );
46-
54+
4755 void insert (int val)
4856 {
49- if (val == m_root. get_value ())
57+ if (val == m_root-> get_value ())
5058 {
51- std::cout << " node with this value already exists."
59+ std::cout << " insert( " << val << " ) ERROR: node with this value already exists."
5260 }
5361 else
5462 {
55- BinaryTreeNode* currentNode = & m_root;
63+ BinaryTreeNode* currentNode = m_root;
5664 BinaryTreeNode* parentNode;
57- while (& currentNode != NULL ) {
65+ while (currentNode != nullptr ) {
5866 parentNode = currentNode;
5967 if (val < currentNode->get_value ()) {
6068 currentNode = currentNode->getLeft ();
6169 } else if (val > currentNode->get_value ()) {
6270 currentNode = currentNode->getRight ();
6371 } else {
64- std::cout << " node with this value already exists."
72+ std::cout << " insert( " << val << " ) ERROR: node with this value already exists."
6573 }
6674 }
6775 // add Node where child is null
@@ -73,17 +81,90 @@ class BinaryTree
7381
7482 }
7583 };
76- void remove (void );
84+
85+ // get Node by value
86+ BinaryTreeNode* getNode (int val) {
87+
88+ };
89+
90+ void remove (int val) {
91+ // 1. find Node
92+ BinaryTreeNode* currentNode = m_root;
93+ BinaryTreeNode* parentNode = nullptr ;
94+ std::cout << " currentNode(root) = " get_value () << std::endl;
95+ while (currentNode->get_value () != val && currentNode != nullptr ) {
96+ parentNode = currentNode;
97+ if (currentNode->get_value () < val) currentNode = currentNode->getRight ();
98+ else if (currentNode->get_value () > val) currentNode = currentNode->getLeft ();
99+ std::cout << " currentNode = " get_value () << std::endl;
100+ };
101+ if (currentNode == nullptr ) std::cout << " Node not found"
102+ else std::cout << " Node removed"
103+
104+ // 2. check children
105+ // a) no children -> just delete
106+ if (currentNode->getLeft () == nullptr && currentNode->getRight () == nullptr ) {
107+ if (parentNode->getLeft () != nullptr && parentNode->get_value () > val)
108+ parentNode->setLeft (nullptr );
109+ else parentNode->setRight (nullptr );
110+ };
111+ // b) 1 child -> link parent to only child
112+ BinaryTreeNode* grandchild;
113+ bool rightChildOnly = (currentNode->getLeft () == nullptr && currentNode->getRight () != nullptr );
114+ bool leftChildOnly = (currentNode->getLeft () != nullptr && currentNode->getRight () == nullptr );
115+
116+ if (leftChildOnly || rightChildOnly) {
117+ if (rightChildOnly) {
118+ grandchild = currentNode->getRight ();
119+ }
120+ else if (leftChildOnly) {
121+ grandchild = currentNode->getLeft ();
122+ }
123+ if (parentNode->getLeft ()->get_value () == currentNode->get_value ()) {
124+ parentNode->setLeft (grandchild);
125+ }
126+ else if (parentNode->getRight ()->get_value () == currentNode->get_value ()) {
127+ parentNode->setRight (grandchild);
128+ }
129+ }
130+ // c) 2 children -> get smallest descendant of right child
131+ BinaryTreeNode* smallestDescendant;
132+ BinaryTreeNode* replaceNode = currentNode;
133+
134+ if (currentNode->getLeft () != nullptr && currentNode->getRight () != nullptr ) {
135+ currentNode = currentNode->getRight ();
136+ while (currentNode != nullptr ) {
137+ smallestDescendant = currentNode;
138+ currentNode = currentNode->getLeft ();
139+ }
140+ replaceNode->set_value (smallestDescendant->get_value ());
141+ }
142+
143+ };
144+
145+
77146 int show ()
78147 {
79- return m_root. get_value ();
148+ return m_root-> get_value ();
80149 };
81150
82- BinaryTreeNode get_root ()
151+ BinaryTreeNode* get_root ()
83152 {
84153 return m_root;
85154 };
86155
156+ // print out Tree structure
157+ char * toString () {
158+ BinaryTreeNode* currentNode = m_root;
159+
160+ };
161+
87162private:
88- BinaryTreeNode m_root;
163+ char * printNode (BinaryTreeNode * currentNode) {
164+ BinaryTreeNode * parentNode;
165+ while (currentNode != nullptr ) {
166+
167+ }
168+ };
169+ BinaryTreeNode* m_root;
89170};
0 commit comments