Trees

Definition

• A tree is a hierarchical data structure consisting of nodes, where each node has a value and zero or more child nodes.
• The topmost node is called the root node.
• Each node in the tree has a unique key or value.

Types of Trees

• Binary Tree: Each node has at most two child nodes (left child and right child).
• B-Tree: A self-balancing search tree that keeps data sorted and allows search, insert, and delete operations in logarithmic time.
• ** AVL Tree**: A self-balancing binary search tree that ensures the height of the tree remains relatively small.

Tree Terminology

• Root Node: The topmost node in the tree.
• Child Node: A node that has a parent node.
• Parent Node: A node that has one or more child nodes.
• Sibling Node: Nodes that have the same parent node.
• Leaf Node: A node with no child nodes.
• Internal Node: A node that has one or more child nodes.

Tree Operations

• Traversal: Visiting each node in the tree in a specific order (e.g., inorder, preorder, postorder).
• Insertion: Adding a new node to the tree while maintaining the tree's properties.
• Deletion: Removing a node from the tree while maintaining the tree's properties.
• Search: Finding a specific node in the tree.

Stacks

Definition

• A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle.
• A stack consists of a collection of elements, with two primary operations: push and pop.

Stack Operations

• Push: Adding an element to the top of the stack.
• Pop: Removing the top element from the stack.
• Peek: Viewing the top element of the stack without removing it.

Stack Properties

• LIFO: Last-In-First-Out, meaning the most recently added element is the first to be removed.
• FILO: First-In-Last-Out, meaning the first element added is the last to be removed.

Stack Applications

• Evaluating Postfix Expressions: Stacks are used to evaluate postfix expressions by parsing the expression from left to right.
• Implementing Recursive Algorithms: Stacks are used to implement recursive algorithms, allowing for efficient use of memory.
• Undo/Redo Functionality: Stacks are used to implement undo and redo functionality in applications.

树

定义

• 树是一种以节点为基础的层次结构，其中每个节点都具有值和零个或多个子节点。
• 树的顶部节点称为根节点。
• 树中的每个节点都具有唯一的键或值。

树的类型

• 二叉树：每个节点最多有两个子节点（左子树和右子树）。
• B-树：一种自平衡搜索树，能够在对数时间内进行搜索、插入和删除操作，并保持数据排序。
• AVL树：一种自平衡二叉搜索树，确保树的高度保持相对较小。

树的术语

• 根节点：树的顶部节点。
• 子节点：具有父节点的节点。
• 父节点：具有一个或多个子节点的节点。
• 兄弟节点：具有相同父节点的节点。
• 叶节点：没有子节点的节点。
• 内部节点：具有一个或多个子节点的节点。

树操作

• 遍历：按照特定顺序访问树中的每个节点（例如中序、前序、后序）。
• 插入：在保持树性质的情况下将新节点添加到树中。
• 删除：在保持树性质的情况下从树中删除节点。
• 搜索：在树中查找特定节点。

栈

定义

• 栈是一种以元素为基础的线性结构，遵循后进先出（LIFO）的原则。
• 栈由元素集合组成，具有两个主要操作：push和pop。

栈操作

• push：将元素添加到栈的顶部。
• pop：从栈的顶部删除元素。
• peek：查看栈的顶部元素，但不删除它。

栈属性

• LIFO：后进先出，意味着最recently添加的元素是第一个被删除的。
• FILO：先进后出，意味着最first添加的元素是最后一个被删除的。

栈应用

• 后缀表达式求值：栈用于从左到右解析后缀表达式。
• 递归算法实现：栈用于实现递归算法，使得内存使用更加高效。
• 撤销/重做功能：栈用于实现应用程序中的撤销和重做功能。