Create Time: 28th February 2024
Title:"[[BinaryTree]]"Author:- AllenYGY
status: DONE
tags:- NOTE
- DataStructure
- Tree
- Algorithm
created:2024-01-16updated: 2024-05-31T00:58
Tree
Basic Concepts
Binary Trees
Binary Search Trees
Basic Concepts
A tree is a collection of nodes
The collection can be empty
(recursive definition) If not empty, a tree consists of a distinguished node r (the root), and zero or more nonempty subtrees , each of whose roots are connected by a directed edge from root
Concept
Root and Leaf
Child and Parent
Every node except the root has one parent
A node can have an zero or more children
A leaf node has no children
Sibling
nodes with same parent
Path
a sequence of edges
Length of a path
Depth of a node
length of the unique path to the root
Height of a node
length of the longest path to a leaf
Tree height
the height of the root
the depth of the deepest leaf
Ancestor and descendant
If there is a path from n1 to n2
n1 is an ancestor of n2, n2 is a descendant of n1
Proper ancestor and proper descendant
Perfect Binary Tree
A perfect binary tree is the tree where a node can have 0 or 2 children and all leaves are at the same depth