W3Schools 線上編輯器 - W3Schools 教學

Python

Java

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        self.height = 1

def getHeight(node):
    if not node:
        return 0
    return node.height

def getBalance(node):
    if not node:
        return 0
    return getHeight(node.left) - getHeight(node.right)

def rightRotate(y):
    print('Rotate right on node',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('Rotate left on node',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))
    return y

def insert(node, data):
    if not node:
        return TreeNode(data)

if data < node.data:
        node.left = insert(node.left, data)
    elif data > node.data:
        node.right = insert(node.right, data)

# Update the balance factor and balance the tree
    node.height = 1 + max(getHeight(node.left), getHeight(node.right))
    balance = getBalance(node)

# Balancing the tree
    # Left Left
    if balance > 1 and getBalance(node.left) >= 0:
        return rightRotate(node)

# Left Right
    if balance > 1 and getBalance(node.left) < 0:
        node.left = leftRotate(node.left)
        return rightRotate(node)

# Right Right
    if balance < -1 and getBalance(node.right) <= 0:
        return leftRotate(node)

# Right Left
    if balance < -1 and getBalance(node.right) > 0:
        node.right = rightRotate(node.right)
        return leftRotate(node)

return node

def inOrderTraversal(node):
    if node is None:
        return
    inOrderTraversal(node.left)
    print(node.data, end=", ")
    inOrderTraversal(node.right)

# Inserting nodes
root = None
letters = ['C', 'B', 'E', 'A', 'D', 'H', 'G', 'F']
for letter in letters:
    root = insert(root, letter)

inOrderTraversal(root)

#Python

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    char data;
    struct TreeNode *left, *right;
    int height;
} TreeNode;

int max(int a, int b) {
    return (a > b) ? a : b;
}

int getHeight(TreeNode* node) {
    if (!node) return 0;
    return node->height;
}

TreeNode* createNode(char data) {
    TreeNode* node = (TreeNode*) malloc(sizeof(TreeNode));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    node->height = 1;
    return(node);
}

TreeNode *rightRotate(TreeNode *y) {
    printf("Rotate right on node %c\n", y->data);
    TreeNode *x = y->left;
    TreeNode *T2 = x->right;

x->right = y;
    y->left = T2;

y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
    x->height = max(getHeight(x->left), getHeight(x->right)) + 1;

return x;
}

TreeNode *leftRotate(TreeNode *x) {
    printf("Rotate left on node %c\n", x->data);
    TreeNode *y = x->right;
    TreeNode *T2 = y->left;

y->left = x;
    x->right = T2;

x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
    y->height = max(getHeight(y->left), getHeight(y->right)) + 1;

return y;
}

int getBalance(TreeNode *N) {
    if (N == NULL) return 0;
    return getHeight(N->left) - getHeight(N->right);
}

TreeNode* insert(TreeNode* root, char data) {
    if (!root) return createNode(data);

if (data < root->data)
        root->left = insert(root->left, data);
    else if (data > root->data)
        root->right = insert(root->right, data);

root->height = 1 + (getHeight(root->left) > getHeight(root->right) ? getHeight(root->left) : getHeight(root->right));
    int balance = getBalance(root);

if (balance > 1 && getBalance(root->left) >= 0)
        return rightRotate(root);

if (balance > 1 && getBalance(root->left) < 0) {
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }

if (balance < -1 && getBalance(root->right) <= 0)
        return leftRotate(root);

if (balance < -1 && getBalance(root->right) > 0) {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }

return root;
}

void inOrderTraversal(TreeNode *root) {
    if (root != NULL) {
        inOrderTraversal(root->left);
        printf("%c ", root->data);
        inOrderTraversal(root->right);
    }
}

int main() {
    TreeNode *root = NULL;
    char letters[] = {'C', 'B', 'E', 'A', 'D', 'H', 'G', 'F'};
    int n = sizeof(letters) / sizeof(letters[0]);
    for (int i = 0; i < n; i++) {
        root = insert(root, letters[i]);
    }

inOrderTraversal(root);
    return 0;
}

//C

public class Main {
    static class AVLTree {
        class TreeNode {
            char data;
            TreeNode left, right;
            int height;

TreeNode(char d) {
                data = d;
                height = 1;
            }
        }

TreeNode root;

int height(TreeNode N) {
            if (N == null) return 0;
            return N.height;
        }

int getBalance(TreeNode N) {
            if (N == null) return 0;
            return height(N.left) - height(N.right);
        }

TreeNode rightRotate(TreeNode y) {
            System.out.println("Rotate right on node " + 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;

return x;
        }

TreeNode leftRotate(TreeNode x) {
            System.out.println("Rotate left on node " + 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;

return y;
        }

TreeNode insert(TreeNode root, char data) {
            if (root == null) return new TreeNode(data);

if (data < root.data) {
                root.left = insert(root.left, data);
            } else if (data > root.data) {
                root.right = insert(root.right, data);
            } else {
                return root; // Duplicate data is not allowed
            }

root.height = 1 + Math.max(height(root.left), height(root.right));

int balance = getBalance(root);

// Left Left Case
            if (balance > 1 && getBalance(root.left) >= 0) {
                return rightRotate(root);
            }

// Left Right Case
            if (balance > 1 && getBalance(root.left) < 0) {
                root.left = leftRotate(root.left);
                return rightRotate(root);
            }

// Right Right Case
            if (balance < -1 && getBalance(root.right) <= 0) {
                return leftRotate(root);
            }

// Right Left Case
            if (balance < -1 && getBalance(root.right) > 0) {
                root.right = rightRotate(root.right);
                return leftRotate(root);
            }

return root;
        }

void inOrderTraversal(TreeNode node) {
            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[] letters = {'C', 'B', 'E', 'A', 'D', 'H', 'G', 'F'};
        for (char letter : letters) {
            tree.root = tree.insert(tree.root, letter);
        }
        tree.inOrderTraversal(tree.root);
    }
}

//Java