二叉树的基本运算有哪些?
时间: 2024-01-23 17:56:02 浏览: 24
二叉树的基本运算包括:
1. 创建二叉树:可以通过手动输入节点数据的方式或者读取文件数据的方式来创建二叉树。
2. 遍历二叉树:遍历包括前序遍历、中序遍历和后序遍历三种方式,可以递归或者非递归实现。
3. 计算二叉树深度:可以递归或者非递归实现,计算二叉树的深度是指从根节点到最深叶子节点的路径上的节点数。
4. 查找二叉树节点:可以通过递归或者非递归的方式查找二叉树中的节点。
5. 插入节点:可以通过递归或者非递归的方式在二叉树中插入一个节点。
6. 删除节点:可以通过递归或者非递归的方式在二叉树中删除一个节点。
7. 判断二叉树是否为空:判断二叉树是否为空。
8. 清空二叉树:清空二叉树,使其成为空树。
相关问题
二叉树的基本运算程序
二叉树的基本运算程序包括二叉树的创建、遍历、查找、插入、删除等操作。下面是一个简单的二叉树基本运算程序的示例:
```python
# 定义二叉树节点类
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# 创建二叉树
def create_tree(s):
if not s:
return None
stack = []
root = None
is_left = True
for i in s:
if i == '(':
stack.append(node)
is_left = True
elif i == ',':
is_left = False
elif i == ')':
stack.pop()
else:
node = TreeNode(i)
if not root:
root = node
elif is_left:
stack[-1].left = node
else:
stack[-1].right = node
return root
# 前序遍历
def preorder_traversal(root):
if not root:
return
print(root.val, end=' ')
preorder_traversal(root.left)
preorder_traversal(root.right)
# 中序遍历
def inorder_traversal(root):
if not root:
return
inorder_traversal(root.left)
print(root.val, end=' ')
inorder_traversal(root.right)
# 后序遍历
def postorder_traversal(root):
if not root:
return
postorder_traversal(root.left)
postorder_traversal(root.right)
print(root.val, end=' ')
# 查找节点
def find_node(root, val):
if not root:
return None
if root.val == val:
return root
left = find_node(root.left, val)
if left:
return left
right = find_node(root.right, val)
if right:
return right
return None
# 插入节点
def insert_node(root, val):
if not root:
return TreeNode(val)
if not root.left:
root.left = TreeNode(val)
elif not root.right:
root.right = TreeNode(val)
else:
insert_node(root.left, val)
return root
# 删除节点
def delete_node(root, val):
if not root:
return None
if root.val == val:
if not root.left:
return root.right
if not root.right:
return root.left
min_node = root.right
while min_node.left:
min_node = min_node.left
root.val = min_node.val
root.right = delete_node(root.right, min_node.val)
elif root.val > val:
root.left = delete_node(root.left, val)
else:
root.right = delete_node(root.right, val)
return root
# 获取二叉树高度
def get_height(root):
if not root:
return 0
left_height = get_height(root.left)
right_height = get_height(root.right)
return max(left_height, right_height) + 1
# 释放二叉树
def free_tree(root):
if not root:
return
free_tree(root.left)
free_tree(root.right)
del root
# 测试
s = "A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))"
root = create_tree(s)
print("前序遍历:", end='')
preorder_traversal(root)
print()
print("中序遍历:", end='')
inorder_traversal(root)
print()
print("后序遍历:", end='')
postorder_traversal(root)
print()
node = find_node(root, 'H')
if node:
print("H结点的左孩子结点值:", node.left.val)
print("H结点的右孩子结点值:", node.right.val)
print("二叉树的高度:", get_height(root))
root = delete_node(root, 'H')
print("删除H结点后的中序遍历:", end='')
inorder_traversal(root)
print()
free_tree(root)
```
用c语言写二叉树基本运算算法写
下面是用C语言实现二叉树基本运算算法的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结构体
typedef struct Node {
int data; // 数据域
struct Node *left; // 左子节点指针
struct Node *right; // 右子节点指针
} Node;
// 创建节点
Node *createNode(int data) {
Node *node = (Node *) malloc(sizeof(Node));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
// 插入节点
Node *insertNode(Node *root, int data) {
// 如果根节点为空,则新建一个节点作为根节点
if (root == NULL) {
root = createNode(data);
}
// 如果数据小于根节点的数据,则插入到左子树
else if (data < root->data) {
root->left = insertNode(root->left, data);
}
// 如果数据大于等于根节点的数据,则插入到右子树
else {
root->right = insertNode(root->right, data);
}
return root;
}
// 查找节点
Node *findNode(Node *root, int data) {
// 如果根节点为空,则返回NULL
if (root == NULL) {
return NULL;
}
// 如果数据等于根节点的数据,则返回根节点
else if (data == root->data) {
return root;
}
// 如果数据小于根节点的数据,则在左子树中查找
else if (data < root->data) {
return findNode(root->left, data);
}
// 如果数据大于根节点的数据,则在右子树中查找
else {
return findNode(root->right, data);
}
}
// 删除节点
Node *deleteNode(Node *root, int data) {
Node *temp;
if (root == NULL) {
return NULL;
}
else if (data < root->data) {
root->left = deleteNode(root->left, data);
}
else if (data > root->data) {
root->right = deleteNode(root->right, data);
}
else {
if (root->left == NULL) {
temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL) {
temp = root->left;
free(root);
return temp;
}
else {
temp = root->right;
while (temp->left != NULL) {
temp = temp->left;
}
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
}
return root;
}
// 中序遍历
void inorderTraversal(Node *root) {
if (root != NULL) {
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
}
int main() {
Node *root = NULL;
// 插入节点
root = insertNode(root, 5);
root = insertNode(root, 3);
root = insertNode(root, 8);
root = insertNode(root, 2);
root = insertNode(root, 4);
root = insertNode(root, 7);
root = insertNode(root, 9);
// 中序遍历
printf("Inorder traversal: ");
inorderTraversal(root);
printf("\n");
// 查找节点
Node *node = findNode(root, 4);
if (node != NULL) {
printf("Node found: %d\n", node->data);
}
else {
printf("Node not found\n");
}
// 删除节点
root = deleteNode(root, 5);
// 中序遍历
printf("Inorder traversal: ");
inorderTraversal(root);
printf("\n");
return 0;
}
```
以上代码实现了二叉树的基本操作,包括创建节点、插入节点、查找节点、删除节点和中序遍历等。你可以根据自己的需求进行修改和扩展。