计算机专业面试基础什么是二叉树及其基本操作？

一、什么是二叉树？

二叉树是一种重要的非线性数据结构，它是由n（n≥0）个结点组成的有限集合。在二叉树中，每个结点最多有两个子结点，分别称为左子结点和右子结点。二叉树的特点如下：

1. 每个结点最多有两个子结点。

2. 没有结点可以有多个父结点。

3. 根结点没有父结点。

4. 每个结点的左子树和右子树都是二叉树。

二叉树可以按照不同的分类，

– 满二叉树：每个结点都有两个子结点，且所有叶子结点都在同一层。

– 完全二叉树：除了最底层，其他层都被完全填满，且最底层从左到右填充。

– 平衡二叉树（AVL树）：任意节点的两个子树的高度最大差为1。

– 二叉搜索树（BST）：左子树上所有结点的值均小于它的根结点的值，右子树上所有结点的值均大于它的根结点的值。

二、二叉树的基本操作

二叉树的基本操作主要包括几种：

1. 创建二叉树：可以通过递归或非递归的创建二叉树。递归创建二叉树时，从根结点开始，分别创建左子树和右子树。

python

class TreeNode:

def __init__(self, value=0, left=None, right=None):

self.val = value

self.left = left

self.right = right

def create_binary_tree(arr):

if not arr:

return None

root = TreeNode(arr[0])

queue = [root]

i = 1

while i < len(arr):

current = queue.pop(0)

if arr[i] is not None:

current.left = TreeNode(arr[i])

queue.append(current.left)

i += 1

if i < len(arr) and arr[i] is not None:

current.right = TreeNode(arr[i])

queue.append(current.right)

i += 1

return root

2. 遍历二叉树：包括前序遍历、中序遍历和后序遍历。

– 前序遍历：先访问根结点，递归遍历左子树，递归遍历右子树。

– 中序遍历：先递归遍历左子树，访问根结点，递归遍历右子树。

– 后序遍历：先递归遍历左子树，递归遍历右子树，访问根结点。

python

def preorder_traversal(root):

if root:

print(root.val, end=' ')

preorder_traversal(root.left)

preorder_traversal(root.right)

def inorder_traversal(root):

if root:

inorder_traversal(root.left)

print(root.val, end=' ')

inorder_traversal(root.right)

def postorder_traversal(root):

if root:

postorder_traversal(root.left)

postorder_traversal(root.right)

print(root.val, end=' ')

3. 查找值：在二叉搜索树中，可以通过比较值来查找特定的结点。

python

def search(root, value):

if root is None or root.val == value:

return root

if root.val < value:

return search(root.right, value)

return search(root.left, value)

4. 插入新值：在二叉搜索树中，插入新值时需要找到合适的插入位置。

python

def insert(root, value):

if root is None:

return TreeNode(value)

if value < root.val:

root.left = insert(root.left, value)

else:

root.right = insert(root.right, value)

return root

5. 删除结点：在二叉搜索树中，删除结点是一个较为复杂的操作，需要考虑删除的是叶子结点、只有一个子结点的结点还是有两个子结点的结点。

python

def delete_node(root, value):

if root is None:

return root

if value < root.val:

root.left = delete_node(root.left, value)

elif value > root.val:

root.right = delete_node(root.right, value)

else:

if root.left is None:

return root.right

elif root.right is None:

return root.left

min_larger_node = find_min(root.right)

root.val = min_larger_node.val

root.right = delete_node(root.right, min_larger_node.val)

return root

def find_min(node):

current = node

while current.left is not None:

current = current.left

return current

以上是二叉树的基本概念和操作，这些是计算机专业面试中常见的基础。掌握这些知识对于深入理解和应用二叉树数据结构至关重要。