What does "tree" refer to in breadth and depth based searches?

I need some working snippets on C++ code regarding breadth/depth first searches. Also, in the links below, when using the term tree, is it in reference to a binary tree or more specefically a red and black tree? Or is this a more abstract tree of sorts? Does anyone have a link to working code for these searches...along with constructing the tree?

Tree seems to refer to some sort of constuct with in the "graph"? I believe this is开发者_开发知识库 some sort of math I have not taken yet.

breadth or depth first search 1

breadth or depth first search 2

---

The tree in question is the thing they're searching. It's kinda hard to understand search algorithms without knowing what it is they are searching through.

A tree is a type of graph. A graph is a series of nodes (which presumably represent some data) with connections between certain nodes. A tree is a graph where the connections between nodes form a hierarchy. For any given node in the graph, it has exactly one "parent" that points to it, and it points to zero or more child nodes. And the nodes cannot form circles; a parent cannot point to a child who points to that parent.

Basically, like branches on a tree.

---

The term "tree" refers to any data structure that can be abstractly looked at as a tree.

A "tree" is a data structure in which there are parent nodes and child nodes, and each child has a single parent, with a single "root" node not having a parent.

If a node in your tree has multiple parents, it is called a "graph".

---

A tree is a special case of a directed acyclic graph (basically a bunch of 'nodes' with arrows ('edges') pointing at each other, such that there cannot be a loop of arrows) in which the following two conditions hold:

• No node has more than one incoming edge
• There exists a single distinguished node (the 'root') from which all other nodes are reachable.

The nodes reachable via an outgoing edge from some node N are often called N's children.

Breadth-first and depth-first search apply to generic trees (indeed, they apply to all DAGs). However there are some more specific types:

• Binary trees are trees in which no node has more than two outgoing edges; outgoing edges are labelled, usually as 'left' and 'right'
• Search trees are binary trees in which each node has a key; further, the key in some node N is greater than the child on its left edge (if any) and less than the child on its right edge (if any). This allows for very fast searching for a specific key.
• Red-black trees are a specific kind of search tree in which a moderately complex algorithm is used to make sure all keys are approximately the same distance from the root.