Chạy ❯
Nhận trang web của
riêng
bạn
×
Thay đổi định hướng
Thay đổi chủ đề, Tối/Sáng
Đi tới Không gian
Python
C
Java
lớp TreeNode: def __init__(self, data): self.data = dữ liệu self.left = Không có self.right = Không có self.height = 1 def getHeight(node): nếu không phải nút: return 0 return node.height def getBalance( nút): nếu không phải nút: return 0 return getHeight(node.left) - getHeight(node.right) def rightRotate(y): print('Xoay sang phải trên nút',y.data) x = y.left T2 = x .right x.right = y y.left = T2 y.height = 1 + max(getHeight(y.left), getHeight(y.right)) x.height = 1 + max(getHeight(x.left), getHeight (x.right)) return x def leftRotate(x): print('Xoay trái trên nút',x.data) y = x.right T2 = y.left y.left = x x.right = T2 x.height = 1 + max(getHeight(x.left), getHeight(x.right)) y.height = 1 + max(getHeight(y.left), getHeight(y.right)) trả về y def chèn(nút, dữ liệu) : nếu không phải nút: trả về TreeNode(data) if data < node.data: node.left = Insert(node.left, data) elif data > node.data: node.right = Insert(node.right, data) node. chiều cao = 1 + max(getHeight(node.left), getHeight(node.right)) Balance = getBalance(node) # Left Left nếu Balance > 1 và data < node.left.data: return rightRotate(node) # Right Right nếu cân bằng < -1 và dữ liệu > node.right.data: return leftRotate(node) # Left Right nếu cân bằng > 1 và data > node.left.data: node.left = leftRotate(node.left) return rightRotate(node) # Phải Trái nếu số dư < -1 và dữ liệu < node.right.data: node.right = rightRotate(node.right) return leftRotate(node) return node def inOrderTraversal(node): nếu nút là None: return inOrderTraversal(node. left) print(node.data, end=", ") inOrderTraversal(node.right) # Chèn nút root = Không có chữ cái nào = ['C', 'B', 'E', 'A', 'D', ' H', 'G', 'F'] cho chữ cái trong các chữ cái: root = Insert(root, letter) inOrderTraversal(root) #Python
#include <stdio.h> #include <stdlib.h> typedef struct TreeNode { dữ liệu char; struct TreeNode *trái, *phải; chiều cao int; } Nút cây; int max(int a, int b) { return (a > b) ? một: b; } int chiều cao(TreeNode *N) { if (N == NULL) trả về 0; trả về N->chiều cao; } TreeNode* newNode(char data) { TreeNode* node = (TreeNode*) malloc(sizeof(TreeNode)); nút->dữ liệu = dữ liệu; nút->trái = NULL; nút->phải = NULL; nút-> chiều cao = 1; trả về (nút); } TreeNode *rightRotate(TreeNode *y) { printf("Xoay sang phải trên nút %c\n", y->data); TreeNode *x = y->left; TreeNode *T2 = x->phải; x->phải = y; y->trái = T2; y->height = max(height(y->left), Height(y->right)) + 1; x->height = max(height(x->left), Height(x->right)) + 1; trả lại x; } TreeNode *leftRotate(TreeNode *x) { printf("Xoay trái trên nút %c\n", x->data); TreeNode *y = x->right; TreeNode *T2 = y->left; y->trái = x; x->phải = T2; x->height = max(height(x->left), Height(x->right)) + 1; y->height = max(height(y->left), Height(y->right)) + 1; trả lại y; } int getBalance(TreeNode *N) { if (N == NULL) return 0; chiều cao trả về(N->trái) - chiều cao(N->phải); } TreeNode* Insert(TreeNode* node, char data) { if (node == NULL) return(newNode(data)); if (dữ liệu < nút-> dữ liệu) nút-> left = chèn (nút-> trái, dữ liệu); ngược lại nếu (dữ liệu > nút-> dữ liệu) nút-> bên phải = chèn (nút-> bên phải, dữ liệu); nút trả về khác; nút->chiều cao = 1 + max(chiều cao(nút->trái), chiều cao(nút->phải)); int Balance = getBalance(nút); if (cân bằng > 1 && dữ liệu < nút-> trái-> dữ liệu) trả về rightRotate(node); if (cân bằng < -1 && dữ liệu > nút->phải->dữ liệu) trả về leftRotate(node); if (cân bằng > 1 && dữ liệu > nút->trái->dữ liệu) { nút->left = leftRotate(nút->trái); return rightRotate(nút); } if (cân bằng < -1 && dữ liệu < node->right->data) { node->right = rightRotate(node->right); return leftRotate(node); } nút trả về; } void inOrderTraversal(TreeNode *root) { if (root != NULL) { inOrderTraversal(root->left); printf("%c", root->data); inOrderTraversal(root->right); } } int main() { TreeNode *root = NULL; chữ char[] = {'C', 'B', 'E', 'A', 'D', 'H', 'G', 'F'}; int n = sizeof(chữ cái) / sizeof(chữ cái[0]); for (int i = 0; i < n; i++) { root = Insert(root, Letters[i]); } inOrderTraversal(root); trả về 0; } //C
lớp công khai Chính { lớp tĩnh AVLtree { lớp TreeNode { dữ liệu char; TreeNode trái, phải; chiều cao int; TreeNode(char d) { data = d; chiều cao = 1; } } Gốc TreeNode; int chiều cao(TreeNode N) { if (N == null) trả về 0; trả về N.height; } int getBalance(TreeNode N) { if (N == null) return 0; chiều cao trả về(N.left) - chiều cao(N.right); } TreeNode rightRotate(TreeNode y) { System.out.println("Xoay sang phải trên nút " + y.data); TreeNode x = y.left; TreeNode T2 = x.right; x.right = y; y.left = T2; y.height = Math.max(height(y.left), Height(y.right)) + 1; x.height = Math.max(height(x.left), Height(x.right)) + 1; trả lại x; } TreeNode leftRotate(TreeNode x) { System.out.println("Xoay trái trên nút " + x.data); TreeNode y = x.right; TreeNode T2 = y.left; y.left = x; x.right = T2; x.height = Math.max(height(x.left), Height(x.right)) + 1; y.height = Math.max(height(y.left), Height(y.right)) + 1; trả lại y; } Chèn TreeNode (nút TreeNode, dữ liệu char) { if (nút == null) trả về TreeNode mới (dữ liệu); if (dữ liệu < node.data) node.left = Insert(node.left, data); ngược lại nếu (dữ liệu > node.data) node.right = Insert(node.right, data); nút trả về khác; node.height = 1 + Math.max(height(node.left), Height(node.right)); int Balance = getBalance(nút); if (cân bằng > 1 && dữ liệu < node.left.data) return rightRotate(node); if (cân bằng < -1 && dữ liệu > node.right.data) return leftRotate(node); if (cân bằng > 1 && dữ liệu > node.left.data) { node.left = leftRotate(node.left); return rightRotate(nút); } if (cân bằng < -1 && dữ liệu < node.right.data) { node.right = rightRotate(node.right); return leftRotate(node); } nút trả về; } void inOrderTraversal(nút TreeNode) { if (node != null) { inOrderTraversal(node.left); System.out.print(node.data + ", "); inOrderTraversal(node.right); } } } public static void main(String[] args) { AVLtree tree = new AVLtree(); char[] chữ cái = {'C', 'B', 'E', 'A', 'D', 'H', 'G', 'F'}; for (chữ char : chữ cái) { tree.root = tree.insert(tree.root, letter); } tree.inOrderTraversal(tree.root); } } //Java
Kết quả Python:
Kết quả C:
Kết quả Java:
Xoay phải trên nút H
A, B, C, D, E, F, G, H,
Xoay phải trên nút H
ABCDEFGH
Xoay phải trên nút H
A, B, C, D, E, F, G, H,