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

一、什么是二叉树

二叉树（Binary Tree）是一种常见的树形数据结构，每个节点最多有两个子节点，称为左子节点和右子节点。二叉树在计算机科学中有着广泛的应用，如数据结构、算法设计、数据库索引等。

二叉树的定义如下：

– 根节点（Root）：二叉树的顶部节点，没有父节点。

– 节点（Node）：包括一个数据元素和两个可能指向子节点的指针（左指针和右指针）。

– 空二叉树：没有任何节点的二叉树。

– 深度（Depth）：根节点到最远叶子节点的最长路径长度。

– 高度（Height）：根节点到最远叶子节点的最长路径上的节点数。

二叉树的特点：

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

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

3. 每个节点都有左右两个子节点，但可以有任意一个为空。

二、二叉树的基本操作

二叉树的基本操作包括创建、遍历、搜索、插入、删除等。

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(preorder, inorder):

if not preorder or not inorder:

return None

root = TreeNode(preorder[0])

root_index = inorder.index(preorder[0])

root.left = create_binary_tree(preorder[1:1+root_index], inorder[:root_index])

root.right = create_binary_tree(preorder[1+root_index:], inorder[root_index+1:])

return root

2. 遍历二叉树

二叉树的遍历方法有三种：前序遍历、中序遍历、后序遍历。

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

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

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

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

python

def preorder_traversal(root):

if root:

print(root.val, end=' ')

preorder_traversal(root.left)

preorder_traversal(root.right)

3. 搜索二叉树

在二叉搜索树（Binary Search Tree，BST）中，左子节点的值小于根节点的值，右子节点的值大于根节点的值。搜索二叉树的基本操作是查找一个特定的值。

是一个在二叉搜索树中查找值的示例代码：

python

def searchBST(root, val):

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

return root

if root.val < val:

return searchBST(root.right, val)

return searchBST(root.left, val)

4. 插入节点到二叉树

在二叉树中插入一个新节点，需要找到合适的插入位置。是在二叉树中插入节点的示例代码：

python

def insert_into_binary_tree(root, val):

if root is None:

return TreeNode(val)

if val < root.val:

root.left = insert_into_binary_tree(root.left, val)

else:

root.right = insert_into_binary_tree(root.right, val)

return root

5. 删除节点从二叉树

删除二叉树中的节点，需要考虑三种情况：节点是叶子节点、节点只有一个子节点、节点有两个子节点。是在二叉树中删除节点的示例代码：

python

def delete_node(root, val):

if root is None:

return None

if val < root.val:

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

elif val > root.val:

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

else:

if root.left is None:

return root.right

elif root.right is None:

return root.left

else:

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):

while node.left:

node = node.left

return node

以上是二叉树的基本操作，掌握这些操作对于计算机专业的面试来说非常重要。