Share binary tree c++

[silverbear794]

## Cây nhị phân trong C ++

Một cây nhị phân là một cấu trúc dữ liệu bao gồm các nút được sắp xếp theo kiểu phân cấp.Mỗi nút có một giá trị và hai nút con: một đứa trẻ trái và một đứa trẻ phải.Đứa trẻ bên trái của một nút luôn nhỏ hơn giá trị của nút và đứa trẻ bên phải luôn lớn hơn giá trị của nút.

Cây nhị phân thường được sử dụng để đại diện cho dữ liệu phân cấp tự nhiên, chẳng hạn như hệ thống tệp trên máy tính.Trong một hệ thống tệp, nút gốc đại diện cho toàn bộ hệ thống tệp và các nút con đại diện cho các tệp và thư mục riêng lẻ.

Cây nhị phân có thể được sử dụng để thực hiện nhiều hoạt động trên dữ liệu, chẳng hạn như tìm kiếm, chèn và xóa.Tìm kiếm một cây nhị phân cho một giá trị cụ thể là một hoạt động rất hiệu quả, vì nó có thể được thực hiện trong thời gian O (log n), trong đó n là số lượng nút trong cây.

Cây nhị phân có thể được thực hiện trong C ++ bằng cách sử dụng nhiều cấu trúc dữ liệu khác nhau.Việc triển khai phổ biến nhất là sử dụng một danh sách được liên kết, trong đó mỗi nút trong danh sách chứa một con trỏ ở các nút con bên trái và bên phải của nó.

Mã sau đây hiển thị một ví dụ về cách thực hiện cây nhị phân trong C ++ bằng danh sách được liên kết:

`` `C ++
#include <Istream>

sử dụng không gian tên STD;

// một nút trong một cây nhị phân.
Nút cấu trúc {
giá trị int;
Nút* trái;
Nút* phải;
};

// một chức năng để tạo một nút mới.
Nút* createnode (int value) {
Nút* newNode = new node ();
newnode-> value = value;
newnode-> trái = null;
newnode-> right = null;
trả về newnode;
}

// một chức năng để chèn một nút mới vào cây nhị phân.
void insertNode (nút* root, int value) {
// Tạo một nút mới cho giá trị.
Nút* newnode = createnode (value);

// Nếu cây trống, hãy làm nút mới thành nút gốc.
if (root == null) {
root = newNode;
} khác {
// Tìm vị trí chính xác cho nút mới trong cây.
Nút* currentNode = root;
while (true) {
// Nếu giá trị nhỏ hơn giá trị của nút hiện tại,
// Chèn nút mới vào cây con bên trái.
if (value <currentNode-> value) {
if (currentNode-> left == null) {
currentNode-> left = newNode;
phá vỡ;
} khác {
currentNode = currentNode-> trái;
}
} khác {
// Nếu giá trị lớn hơn giá trị của nút hiện tại,
// Chèn nút mới vào cây con bên phải.
if (currentNode-> right == null) {
currentNode-> right = newNode;
phá vỡ;
} khác {
currentNode = currentNode-> right;
}
}
}
}
}

// một chức năng để in một cây nhị phân trong việc đặt hàng trước.
void printPreArder (Node* root) {
// Nếu cây trống, không có gì để in.
if (root == null) {
trở lại;
}

// In giá trị của nút gốc.
cout << root-> value << "";

// In Subtree bên trái trong Traversal trước.
printpreorder (root-> trái);

// In Subtree bên phải trong Traversal trước.
printpreorder (root-> phải);
}

int main () {
// Tạo một cây nhị phân mới.
Nút* root = null;

// Chèn một số nút vào cây.
ChènNode (gốc, 10);
ChènNode (root, 5);
ChènNode (gốc, 15);
ChènNode (gốc, 2);
ChènNode (gốc, 7);
ChènNode (gốc, 12);
ChènNode
=======================================
## Binary Tree in C++

A binary tree is a data structure that consists of nodes arranged in a hierarchical fashion. Each node has a value, and two child nodes: a left child and a right child. The left child of a node is always less than the value of the node, and the right child is always greater than the value of the node.

Binary trees are often used to represent data that is naturally hierarchical, such as the file system on a computer. In a file system, the root node represents the entire file system, and the child nodes represent the individual files and folders.

Binary trees can be used to perform a variety of operations on data, such as searching, insertion, and deletion. Searching a binary tree for a particular value is a very efficient operation, as it can be done in O(log n) time, where n is the number of nodes in the tree.

Binary trees can be implemented in C++ using a variety of different data structures. The most common implementation is to use a linked list, where each node in the list contains a pointer to its left and right child nodes.

The following code shows an example of how to implement a binary tree in C++ using a linked list:

```c++
#include <iostream>

using namespace std;

// A node in a binary tree.
struct Node {
int value;
Node* left;
Node* right;
};

// A function to create a new node.
Node* createNode(int value) {
Node* newNode = new Node();
newNode->value = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}

// A function to insert a new node into a binary tree.
void insertNode(Node* root, int value) {
// Create a new node for the value.
Node* newNode = createNode(value);

// If the tree is empty, make the new node the root node.
if (root == NULL) {
root = newNode;
} else {
// Find the correct location for the new node in the tree.
Node* currentNode = root;
while (true) {
// If the value is less than the current node's value,
// insert the new node into the left subtree.
if (value < currentNode->value) {
if (currentNode->left == NULL) {
currentNode->left = newNode;
break;
} else {
currentNode = currentNode->left;
}
} else {
// If the value is greater than the current node's value,
// insert the new node into the right subtree.
if (currentNode->right == NULL) {
currentNode->right = newNode;
break;
} else {
currentNode = currentNode->right;
}
}
}
}
}

// A function to print a binary tree in preorder traversal.
void printPreorder(Node* root) {
// If the tree is empty, there is nothing to print.
if (root == NULL) {
return;
}

// Print the value of the root node.
cout << root->value << " ";

// Print the left subtree in preorder traversal.
printPreorder(root->left);

// Print the right subtree in preorder traversal.
printPreorder(root->right);
}

int main() {
// Create a new binary tree.
Node* root = NULL;

// Insert some nodes into the tree.
insertNode(root, 10);
insertNode(root, 5);
insertNode(root, 15);
insertNode(root, 2);
insertNode(root, 7);
insertNode(root, 12);
insertNode