数据结构(树):二叉树


概述

  二叉树是n个有限元素的集合,该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成,是有序树。当集合为空时,称该二叉树为空二叉树。在二叉树中,一个元素也称作一个结点 。二叉树(binary tree)是指树中节点的度不大于2的有序树,它是一种最简单且最重要的树。

二叉树性质

  • 二叉树的第i层上至多有2i-1(i≥1)个节点。
  • 深度为h的二叉树中至多含有2h-1个节点。
  • 若在任意一棵二叉树中,有n0个叶子节点,有n2个度为2的节点,则必有n0=n2+1。

二叉树特殊类型

  • 满二叉树

  如果一棵二叉树只有度为0的结点(叶子节点)和度为2的结点,并且度为0的结点在同一层上,则这棵二叉树为满二叉树。满二叉树又是特殊的完全二叉树。

  满二叉树除了具备普通二叉树的性质,还具备以下性质:

  1. 满二叉树中第 i 层的节点数为 2i-1 个。
  2. 深度为 h 的满二叉树必有 2h-1 个节点 ,叶子数为 2h-1
  3. 满二叉树中不存在度为 1 的节点,每一个分支点中都两棵深度相同的子树,且叶子节点都在最底层。
  4. 具有 n 个节点的满二叉树的深度为 log2(n+1)(与第2点对应)。
  • 完全二叉树

  深度为h,有n个结点的二叉树当且仅当其每一个结点都与深度为h的满二叉树中编号从1到n的结点一一对应时;简单来说就是二叉树中除去最后一层节点为满二叉树,且最后一层的结点依次从左到右分布,则此二叉树被称为完全二叉树。

  二叉树除了满足普通二叉树的性质,还具备以下性质:

  1. 具有n个节点的完全二叉树的深度为(int)log2n+1。
  2. 若对一棵有n个节点的完全二叉树进行顺序编号(1≤i≤n),那么,对于编号为i(i≥1)的节点:

    当i=1时,该节点为根,它无双亲节点;

    当i>1时,该节点的双亲节点的编号为i/2;

    若2i≤n,则有编号为2i的左节点,否则没有左节点;

    若2i+1≤n,则有编号为2i+1的右节点,否则没有右节点。

二叉树存储

  • 顺序存储

  顺序存储适用于完全二叉树,因为完全二叉树从根节点往下排,可以看成是连续的节点。

  

  • 链式存储

  

二叉树遍历

  • 前序遍历:根节点-->左子节点-->右子节点

 1     public void preorderTraversal(BinaryTreeNode root){
 2         if (root == null){
 3             return;
 4         }
 5         print(root);
 6         if (root.getLeft() != null){
 7             preorderTraversal(root.getLeft());
 8         }
 9         if (root.getRight() != null){
10             preorderTraversal(root.getRight());
11         }
12     }
  • 中序遍历

 1     public void inOrderTraversal(BinaryTreeNode root){
 2         if (root == null){
 3             return;
 4         }
 5         if (root.getLeft() != null){
 6             inOrderTraversal(root.getLeft());
 7         }
 8         print(root);
 9         if (root.getRight() != null){
10             inOrderTraversal(root.getRight());
11         }
12     }
  • 后序遍历

 1     public void postOrderTraversal(BinaryTreeNode root){
 2         if (root == null){
 3             return;
 4         }
 5         if (root.getLeft() != null){
 6             postOrderTraversal(root.getLeft());
 7         }
 8         if (root.getRight() != null){
 9             postOrderTraversal(root.getRight());
10         }
11         print(root);
12     }
  • 层次遍历

 1     public void levelTraversal(BinaryTreeNode root){
 2         if (root == null){
 3             return;
 4         }
 5         LinkedList<BinaryTreeNode> queue = new LinkedList<BinaryTreeNode>();
 6         queue.offer(root);
 7         while (!queue.isEmpty()){
 8             BinaryTreeNode node = queue.poll();
 9             print(node);
10             if (node.getLeft() != null){
11                 queue.offer(node.getLeft());
12             }
13             if (node.getRight() != null){
14                 queue.offer(node.getRight());
15             }
16         }
17 
18     }

 

本站声明:网站内容来源于网络,如有侵权,请联系我们,我们将及时处理。

  • 分享:
评论
还没有评论
    发表评论 说点什么