03. Tree and Binary Tree

Tree and Binary Tree

1. Basic Concepts of Trees

• Tree: A finite set of n (n≥0) nodes, including root node, subtrees, leaf nodes, degree, level, and depth
• Forest: A collection of several disjoint trees

2. Definition and Features of Binary Trees

• Each node has at most two children (left and right)
• Full binary tree, complete binary tree, binary search tree, balanced binary tree

3. Storage Structures

• Sequential storage: Use arrays to store complete binary trees
• Linked storage: Each node has a data field and left/right pointer fields

4. Traversal of Binary Trees

• Preorder traversal (root-left-right)
• Inorder traversal (left-root-right)
• Postorder traversal (left-right-root)
• Level-order traversal (by level)

5. Threaded Binary Trees

• Use null pointers to store predecessor/successor information to improve traversal efficiency

6. Storage and Traversal of Trees and Forests

• Child representation, parent representation, child-sibling representation
• Conversion between forests and binary trees

7. Applications

• Binary search tree, balanced binary tree, Huffman tree and Huffman coding

Exercises

1. Briefly describe the main differences between trees and binary trees.
2. What are the orders of preorder, inorder, and postorder traversals of a binary tree?
3. How do you store a complete binary tree using an array?
4. What is the purpose of a threaded binary tree?
5. What are the main applications of Huffman trees?