跳到主要内容

二叉树

提示
  1. 二叉树定义：二叉树是一种树形数据结构，其中每个节点最多有两个子节点，通常被称为左子节点和右子节点。
  2. 二叉树类型：二叉树有多种类型，包括完全二叉树、完美二叉树、完全二叉树、退化树、偏斜二叉树和平衡二叉树，每种类型具有独特的特征和应用。
  3. 二叉树应用：二叉树广泛应用于数据快速访问、路由算法、堆数据结构和构建语法树等领域。

二叉树是一种树形数据结构，其中每个父节点最多有两个子节点。一个二叉树的节点由三部分组成：

  • 数据项

  • 左子节点的地址

  • 右子节点的地址

二叉树

二叉树的类型​

1. 完全二叉树​

完全二叉树是二叉树的一种特殊形式，其中每个父节点/内部节点要么有两个子节点，要么没有子节点。

完全二叉树

要了解更多，请访问完全二叉树。

2. 完美二叉树​

完美二叉树是一种二叉树，其中每个内部节点都恰好有两个子节点，并且所有叶节点都在同一层级。

完美二叉树

要了解更多，请访问完美二叉树。

3. 完全二叉树​

完全二叉树就像完全二叉树一样，但有两个主要区别：

  1. 每个层级必须被完全填满
  2. 所有叶元素必须倾向于左侧
  3. 最后一个叶元素可能没有右侧兄弟节点，即完全二叉树不必是完全二叉树

完全二叉树

要了解更多，请访问完全二叉树。

4. 退化树或病态树​

退化树或病态树是只有一个左或右子节点的树。

退化二叉树

5. 偏斜二叉树​

偏斜二叉树是一种病态/退化树，其中树要么由左节点要么由右节点主导。因此，有两种类型的偏斜二叉树：左偏斜二叉树和右偏斜二叉树。

偏斜二叉树

6. 平衡二叉树​

平衡二叉树是一种二叉树，在这种树中，每个节点的左右子树的高度差要么是 0 要么是 1。

平衡二叉树

要了解更多，请访问平衡二叉树。

二叉树的表示​

二叉树的一个节点由一个结构体表示，包含一个数据部分和两个指向同类型其他结构体的指针。

struct node
{
 int data;
 struct node *left;
 struct node *right;
};

二叉树表示

Python、Java 和 C/C++ 示例​

Python Java C C++

# Python 中的二叉树

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

    # 先序遍历
    def traversePreOrder(self):
        print(self.val, end=' ')
        if self.left:
            self.left.traversePreOrder()
        if self.right:
            self.right.traversePreOrder()

    # 中序遍历
    def traverseInOrder(self):
        if self.left:
            self.left.traverseInOrder()
        print(self.val, end=' ')
        if

 self.right:
            self.right.traverseInOrder()

    # 后序遍历
    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("先序遍历: ", end="")
root.traversePreOrder()
print("\n中序遍历: ", end="")
root.traverseInOrder()
print("\n后序遍历: ", end="")
root.traversePostOrder()
// Java 中的二叉树

// 节点创建
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;
  }

  // 中序遍历
  public void traverseInOrder(Node node) {
    if (node != null) {
      traverseInOrder(node.left);
      System.out.print(" " + node.key);
      traverseInOrder(node.right);
    }
  }

  // 后序遍历
  public void traversePostOrder(Node node) {
    if (node != null) {
      traversePostOrder(node.left);
      traversePostOrder(node.right);
      System.out.print(" " + node.key);
    }
  }

  // 先序遍历
  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("先序遍历：");
    tree.traversePreOrder(tree.root);
    System.out.print("\n中序遍历：");
    tree.traverseInOrder(tree.root);
    System.out.print("\n后序遍历：");
    tree.traversePostOrder(tree.root);
  }
}
// C 中的树遍历

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

struct node {
  int item;
  struct node* left;
  struct node* right;
};

// 中序遍历
void inorderTraversal(struct node* root) {
  if (root == NULL) return;
  inorderTraversal(root->left);
  printf("%d ->", root->item);
  inorderTraversal(root->right);
}

// 先序遍历
void preorderTraversal(struct node* root) {
  if (root == NULL) return;
  printf("%d ->", root->item);
  preorderTraversal(root->left);
  preorderTraversal(root->right);
}

// 后序遍历
void postorderTraversal(struct node* root) {
  if (root == NULL) return;
  postorderTraversal(root->left);
  postorderTraversal(root->right);
  printf("%d ->", root->item);
}

// 创建新节点
struct node* createNode(value) {
  struct node* newNode = malloc(sizeof(struct node));
  newNode->item = value;
  newNode->left = NULL;
  newNode->right = NULL;

  return newNode;
}

// 在节点左侧插入
struct node* insertLeft(struct node* root, int value) {
  root->left = createNode(value);
  return root->left;
}

// 在节点右侧插入
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("中序遍历 \n");
  inorderTraversal(root);

  printf("\n先序遍历 \n");
  preorderTraversal(root);

  printf("\n后序遍历 \n");
  postorderTraversal(root);
}

C++中的二叉树应用​

  • 用于数据的快速和容易访问
  • 在路由器算法中应用
  • 用于实现堆数据结构
  • 语法树
// C++中的二叉树

#include <stdlib.h>

#include <iostream>

using namespace std;

struct node {
  int data;
  struct node *left;
  struct node *right;
};

// 创建新节点
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);
}

// 前序遍历
void traversePreOrder(struct node *temp) {
  if (temp != NULL) {
    cout << " " << temp->data;
    traversePreOrder(temp->left);
    traversePreOrder(temp->right);
  }
}

// 中序遍历
void traverseInOrder(struct node *temp) {
  if (temp != NULL) {
    traverseInOrder(temp->left);
    cout << " " << temp->data;
    traverseInOrder(temp->right);
  }
}

// 后序遍历
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);
}

二叉树的应用​

  • 用于快速方便地访问数据
  • 在路由算法中使用
  • 用于实现堆数据结构
  • 语法树
最后于 更新