Jump to content

Welcome to Geeks to Go - Register now for FREE

Geeks To Go is a helpful hub, where thousands of volunteer geeks quickly serve friendly answers and support. Check out the forums and get free advice from the experts. Register now to gain access to all of our features, it's FREE and only takes one minute. Once registered and logged in, you will be able to create topics, post replies to existing threads, give reputation to your fellow members, get your own private messenger, post status updates, manage your profile and so much more.

Create Account How it Works
Photo

Pascal Help - Binary Trees


  • Please log in to reply

#1
zell_ffhut

zell_ffhut

    Member

  • Member
  • PipPip
  • 34 posts
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 :tazz:
  • 0

Advertisements


#2
gust0208

gust0208

    Member

  • Member
  • PipPipPip
  • 311 posts
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 :tazz:


  • 0

#3
zell_ffhut

zell_ffhut

    Member

  • Topic Starter
  • Member
  • PipPip
  • 34 posts
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.
  • 0

#4
zell_ffhut

zell_ffhut

    Member

  • Topic Starter
  • Member
  • PipPip
  • 34 posts
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 :tazz:

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

#5
gust0208

gust0208

    Member

  • Member
  • PipPipPip
  • 311 posts
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 :tazz:

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


  • 0

#6
zell_ffhut

zell_ffhut

    Member

  • Topic Starter
  • Member
  • PipPip
  • 34 posts
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.
  • 0

#7
gust0208

gust0208

    Member

  • Member
  • PipPipPip
  • 311 posts
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.


  • 0

#8
zell_ffhut

zell_ffhut

    Member

  • Topic Starter
  • Member
  • PipPip
  • 34 posts
working on pascal again :tazz:
  • 0






Similar Topics

0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users

As Featured On:

Microsoft Yahoo BBC MSN PC Magazine Washington Post HP