# 二叉樹 > 原文： [https://www.programiz.com/dsa/binary-tree](https://www.programiz.com/dsa/binary-tree) #### 在本教程中，您將學習二叉樹及其不同類型。 另外，您還將找到 C，C++ ，Java 和 Python 中二叉樹的工作示例。 二叉樹是一種樹數據結構，其中每個父節點最多可以有兩個子節點。 例如：在下圖中，每個元素最多有兩個子代。  二叉樹 * * * ## 二叉樹的類型 ### 滿二叉樹 滿二叉樹是二叉樹的一種特殊類型，其中每個父節點/內部節點都有兩個或沒有子節點。  滿二叉樹 要了解更多信息，請訪問[滿二叉樹](http://programiz.com/dsa/full-binary-tree)。 ### 完美二叉樹 完美二叉樹是一種二叉樹，其中每個內部節點恰好有兩個子節點，而所有葉節點都處于同一級別。  完美二叉樹 要了解更多信息，請訪問[完美二叉樹](http://programiz.com/dsa/perfect-binary-tree)。 ### 完全二叉樹 完全二叉樹就像滿二叉樹，但有兩個主要區別 1. 每個級別都必須完全填滿 2. 所有葉子元素都必須向左傾斜。 3. 最后一個葉子元素可能沒有正確的同級，即滿完全二叉樹不必是滿二叉樹。  完全二叉樹 要了解更多信息，請訪問[完全二叉樹](http://programiz.com/dsa/complete-binary-tree)。 ### 退化樹或病態樹 退化或病態的樹是具有左右一個獨生子的樹。  退化樹 ### 偏二叉樹 偏二叉樹是一種病態/退化的樹，其中該樹由左節點或右節點支配。 因此，存在兩種類型的斜二叉樹：**左斜二叉樹**和**右斜二叉樹**。  偏二叉樹 ### 平衡二叉樹 它是一種二叉樹，其中每個節點的左和右子樹之間的差為 0 或 1。  平衡二叉樹 要了解更多信息，請訪問[平衡二叉樹](http://programiz.com/dsa/balanced-binary-tree)。 * * * ## 二叉樹表示 二叉樹的節點由包含數據部分和兩個指向相同類型其他結構的指針的結構表示。 ``` struct node { int data; struct node *left; struct node *right; }; ```  二叉樹表示 * * * ## Python，Java 和 C/C++ 示例 ```py # Binary Tree in Python class Node: def __init__(self, key): self.left = None self.right = None self.val = key # Traverse preorder def traversePreOrder(self): print(self.val, end=' ') if self.left: self.left.traversePreOrder() if self.right: self.right.traversePreOrder() # Traverse inorder def traverseInOrder(self): if self.left: self.left.traverseInOrder() print(self.val, end=' ') if self.right: self.right.traverseInOrder() # Traverse postorder def traversePostOrder(self): if self.left: self.left.traversePostOrder() if self.right: self.right.traversePostOrder() print(self.val, end=' ') root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) print("Pre order Traversal: ", end="") root.traversePreOrder() print("\nIn order Traversal: ", end="") root.traverseInOrder() print("\nPost order Traversal: ", end="") root.traversePostOrder() ``` ```java // Binary Tree in Java // Node creation class Node { int key; Node left, right; public Node(int item) { key = item; left = right = null; } } class BinaryTree { Node root; BinaryTree(int key) { root = new Node(key); } BinaryTree() { root = null; } // Traverse Inorder public void traverseInOrder(Node node) { if (node != null) { traverseInOrder(node.left); System.out.print(" " + node.key); traverseInOrder(node.right); } } // Traverse Postorder public void traversePostOrder(Node node) { if (node != null) { traversePostOrder(node.left); traversePostOrder(node.right); System.out.print(" " + node.key); } } // Traverse Preorder public void traversePreOrder(Node node) { if (node != null) { System.out.print(" " + node.key); traversePreOrder(node.left); traversePreOrder(node.right); } } public static void main(String[] args) { BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(3); tree.root.left.left = new Node(4); System.out.print("Pre order Traversal: "); tree.traversePreOrder(tree.root); System.out.print("\nIn order Traversal: "); tree.traverseInOrder(tree.root); System.out.print("\nPost order Traversal: "); tree.traversePostOrder(tree.root); } } ``` ```c // Tree traversal in C #include <stdio.h> #include <stdlib.h> struct node { int item; struct node* left; struct node* right; }; // Inorder traversal void inorderTraversal(struct node* root) { if (root == NULL) return; inorderTraversal(root->left); printf("%d ->", root->item); inorderTraversal(root->right); } // Preorder traversal void preorderTraversal(struct node* root) { if (root == NULL) return; printf("%d ->", root->item); preorderTraversal(root->left); preorderTraversal(root->right); } // Postorder traversal void postorderTraversal(struct node* root) { if (root == NULL) return; postorderTraversal(root->left); postorderTraversal(root->right); printf("%d ->", root->item); } // Create a new Node struct node* createNode(value) { struct node* newNode = malloc(sizeof(struct node)); newNode->item = value; newNode->left = NULL; newNode->right = NULL; return newNode; } // Insert on the left of the node struct node* insertLeft(struct node* root, int value) { root->left = createNode(value); return root->left; } // Insert on the right of the node struct node* insertRight(struct node* root, int value) { root->right = createNode(value); return root->right; } int main() { struct node* root = createNode(1); insertLeft(root, 2); insertRight(root, 3); insertLeft(root->left, 4); printf("Inorder traversal \n"); inorderTraversal(root); printf("\nPreorder traversal \n"); preorderTraversal(root); printf("\nPostorder traversal \n"); postorderTraversal(root); } ``` ```cpp // Binary Tree in C++ #include <stdlib.h> #include <iostream> using namespace std; struct node { int data; struct node *left; struct node *right; }; // New node creation struct node *newNode(int data) { struct node *node = (struct node *)malloc(sizeof(struct node)); node->data = data; node->left = NULL; node->right = NULL; return (node); } // Traverse Preorder void traversePreOrder(struct node *temp) { if (temp != NULL) { cout << " " << temp->data; traversePreOrder(temp->left); traversePreOrder(temp->right); } } // Traverse Inorder void traverseInOrder(struct node *temp) { if (temp != NULL) { traverseInOrder(temp->left); cout << " " << temp->data; traverseInOrder(temp->right); } } // Traverse Postorder void traversePostOrder(struct node *temp) { if (temp != NULL) { traversePostOrder(temp->left); traversePostOrder(temp->right); cout << " " << temp->data; } } int main() { struct node *root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); cout << "preorder traversal: "; traversePreOrder(root); cout << "\nInorder traversal: "; traverseInOrder(root); cout << "\nPostorder traversal: "; traversePostOrder(root); } ``` * * * ## 二叉樹應用 * 輕松快速地訪問數據 * 在路由器算法中 * 實現[堆數據結構](https://www.programiz.com/dsa/heap-data-structure) * 語法樹