[zell_ffhut]

Have been trying to write a piece of code, that will allow me to spot weather a tree is a correct Binary Tree, or not.

I feel im quite close to cracking it, but the whole thing is now really confusing me. Can anyone see where im going wrong?

procedure TraverseTree(var flag: integer;t: BinaryTree);
// Traverse Tree
  Begin

	If t <> nil then
	  Begin
		with t^ do
		  TraverseTree(flag, t^.left);
			if ((t^.left<> nil) AND (t^.right <> nil)) Then
			  begin
				if t^.left.data > t.data then
				  flag := flag + 1
				else
				  flag := flag;
			  end;
		  TraverseTree(flag, t^.right);
			if ((t^.left<> nil) AND (t^.right <> nil)) Then
			  begin
				if t^.right.data < t.data then
				  flag := flag + 1
				else
				  flag := flag;
			  end
	  End

  End;


function IsItABinarySearchTree(t:BinaryTree): TAnswer;

var ans: TAnswer;
	flag: integer;
begin

  flag := 0;
  ans.known := true;
  TraverseTree(flag, t);


  If flag = 0 then
	ans.answer := true
  Else
	ans.answer := False;

  IsItABinarySearchTree := ans
End;

Any help would be fantastic

[Advertisements]

Hello,

I had a few questions about the code and your goal. Are you testing to see if the tree is just a binary tree or a "full" binary tree or "perfect" tree? It looks from the code as if you are testing to see if it is a "full" binary tree since your data structure, BinaryTree, by default makes it a binary tree by only allowing 2 children per node.

What is the "data" variable that you are testing in each node? The values in each node have no bearing on whether it is a binary tree, that is only concerned with the data structure.

It appears from the code (if t^.left.data > t.data then ...) that you want the function to return a "false" value if one of the children values is greater than it's parent. From appearance of the code, it appears as if you are testing to see in the BinaryTree is a valid minimum binary heap?

Let us know your exact goals for testing the tree and we should be able to get it working.

Cheers,
Tom

Have been trying to write a piece of code, that will allow me to spot weather a tree is a correct Binary Tree, or not.

I feel im quite close to cracking it, but the whole thing is now really confusing me. Can anyone see where im going wrong?

procedure TraverseTree(var flag: integer;t: BinaryTree);
// Traverse Tree
  Begin

	If t <> nil then
	  Begin
		with t^ do
		  TraverseTree(flag, t^.left);
			if ((t^.left<> nil) AND (t^.right <> nil)) Then
			  begin
				if t^.left.data > t.data then
				  flag := flag + 1
				else
				  flag := flag;
			  end;
		  TraverseTree(flag, t^.right);
			if ((t^.left<> nil) AND (t^.right <> nil)) Then
			  begin
				if t^.right.data < t.data then
				  flag := flag + 1
				else
				  flag := flag;
			  end
	  End

  End;
function IsItABinarySearchTree(t:BinaryTree): TAnswer;

var ans: TAnswer;
	flag: integer;
begin

  flag := 0;
  ans.known := true;
  TraverseTree(flag, t);
  If flag = 0 then
	ans.answer := true
  Else
	ans.answer := False;

  IsItABinarySearchTree := ans
End;

Any help would be fantastic

[gust0208]

Hello,

I had a few questions about the code and your goal. Are you testing to see if the tree is just a binary tree or a "full" binary tree or "perfect" tree? It looks from the code as if you are testing to see if it is a "full" binary tree since your data structure, BinaryTree, by default makes it a binary tree by only allowing 2 children per node.

What is the "data" variable that you are testing in each node? The values in each node have no bearing on whether it is a binary tree, that is only concerned with the data structure.

It appears from the code (if t^.left.data > t.data then ...) that you want the function to return a "false" value if one of the children values is greater than it's parent. From appearance of the code, it appears as if you are testing to see in the BinaryTree is a valid minimum binary heap?

Let us know your exact goals for testing the tree and we should be able to get it working.

Cheers,
Tom

Have been trying to write a piece of code, that will allow me to spot weather a tree is a correct Binary Tree, or not.

I feel im quite close to cracking it, but the whole thing is now really confusing me. Can anyone see where im going wrong?

procedure TraverseTree(var flag: integer;t: BinaryTree);
// Traverse Tree
  Begin

	If t <> nil then
	  Begin
		with t^ do
		  TraverseTree(flag, t^.left);
			if ((t^.left<> nil) AND (t^.right <> nil)) Then
			  begin
				if t^.left.data > t.data then
				  flag := flag + 1
				else
				  flag := flag;
			  end;
		  TraverseTree(flag, t^.right);
			if ((t^.left<> nil) AND (t^.right <> nil)) Then
			  begin
				if t^.right.data < t.data then
				  flag := flag + 1
				else
				  flag := flag;
			  end
	  End

  End;
function IsItABinarySearchTree(t:BinaryTree): TAnswer;

var ans: TAnswer;
	flag: integer;
begin

  flag := 0;
  ans.known := true;
  TraverseTree(flag, t);
  If flag = 0 then
	ans.answer := true
  Else
	ans.answer := False;

  IsItABinarySearchTree := ans
End;

Any help would be fantastic

[zell_ffhut]

Hi Tom

Im trying to test it to see if it is a correct Binary Tree.

Each node contains an integer. Im trying to test the nodes to make sure the left child is lower, and the right child is higher then the parent node.

Chris.

[zell_ffhut]

Well, i've just had what i'd like to call "A moment of clairty" And i spoted a few massive flaws, and it now works

Thanks for your comments Tom, i think they help me realise the flaws!

[gust0208]

Hey, no worries and glad it worked out!

Feel free to post any more questions and I can keep myself brushed up on Pascal syntax.

Cheers,
Tom

Well, i've just had what i'd like to call "A moment of clairty" And i spoted a few massive flaws, and it now works

Thanks for your comments Tom, i think they help me realise the flaws!

[zell_ffhut]

If anyone knows how to find the height of branches in a binary tree, that would be a great help.

Im trying to implement a similar program now, but for AVL trees.

[gust0208]

Hello,

Finding the height would largely depend on how you are representing your binary tree structure (array, linked list, etc.). Basically, you just need a function to traverse the each node's subtree and increment a counter by one. By definition, you will get the height within one even if you just follow one node all the way down to the base (say, always follow the left child node). There is a great wikipedia page on balanced AVL trees, you can check it out here:

http://en.wikipedia.org/wiki/AVL_tree

Let us know what language you are working in and we should be able to help you out.

Cheers,
Tom

If anyone knows how to find the height of branches in a binary tree, that would be a great help.

Im trying to implement a similar program now, but for AVL trees.

[zell_ffhut]

working on pascal again