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

一、什么是二叉树？

二叉树（Binary Tree）是计算机科学中常见的一种树形数据结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树可以是空树，也可以是非空树。在非空树中，每个节点都有一个唯一的父节点，除了根节点（存在的话）没有父节点。

二叉树具有特点：

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

2. 没有父节点的节点称为根节点。

3. 每个节点都有左右子节点，但可以是空节点。

4. 每个节点的左子节点都是比它小的值，右子节点都是比它大的值（这是二叉搜索树的特点）。

二、二叉树的基本操作

二叉树的基本操作包括创建、遍历、搜索、插入、删除等。是几种常见的二叉树操作：

1. 创建二叉树：

创建二叉树可以通过递归或迭代的进行。是一个使用递归创建二叉树的示例代码：

python

class TreeNode:

def __init__(self, value):

self.value = value

self.left = None

self.right = None

def create_binary_tree(values):

if not values:

return None

root = TreeNode(values[0])

queue = [root]

i = 1

while i < len(values):

current_node = queue.pop(0)

if values[i] is not None:

current_node.left = TreeNode(values[i])

queue.append(current_node.left)

i += 1

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

current_node.right = TreeNode(values[i])

queue.append(current_node.right)

i += 1

return root

2. 遍历二叉树：

二叉树的遍历有三种基本前序遍历、中序遍历和后序遍历。

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

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

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

是一个中序遍历的示例代码：

python

def inorder_traversal(root):

if root:

inorder_traversal(root.left)

print(root.value)

inorder_traversal(root.right)

3. 搜索二叉树：

在二叉搜索树中，搜索操作非常高效。给定一个值，搜索操作会在树中寻找该值，找到，则返回该节点；未找到，则返回None。

python

def search_binary_tree(root, value):

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

return root

if value < root.value:

return search_binary_tree(root.left, value)

else:

return search_binary_tree(root.right, value)

4. 插入节点：

在二叉树中插入新节点时，需要找到合适的插入位置，并保持二叉搜索树的特性。

python

def insert_binary_tree(root, value):

if root is None:

return TreeNode(value)

if value < root.value:

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

else:

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

return root

5. 删除节点：

删除节点是二叉树操作中的一个复杂部分，需要考虑不同的情况，如节点没有子节点、有一个子节点或有两个子节点。

python

def delete_binary_tree(root, value):

if root is None:

return None

if value < root.value:

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

elif value > root.value:

root.right = delete_binary_tree(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.value = min_larger_node.value

root.right = delete_binary_tree(root.right, min_larger_node.value)

return root

def find_min(node):

while node.left is not None:

node = node.left

return node

通过以上对二叉树及其基本操作的介绍，相信您对面试中可能遇到的有了更深入的了解。在实际面试中，这些可能会以不同的形式出现，但理解二叉树的基本概念和操作是解决这些的关键。