Representing trees

Now we鈥檙e ready to work with some tree search and traversal algorithms. But that brings up the question of how we represent a tree? What data structures are suitable?

Three Representations

Here we present how to represent a tree, including adjacency list, adjacency matrix, incidence matrix, and simple L/R object-oriented approach.

Representing trees

Note: You will not be assessed on incidence matrix.

Resources

• Representing_Trees.pdf

Further reading

Comprehension check

1. A data structure that is well-suited to sparse graphs like trees is _____________________.
2. A data structure that is well-suited to dense graphs is _____________________.
3. With a binary tree all we need are pointers to __________ and ___________ children, to represent our data.
4. In an adjacency matrix, if we take a column or row sum, this equals the _______________ of the corresponding node.
5. In an adjacency matrix, the complexity of finding whether or not a node is adjacent to another node is ____________ than doing so with an adjacency list. Less or greater?

Answers: ss菨l / 菨菨晒苾菨p / 蕠丧苾岽壣� 鈥櫴嚿熐漧 / x岽壣故嚿惿� 蕩蓴u菨蓴蓯删p蓯 / 蕠s岽塴 蕩蓴u菨蓴蓯删p蓯

Copyright 漏 2023鈥�2025 Clayton Cafiero

No generative AI was used in producing this material. This was written the old-fashioned way.