Click here to Skip to main content
15,891,888 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
See more:
Hi, this program searches in binary tree, knots with only one child. My question is, how to fix it so it can searches for knots with two children?

C++
#include <iostream>
using namespace std;

struct elem {
	int key;
	elem *left;
	elem *right;
} *root = NULL;

void preorder(elem *t) 
{
	if (t)

	{
		cout << t->key << "\t";
		preorder(t->left);
		preorder(t->right);
	}

}

void inorder(elem *t) 
{
	if (t)
	{
		inorder(t->left);
		cout << t->key << "\t";
		inorder(t->right);
	}
}

void add(int n, elem *&t)
{
	if (t == NULL)
	{
		t = new elem; t->key = n;
		t->left = NULL; t->right = NULL;
	}
	else
	{
		if (t->key>n)
			add(n, t->left);
		else if (t->key<n)
			add(n, t->right);
	}
}

void postorder(elem *t) 
{
	if (t)
	{
		postorder(t->left);
		postorder(t->right);
		cout << t->key << "\t";
	}
}


int height(elem * t)
{
	if (t == NULL)
		return -1;
	int u = height(t->left);
	int v = height(t->right);
	if (u > v)
		return u + 1;
	return v + 1;
}


void printnode(int n, int h)
{
	for (int i = 0; i<h; i++)
		cout << "\t";
	cout << n << endl;
}


void show(elem *t, int h)
{
	if (t == NULL)
		return;
	show(t->right, h + 1);
	printnode(t->key, h);
	show(t->left, h + 1);
}


int count(elem *t)
{
	if (t == NULL) return 0;  return count(t->left) + count(t->right) + 1;
}

 
int count1(elem *t)
{
	if (t == NULL) return 0;
	return count1(t->left) + count1(t->right) + (t->left == NULL) ^ (t->right == NULL);
}

void main()
{
	int a;
	cout << "\n Add elements" << endl;

	do
	{
		cin >> a;
		if (a>0)
			add(a, root);
	} while (a>0);

	int r = count(root);
	cout << "Number of knots " << r << endl;
	int r1 = count1(root);
	cout << "Number of knots with one child" << r1;
	cout << endl;
	cout << endl;
	show(root, 0);
	system("pause");
}


What I have tried:

I have tried to change some things, but none of them worked like i want.
Posted
Updated 9-May-16 7:50am
Comments
Sergey Alexandrovich Kryukov 9-May-16 12:10pm    
Not clear.
—SA
[no name] 9-May-16 12:24pm    
The code or the task?

Your problem is operator precedence: + operator have a priority over ^ operator so that your expression is evaluated as

C++
return (count1(t->left) + count1(t->right) + (t->left == NULL)) ^ (t->right == NULL);


To correct this, you need to use brackets to change the evaluation order:

C++
return count1(t->left) + count1(t->right) + ((t->left == NULL) ^ (t->right == NULL));
 
Share this answer
 
v2
Comments
[no name] 9-May-16 13:27pm    
It says that there are 0 knots with two children..
Sorry, that fix was for your initial program (searching for nodes with the only child). It contained an operator precedence error.
If you want to search for nodes with two children, use this line instead:
C++
return count1(t->left) + count1(t->right) + (t->left != NULL && t->right != NULL ? 1 : 0);
 
Share this answer
 
v2
Comments
[no name] 9-May-16 14:06pm    
Thanks a lot but did you try to run it, cuz it does not give a correct answer either.
jeron1 9-May-16 15:11pm    
Have you tried stepping through the code using a debugger?
Ronn2000 10-May-16 5:24am    
Yes, I just tried it, and it worked. What input numbers do you use for testing?
[no name] 10-May-16 6:39am    
50 60 40 70 30 45 55
i tried it now again and it worked. thanks a lot!
[no name] 9-May-16 16:02pm    
I know where should be edited, I just do not know how.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900