C S 313E Lecture Notes - Lecture 7: Binary Tree, Preorder, Linked List
Document Summary
Trees are hierarchical: you can measure the distance of a node from its root (level) All of the children of one node are independent of the children of another. If every node in a tree has a maximum of 2 children, the tree is a binary tree. Returns: a pointer to the left/right subtree. Creating a new binary tree with a value and installing it as the left/right child of tree t: t. insertleft(val)/t. insertright(val) A binary tree which is completely filled in from left to right. The bottom level may only be partially filled, but it must be full from left to right. Trees have no semantic organization by default. Heaps: look like a tree, but are organized as a linked list. If p is the parent of node n, then the value stored in node p is smaller than the value stored in node n. Take a node and swap it with the larger of its children if necessary.