二叉树 数据类型android_有一节点数据为字符的二叉树,请定义表示该二叉树的数据结构 - CSDN
  • 二叉树除最后一层无任何子节点外,每一层上的所有结点都有两个子结点二叉树。 完全二叉树一棵二叉树至多只有最下面的一层上的结点的度数可以小于2,并且最下层上的结点都集中在该层最左边的若干位置上,则此...

    满二叉树

    除最后一层无任何子节点外,每一层上的所有结点都有两个子结点二叉树。
    这里写图片描述

    完全二叉树

    一棵二叉树至多只有最下面的一层上的结点的度数可以小于2,并且最下层上的结点都集中在该层最左边的若干位置上,则此二叉树成为完全二叉树。
    这里写图片描述

    平衡二叉树

    它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树
    这里写图片描述

    二叉搜索树

    它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树
    这里写图片描述

    红黑树

    平衡二叉搜索树
    这里写图片描述

    哈弗曼树

    给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。
    这里写图片描述

    展开全文
  • 数据结构:图文详解二叉树(遍历、类型、操作)

    前言

    • 二叉树是一种特殊的树结构,应用广泛
    • 下面,我将详细介绍 二叉树的相关知识,希望你们会喜欢。

    目录

    示意图


    1. 简介

    示意图


    2. 性质

    示意图


    3. 存储结构

    二叉树的存储结构包括:顺序存储结构 & 链式存储结构

    示意图

    注:上述的链式存储方式,即为树结构中的孩子兄弟表示法。具体如下:

    示意图

    大多数情况下,二叉树的建立会采用 链式存储结构


    4. 二叉树的建立

    建立的核心:
    数据结构 = 链表 、实现方式 = 递归 / 非递归 算法

    4.1 数据结构

    采用链表的方式,也称为:二叉链表

    1. 为了确保每个结点都有左右孩子,所以空指针 = 虚结点 = #
    2. 这种处理也称:扩展二叉树

    示意图

    • 节点结构 & 树的定义如下
       /**
         * 设置结点结构
         */
        public static class TreeNode<T> {
            T val; // 二叉树的结点数据
            TreeNode<T> leftNode; // 二叉树的左子树(左孩子)
            TreeNode<T> rightNode; // 二叉树的右子树(右孩子)
    
            public TreeNode(T data,TreeNode<T> left,TreeNode<T> right) {
                this.val = data;
                this.leftNode = left;
                this.rightNode = right;
            }
    
    
            // 获得 & 设置二叉树的结点数据
            public T getData(){
                return val;
            }
    
            public void setData(T data){
                this.val = data;
            }
    
            // 获得 & 设置二叉树的左子树(左孩子)
            public TreeNode getLeftNode(){
                return leftNode;
            }
    
            public void setLeftNode(TreeNode leftNode){
                this.leftNode = leftNode;
            }
    
            // 获得 & 设置二叉树的右子树(右孩子)
            public TreeNode getRightNode(){
                return rightNode;
            }
            public void setRightNode(TreeNode rightNode){
                this.rightNode = rightNode;
            }
        }
    
    
    /**
     * 作用:构造二叉树
     * 注:必须逆序建立,即:先建立子节点,再逆序往上建立
     * 原因:非叶子节点会使用到下面的节点,而初始化是按顺序初始化的,不逆序建立会报错
     */ 
    public Node init(){
        // 结构如下:(由下往上建立)
        //            A
        //       B         C
        //    D         E     F
        //  G   H         I
        Node I = new Node("I", null, null);
        Node H = new Node("H", null, null);
        Node G = new Node("G", null, null);
        Node F = new Node("F", null, null);
        Node E = new Node("E", null, I);
        Node D = new Node("D", G, H);
        Node C = new Node("C", E, F);
        Node B = new Node("B", D, null);
        Node A = new Node("A", B, C);
        return A;  // 返回根节点
    }
    

    4.2 递归 算法

    • 通过 递归方式 构造出整个二叉树
    • 构造过程 = 将遍历算法的输出结点操作 替换成: 生成结点 & 赋值操作 即可

    关于遍历算法,下节会详细说明


    5. 二叉树的遍历

    5.1 定义

    从根节点出发,按照某种次序访问二叉树中的所有结点,使得每个结点被访问1次 且 只被访问1次

    5.2 遍历方式

    二叉树的遍历方式包括:

    1. 前序遍历(深度优先遍历)
    2. 中序遍历
    3. 后序遍历
    4. 层序遍历(广度优先遍历)

    5.3 遍历实现

    遍历的实现方式分为:递归 & 非递归方式,下面会详细说明

    5.3.1 前序遍历

    也称 深度优先遍历

    • 简介

    示意图

    • 递归实现
       /**
         * 内容:前序遍历
         * 方式:递归
         */
         public void preOrder(Node root){
            // 1. 判断二叉树结点是否为空;若是,则返回空操作
            if(root ==null)
                return;
    
            // 2. 访问根节点(显示根结点)
            printNode(root);
    
            // 3. 遍历左子树
            preOrder(root.getLeftNode());
    
            // 4. 遍历右子树
            preOrder(root.getRightNode());
    
        }
    

    示意图

    • 非递归实现
      主要采用 栈实现
      流程图
    /**
      * 方式:非递归(栈实现)
      */
        public static void preOrder_stack(Node root){
    
            Stack<Node> stack = new Stack<Node>();
    
            // 步骤1:直到当前结点为空 & 栈空时,循环结束
            while(root != null || stack.size()>0){
    
                // 步骤2:判断当前结点是否为空
                  // a. 若不为空,执行3
                  // b. 若为空,执行5
                  if(root != null){
    
                    // 步骤3:输出当前节点,并将其入栈
                    printNode(root);
                    stack.push(root);
    
                    // 步骤4:置当前结点的左孩子为当前节点
                    // 返回步骤1
                    root = root.getLeftNode();
    
                }else{
    
                    // 步骤5:出栈栈顶结点
                    root = stack.pop();
                    // 步骤6:置当前结点的右孩子为当前节点
                    root = root.getRightNode();
                      // 返回步骤1
                }
            }
        }
    

    示意图

    5.3.2 中序遍历

    • 简介

    示意图

    • 递归实现
    /**
      * 方式:递归
      */
        public void InOrder(Node root){
        
            // 1. 判断二叉树结点是否为空;若是,则返回空操作
            if(root ==null)
                return;
    
            // 2. 遍历左子树
            InOrder(root.getLeftNode());
    
            // 3. 访问根节点(显示根结点)
            printNode(root);
    
            // 4. 遍历右子树
            InOrder(root.getRightNode());
    
        }
    

    示意图

    • 非递归实现
      主要采用 栈实现

    流程图

    /**
      * 方式:非递归(栈实现)
      */
        public static void InOrder_stack(Node root){
    
            Stack<Node> stack = new Stack<Node>();
    
            // 1. 直到当前结点为空 & 栈空时,循环结束
            while(root != null || stack.size()>0){
    
                // 2. 判断当前结点是否为空
                // a. 若不为空,执行3、4
                // b. 若为空,执行5、6
                if(root != null){
    
                    // 3. 入栈当前结点
                    stack.push(root);
    
                    // 4. 置当前结点的左孩子为当前节点
                    // 返回步骤1
                    root = root.getLeftNode();
    
                }else{
    
                    // 5. 出栈栈顶结点
                    root = stack.pop();
                    // 6. 输出当前节点
                    printNode(root);
                    // 7. 置当前结点的右孩子为当前节点
                    root = root.getRightNode();
                    // 返回步骤1
                }
            }
    

    5.3.3 后序遍历

    • 简介

    示意图

    • 递归实现
    /**
      * 方式:递归
      */
        public void PostOrder(Node root){
            // 1. 判断二叉树结点是否为空;若是,则返回空操作
            if(root ==null)
                return;
    
            // 2. 遍历左子树
            PostOrder(root.getLeftNode());
    
            // 3. 遍历右子树
            PostOrder(root.getRightNode());
    
            // 4. 访问根节点(显示根结点)
            printNode(root);
    
        }
    

    示意图

    • 非递归实现
      主要采用 栈实现

    示意图

    /**
      * 方式:非递归(栈实现)
      */
        public void PostOrder_stack(Node root){
    
            Stack<Node> stack = new Stack<Node>();
            Stack<Node> output = new Stack<Node>();
    
            // 步骤1:直到当前结点为空 & 栈空时,循环结束——> 步骤8
            while(root != null || stack.size()>0){
    
                // 步骤2:判断当前结点是否为空
                // a. 若不为空,执行3、4
                // b. 若为空,执行5、6
                if(root != null){
    
                    // 步骤3:入栈当前结点到中间栈
                    output.push(root);
    
                    // 步骤4:入栈当前结点到普通栈
                    stack.push(root);
    
                    // 步骤4:置当前结点的右孩子为当前节点
                    // 返回步骤1
                    root = root.getRightNode();
    
                }else{
    
                    // 步骤5:出栈栈顶结点
                    root = stack.pop();
                    // 步骤6:置当前结点的右孩子为当前节点
                    root = root.getLeftNode();
                    // 返回步骤1
                }
            }
    
            // 步骤8:输出中间栈的结点
            while(output.size()>0){
                printNode(output.pop());
    
            }
    
        }
    

    示意图

    5.3.4 层序遍历

    • 简介

    示意图

    • 实现思路
      非递归实现,采用 队列

    示意图

    • 算法流程图
      示意图
    /**
      * 方式:非递归(采用队列)
      */
        public void levelTravel(Node root){
            // 创建队列
            Queue<Node> q=new LinkedList<Node>();
    
            // 1. 判断当前结点是否为空;若是,则返回空操作
            if(root==null)
                return;
            // 2. 入队当前结点
            q.add(root);
    
            // 3. 判断当前队列是否为空,若为空则跳出循环
            while(!q.isEmpty()){
    
                // 4. 出队队首元素
                root =  q.poll();
    
                // 5. 输出 出队元素
                printNode(root);
    
                // 6. 若出队元素有左孩子,则入队其左孩子
                if(root.getLeftNode()!=null) q.add(root.getLeftNode());
    
                // 7. 若出队元素有右孩子,则入队其右孩子
                if(root.getRightNode()!=null) q.add(root.getRightNode());
            }
        }
    

    示意图

    5.4 遍历方式总结

    示意图


    6. 二叉树的类型

    • 上述讲解的是基础的二叉树
    • 根据不同的需求场景,二叉树分为许多类型,主要有:

    示意图

    • 下面,我将详细讲解各种二叉树的类型

    6.1 线索二叉树

    • 简介

    示意图

    • 示意图
      示意图

    • 特别注意

      • 问:如何区别该指针 = 指向左(右)孩子 or 前驱(后继)
      • 答:增设标志域:Ltag 和 Rtag

    示意图

    6.2 二叉排序树

    也称:二叉查找树、二叉搜索树

    • 特点
      示意图

    • 作用 & 应用场景

    示意图

    6.3 平衡二叉排序树(AVL树)

    属于 二叉搜索树的一种特殊类型

    • 特点

    示意图

    • 具体介绍

    示意图

    6.4 红黑树

    属于 二叉搜索树的一种特殊类型

    示意图

    6.5 赫夫曼树

    • 简介

    示意图

    • 哈夫曼树算法
      即,如何找出哈弗曼树。具体算法请看下图

    算法描述

    示意图

    更加详细请看文章:http://www.cnblogs.com/mcgrady/p/3329825.html

    • 哈夫曼编码

    示意图

    更加详细请看文章:http://blog.csdn.net/lfeng_coding/article/details/47782141

    6.6 其他类型(特殊形态)

    包括:斜树、满二叉树 & 完全二叉树

    示意图

    6.7 总结

    示意图


    7. 总结


    请帮顶 / 评论点赞!因为你的鼓励是我写作的最大动力!

    展开全文
  • 什么是二叉树

    2018-07-03 19:25:56
    一 什么是二叉树(参看http://media.openonline.com.cn数据结构介绍) 二叉树是树形结构的一种重要类型,在实际应用中具有十分重要的意义。从许多实际问题中抽象出来的数据结构往往是二叉树的形式,即使是一般的树也...
     一 什么是二叉树(参看http://media.openonline.com.cn数据结构介绍)
      二叉树是树形结构的一种重要类型,在实际应用中具有十分重要的意义。从许多实际问题中抽象出来的数据结构往往是二叉树的形式,即使是一般的树也能够简单地转换为二叉树形式,而且二叉树的存储结构及其算法都比较简单,因此我们将详细地讨论关于二叉树的存储、运算及应用。

      二叉树(Binary)是n(n≥0)个结点的有限集合,它的每个结点至多只有两棵子树。它或是空集,或是由一个根结点及两棵不相交的分别称作这个根的左子树和右子树的二叉树组成。

    二 二叉树的性质
      二叉树具有几个非常重要的性质,它们是:
      性质1 二叉树的第i层上至多有2i-1个结点(i≥1)。
      证明:用数学归纳法证明如下:
      ① 当i=1时,只有一个根结点,即2i-1=20=1,命题成立。
      ② 假设对所有的j(1≤j<i),命题成立,即第j层最多有2j-1第个结点。
      ③ 根据归纳假设,第i-1层上最多有2i-2个结点。由于二叉树的每个结点的度至多为2,因此在第i层上的结点数至多是第i-1层上最大结点数的2倍,即为2×2i-2=2i-1。

      性质2 深度为k的二叉树至多有2k-1个结点。
      证明:深度为k的二叉树最多含有的结点数,应是二叉树中每一层上最多含有结点数的和,由性质1可见,深度为k的二叉树的最大结点数为:
        20 + 21 + … + 2k-1= 2k-1
      满二叉树和完全二叉树是两种特殊情形的二叉树。
      一棵深度为k且有2k-1个结点的二叉树称为满二叉树。这种树的特点是每一层上的结点数都达到最大值,因此不存在度数为1的结点,且所有叶子结点都在第k层上。

      若一棵二叉树至多只有最下面两层上结点的度数小于2,并且最下一层上的结点都集中在该层最左边的若干位置上,则此二叉树称为完全二叉树。显然满二叉树是完全二叉树,但完全二叉树不一定是满二叉树。

    三 二叉树存储

         一般二叉树的存储有顺序存储和链式存储两种方式,由于顺序存储在二叉树非完全的时候浪费空间,并且考虑移动删除二叉树的时候需要移动大量的节点,因此一般情况下多数用链式存储方式存储二叉树

    四 二叉树遍历
         遍历一棵非空二叉树的问题可分解为三个子问题:即访问根结点、遍历左子树和遍历右子树。若分别用D、L和R表示以上三个问题,则有DLR、LDR、LRD和DRL、RDL、RLD六种次序遍历方案。其中前三种方案是按先左后右次序遍历根的两棵子树,而后三种则是按先右后左次序遍历两棵子树。由于两者对称,因此我们在这里仅讨论前三种次序的遍历方案。
        在遍历方案DLR中,因为访问根结点的操作在遍历左、右子树之前,故称之为前序(Preorder)遍历或先根遍历;类似地,在方案LDR中,访问根结点的操作在遍历左子树之后和遍历右子树之前,故称之为中序(Inorder)遍历或中根遍历;在方案LRD中,因为访问根结点的操作在遍历左、右子树之后,故称之为后序(Postorder)遍历或后根遍历。显然,遍历左、右子树的问题仍然是遍历二叉树的问题,当二叉树为空时递归遍历结束,所以很容易给出以上三种遍历的递归算法定义。
         由于自己目前从事java android开发,因此自己也简单的实现了一下这三种遍历的非递归方式的算法。

    package com.example.javaapitest;
    
    import android.app.Activity;
    import android.os.Bundle;
    import android.util.Log;
    import android.view.View;
    import com.java.api.test.BinaryTree;
    
    public class MainActivity extends Activity {
    
        @Override
        protected void onCreate(Bundle savedInstanceState) {
            super.onCreate(savedInstanceState);
            setContentView(R.layout.activity_main);
        }
    
        public void startTest(View view) {
            BinaryTree.BinaryTreeNode nodeA = new BinaryTree.BinaryTreeNode();
            nodeA.data = "A";
    
            BinaryTree.BinaryTreeNode nodeB = new BinaryTree.BinaryTreeNode();
            nodeB.data = "B";
    
            BinaryTree.BinaryTreeNode nodeC = new BinaryTree.BinaryTreeNode();
            nodeC.data = "C";
    
            BinaryTree.BinaryTreeNode nodeD = new BinaryTree.BinaryTreeNode();
            nodeD.data = "D";
    
            BinaryTree.BinaryTreeNode nodeE = new BinaryTree.BinaryTreeNode();
            nodeE.data = "E";
    
            BinaryTree.BinaryTreeNode nodeF = new BinaryTree.BinaryTreeNode();
            nodeF.data = "F";
    
            BinaryTree.BinaryTreeNode nodeG = new BinaryTree.BinaryTreeNode();
            nodeG.data = "G";
    
            BinaryTree.BinaryTreeNode nodeH = new BinaryTree.BinaryTreeNode();
            nodeH.data = "H";
    
            BinaryTree.BinaryTreeNode nodeI = new BinaryTree.BinaryTreeNode();
            nodeI.data = "I";
    
            BinaryTree.BinaryTreeNode nodeJ = new BinaryTree.BinaryTreeNode();
            nodeJ.data = "J";
    
            nodeA.leftChildNode = nodeB;
            nodeA.rightChildNode = nodeC;
    
            nodeB.leftChildNode = nodeD;
            nodeB.rightChildNode = nodeE;
    
            nodeC.leftChildNode = nodeF;
            nodeC.rightChildNode = nodeG;
    
            nodeD.leftChildNode = nodeH;
            nodeD.rightChildNode = null;
    
            nodeE.leftChildNode = null;
            nodeE.rightChildNode = null;
    
            nodeF.leftChildNode = nodeI;
            nodeF.rightChildNode = null;
    
            nodeG.leftChildNode = null;
            nodeG.rightChildNode = nodeJ;
    
            nodeH.leftChildNode = null;
            nodeH.rightChildNode = null;
    
            nodeI.leftChildNode = null;
            nodeI.rightChildNode = null;
    
            nodeJ.leftChildNode = null;
            nodeJ.rightChildNode = null;
    
            BinaryTree.inOrder(nodeA);
            Log.d("Util_Test", "");
    
            BinaryTree.preOrder(nodeA);
            Log.d("Util_Test", "");
    
            BinaryTree.postOrder(nodeA);
        }
    
        /*
    01-09 13:08:20.260  8421  8421 D Util_Test: H
    01-09 13:08:20.260  8421  8421 D Util_Test: D
    01-09 13:08:20.260  8421  8421 D Util_Test: B
    01-09 13:08:20.260  8421  8421 D Util_Test: E
    01-09 13:08:20.260  8421  8421 D Util_Test: A
    01-09 13:08:20.261  8421  8421 D Util_Test: I
    01-09 13:08:20.261  8421  8421 D Util_Test: F
    01-09 13:08:20.261  8421  8421 D Util_Test: C
    01-09 13:08:20.261  8421  8421 D Util_Test: G
    01-09 13:08:20.261  8421  8421 D Util_Test: J
    01-09 13:08:20.261  8421  8421 D Util_Test:
    01-09 13:08:20.261  8421  8421 D Util_Test: A
    01-09 13:08:20.261  8421  8421 D Util_Test: B
    01-09 13:08:20.261  8421  8421 D Util_Test: D
    01-09 13:08:20.261  8421  8421 D Util_Test: H
    01-09 13:08:20.261  8421  8421 D Util_Test: E
    01-09 13:08:20.261  8421  8421 D Util_Test: C
    01-09 13:08:20.261  8421  8421 D Util_Test: F
    01-09 13:08:20.261  8421  8421 D Util_Test: I
    01-09 13:08:20.261  8421  8421 D Util_Test: G
    01-09 13:08:20.261  8421  8421 D Util_Test: J
    01-09 13:08:20.261  8421  8421 D Util_Test:
    01-09 13:08:20.261  8421  8421 D Util_Test: H
    01-09 13:08:20.261  8421  8421 D Util_Test: D
    01-09 13:08:20.261  8421  8421 D Util_Test: E
    01-09 13:08:20.261  8421  8421 D Util_Test: B
    01-09 13:08:20.261  8421  8421 D Util_Test: I
    01-09 13:08:20.261  8421  8421 D Util_Test: F
    01-09 13:08:20.261  8421  8421 D Util_Test: J
    01-09 13:08:20.261  8421  8421 D Util_Test: G
    01-09 13:08:20.261  8421  8421 D Util_Test: C
    01-09 13:08:20.261  8421  8421 D Util_Test: A
        * */
    }
    package com.java.api.test;
    
    import java.util.Stack;
    
    /**
     * Created by abm on 18-7-3.
     */
    
    public class BinaryTree {
    
        /*
        * 前序遍历DLR
        * 1. 访问根结点
        * 2. 访问左子树
        * 3. 访问右子树
        *
        * */
        public static void preOrder(BinaryTreeNode root) {
            Stack<BinaryTreeNode> stack = new Stack<>();
            BinaryTreeNode current = root;
            while (current != null || stack.size() > 0) {
                while (current != null) {
                    current.show();
                    stack.push(current);
                    current = current.leftChildNode;
                }
    
                if (stack.size() > 0) {
                    current = stack.pop();
                    current = current.rightChildNode;
                }
            }
        }
    
        /*
        * 中序遍历DLR
        * 1. 访问左子树
        * 2. 访问根结点
        * 3. 访问右子树
        *
        * */
        public static void inOrder(BinaryTreeNode root) {
            Stack<BinaryTreeNode> stack = new Stack<>();
            BinaryTreeNode current = root;
            while (current != null || stack.size() > 0) {
                while (current != null) {
                    stack.push(current);
                    current = current.leftChildNode;
                }
    
                if (stack.size() > 0) {
                    current = stack.pop();
                    current.show();
                    current = current.rightChildNode;
                }
            }
        }
    
        /*
        * 后序遍历LRD
        * 1. 访问左子树
        * 2. 访问右子树
        * 3. 访问根结点
        *
        * */
        public static void postOrder(BinaryTreeNode root) {
            Stack<BinaryTreeNode> stack = new Stack<>();
            BinaryTreeNode current = root;
            BinaryTreeNode pre = null;
            while (current != null || stack.size() > 0) {
                while (current != null) {
                    stack.push(current);
                    current = current.leftChildNode;
                }
    
                if (stack.size() > 0) {
                    current = stack.peek().rightChildNode; //目前节点栈中的栈定情况分为1.叶子2.之前弹出叶子的双亲节点
                    //访问栈顶的右孩子,此时存在情况:1.叶子节点不存在右孩子2.父节点不存在或存在右节点1.1存在则重复遍历右节点树
                    if (current == null || current == pre) { /*当访问到叶子结点的时候并且该叶子结点没有孩子的时候,
                    从结点栈中弹出打印该节点并打印该结点数据,设置之前访问节点为当叶子结点,此时弹出当前叶子结点时,
                    节点栈中栈定节点为之前弹出节点的双亲节点*/
                        current = stack.pop();
                        current.show();
                        pre = current;
                        current = null;
                    }
                }
            }
        }
    
        public static class BinaryTreeNode {
            public String data;
            public BinaryTreeNode leftChildNode;
            public BinaryTreeNode rightChildNode;
    
            public void show() {
                Util.d(data);
            }
        }
    }
    

    展开全文
  • 读完本文你将了解到:什么是二叉树 Binary Tree两种特殊的二叉树二叉树完全二叉树二叉树 和 完全二叉树 的对比图二叉树的实现用 递归节点实现法左右链表示法 表示一个二叉树节点用 数组下标表示法 表示一个节点...


    读完本文你将了解到:

    树的分类有很多种,但基本都是 二叉树 的衍生,今天来学习下二叉树。

    这里写图片描述

    什么是二叉树 Binary Tree

    先来个定义:

    二叉树是有限个节点的集合,这个集合可以是空集,也可以是一个根节点和至多两个子二叉树组成的集合,其中一颗树叫做根的左子树,另一棵叫做根的右子树。

    简单地说,二叉树是每个节点至多有两个子树的树,下面的家谱就是一个形象的二叉树:

    这里写图片描述

    二叉树的定义是一个递归的定义,其中值得注意的是左右子树的概念,因为有左、右之分,下面两棵树并不是同样的二叉树:

    shixinzhang

    两种特殊的二叉树

    有两种特殊的二叉树:

    • 满二叉树
    • 完全二叉树

    满二叉树

    在上文 树及 Java 实现 中我们介绍了 树的高度 的定义,而这里 满二叉树 的定义是:

    如果一棵树的高度为 k,且拥有 2^k-1 个节点,则称之为 满二叉树。

    什么意思呢?

    就是说,每个节点要么必须有两棵子树,要么没有子树。

    完全二叉树

    完全二叉树是一种特殊的二叉树,满足以下要求:

    1. 所有叶子节点都出现在 k 或者 k-1 层,而且从 1 到 k-1 层必须达到最大节点数;
    2. 第 k 层可是不是慢的,但是第 k 层的所有节点必须集中在最左边。

    简单地说, 
    就是叶子节点都必须在最后一层或者倒数第二层,而且必须在左边。任何一个节点都不能没有左子树却有右子树。

    满二叉树 和 完全二叉树 的对比图

    来一张图对比下两者:

    shixinzhang

    二叉树的实现

    二叉树的实现比普通树简单,因为它最多只有两个节点嘛。

    用 递归节点实现法/左右链表示法 表示一个二叉树节点

    public class BinaryTreeNode {
        /*
         * 一个二叉树包括 数据、左右孩子 三部分
         */
        private int mData;
        private BinaryTreeNode mLeftChild;
        private BinaryTreeNode mRightChild;
    
        public BinaryTreeNode(int data, BinaryTreeNode leftChild, BinaryTreeNode rightChild) {
            mData = data;
            mLeftChild = leftChild;
            mRightChild = rightChild;
        }
    
        public int getData() {
            return mData;
        }
    
        public void setData(int data) {
            mData = data;
        }
    
        public BinaryTreeNode getLeftChild() {
            return mLeftChild;
        }
    
        public void setLeftChild(BinaryTreeNode leftChild) {
            mLeftChild = leftChild;
        }
    
        public BinaryTreeNode getRightChild() {
            return mRightChild;
        }
    
        public void setRightChild(BinaryTreeNode rightChild) {
            mRightChild = rightChild;
        }
    }
    

    用这种实现方式表示的节点创建的树,结构如右图所示:

    shixinzhang

    用 数组下标表示法 表示一个节点

    public class BinaryTreeArrayNode {
        /**
         * 数组实现,保存的不是 左右子树的引用,而是数组下标
         */
        private int mData;
        private int mLeftChild;
        private int mRightChild;
    
        public int getData() {
            return mData;
        }
    
        public void setData(int data) {
            mData = data;
        }
    
        public int getLeftChild() {
            return mLeftChild;
        }
    
        public void setLeftChild(int leftChild) {
            mLeftChild = leftChild;
        }
    
        public int getRightChild() {
            return mRightChild;
        }
    
        public void setRightChild(int rightChild) {
            mRightChild = rightChild;
        }
    }
    

    一般使用左右链表示的节点来构造二叉树。

    二叉树的主要方法

    有了节点后接下来开始构造一个二叉树,二叉树的主要方法有:

    • 创建
    • 添加元素
    • 删除元素
    • 清空
    • 遍历
    • 获得树的高度
    • 获得树的节点数
    • 返回某个节点的父亲节点

    1.二叉树的创建

    创建一个二叉树很简单,只需要有一个 二叉根节点,然后提供设置根节点的方法即可:

    public class BinaryTree {
        private BinaryTreeNode mRoot;   //根节点
    
        public BinaryTree() {
        }
    
        public BinaryTree(BinaryTreeNode root) {
            mRoot = root;
        }
    
        public BinaryTreeNode getRoot() {
            return mRoot;
        }
    
        public void setRoot(BinaryTreeNode root) {
            mRoot = root;
        }
    }       
    

    2.二叉树的添加元素

    由于二叉树有左右子树之分,所以添加元素时也分为两种情况:添加为左子树还是右子树:

     public void insertAsLeftChild(BinaryTreeNode child){
            checkTreeEmpty();
            mRoot.setLeftChild(child);
        }
    
        public void insertAsRightChild(BinaryTreeNode child){
            checkTreeEmpty();
            mRoot.setRightChild(child);
        }
    
        private void checkTreeEmpty() {
            if (mRoot == null){
                throw new IllegalStateException("Can't insert to a null tree! Did you forget set value for root?");
            }
        }
    

    在每次插入前都会检查 根节点是否为空,如果是就抛出异常(跟 Android 源码学的嘿嘿)。

    3.二叉树的删除元素

    删除某个元素很简单,只需要把自己设为 null。

    但是为了避免浪费无用的内存,方便 GC 及时回收,我们还需要遍历这个元素的左右子树,挨个设为空:

    public void deleteNode(BinaryTreeNode node){
        checkTreeEmpty();
        if (node == null){  //递归出口
            return;
        }
        deleteNode(node.getLeftChild());
        deleteNode(node.getRightChild());
        node = null;
    }
    

    4.二叉树的清空

    二叉树的清空其实就是特殊的删除元素–删除根节点,因此很简单:

    public void clear(){
        if (mRoot != null){
            deleteNode(mRoot);
        }
    }
    

    5.获得二叉树的高度

    二叉树中,树的高度是 各个节点度的最大值。

    因此获得树的高度需要递归获取所有节点的高度,然后取最大值。

       /**
         * 获取树的高度 ,特殊的获得节点高度
         * @return
         */
        public int getTreeHeight(){
            return getHeight(mRoot);
        }
        /**
         * 获得指定节点的度
         * @param node
         * @return
         */
        public int getHeight(BinaryTreeNode node){
            if (node == null){      //递归出口
                return 0;
            }
            int leftChildHeight = getHeight(node.getLeftChild());
            int rightChildHeight = getHeight(node.getRightChild());
    
            int max = Math.max(leftChildHeight, rightChildHeight);
    
            return max + 1; //加上自己本身
        }
    

    6.获得二叉树的节点数

    获得二叉树的节点数,需要遍历所有子树,然后加上总和。

    public int getSize(){
        return getChildSize(mRoot);
    }
    
    /**
     * 获得指定节点的子节点个数
     * @param node
     * @return
     */
    public int getChildSize(BinaryTreeNode node){
        if (node == null){
            return 0;
        }
        int leftChildSize = getChildSize(node.getLeftChild());
        int rightChildSize = getChildSize(node.getRightChild());
    
        return leftChildSize + rightChildSize + 1;
    }
    

    7.获得某个节点的父亲节点

    由于我们使用左右子树表示的节点,不含有父亲节点引用,因此有时候可能也需要一个方法,返回二叉树中,指定节点的父亲节点。

    需要从顶向下遍历各个子树,若该子树的根节点的孩子就是目标节点,返回该节点,否则递归遍历它的左右子树:

    /**
     * 获得指定节点的父亲节点
     * @param node
     * @return
     */
    public BinaryTreeNode getParent(BinaryTreeNode node) {
        if (mRoot == null || mRoot == node) {   //如果是空树,或者这个节点就是根节点,返回空
            return null;
        } else {
            return getParent(mRoot, node);  //否则递归查找 父亲节点
        }
    }
    
    /**
     * 递归对比 节点的孩子节点 与 指定节点 是否一致
     *
     * @param subTree 子二叉树根节点
     * @param node    指定节点
     * @return
     */
    public BinaryTreeNode getParent(BinaryTreeNode subTree, BinaryTreeNode node) {
        if (subTree == null) {       //如果子树为空,则没有父亲节点,递归出口 1
            return null;
        }
        //正好这个根节点的左右孩子之一与目标节点一致
        if (subTree.getLeftChild() == node || subTree.getRightChild() == node) {    //递归出口 2
            return subTree;
        }
        //需要遍历这个节点的左右子树
        BinaryTreeNode parent;
        if ((parent = getParent(subTree.getLeftChild(), node)) != null) { //左子树节点就是指定节点,返回
            return parent;
        } else {
            return getParent(subTree.getRightChild(), node);    //从右子树找找看
        }
    
    }
    

    二叉树的遍历

    二叉树的遍历单独介绍,是因为太重要了!以前考试就老考这个。

    前面的那些操作可以发现,二叉树的递归数据结构使得很多操作都可以使用递归进行。

    而二叉树的遍历其实也是个 递归遍历的过程,使得每个节点被访问且仅访问一次。

    根据不同的场景中,根节点、左右子树遍历的顺序,二叉树的遍历分为三种:

    • 先序遍历
    • 中序遍历
    • 后序遍历

    这里先序、中序、后序指的是 根节点相对左右子树的遍历顺序。

    先序遍历

    即根节点在左右子树之前遍历:

    • 先访问根节点
    • 再先序遍历左子树
    • 再先序遍历右子树
    • 退出

    代码:

    /**
     * 先序遍历
     * @param node
     */
    public void iterateFirstOrder(BinaryTreeNode node){
        if (node == null){
            return;
        }
        operate(node);
        iterateFirstOrder(node.getLeftChild());
        iterateFirstOrder(node.getRightChild());
    }
    
    /**
     * 模拟操作
     * @param node
     */
    public void operate(BinaryTreeNode node){
        if (node == null){
            return;
        }
        System.out.println(node.getData());
    }
    

    中序遍历

    遍历顺序:

    • 先中序遍历左子树
    • 再访问根节点
    • 再中序遍历右子树
    • 退出

    代码:

    /**
     * 中序遍历
     * @param node
     */
    public void iterateMediumOrder(BinaryTreeNode node){
        if (node == null){
            return;
        }
        iterateMediumOrder(node.getLeftChild());
        operate(node);
        iterateMediumOrder(node.getRightChild());
    }
    

    后序遍历

    即根节点在左右子树之后遍历:

    • 先后序遍历左子树
    • 再后序遍历右子树
    • 最后访问根节点
    • 退出

    代码:

    /**
     * 后序遍历
     * @param node
     */
    public void iterateLastOrder(BinaryTreeNode node){
        if (node == null){
            return;
        }
        iterateLastOrder(node.getLeftChild());
        iterateLastOrder(node.getRightChild());
        operate(node);
    }
    

    遍历小结

    可以看到,三种遍历方式的区别就在于递归的先后。

    shixinzhang

    以上图为例,三种遍历结果:

    先序遍历: 
    1 2 4 5 7 3 6

    中序遍历: 
    4 2 7 5 1 3 6

    后序遍历: 
    4 7 5 2 6 3 1

    总结

    这篇文章介绍了 数据结构中的二叉树的基本概念,常用操作以及三种遍历方式。

    其中三种遍历方式一般在面试中可能会考察,给你两种遍历结果,让你画出实际的二叉树结构。只要掌握三种遍历方式的区别,即可解答。

    一道笔试题

    二叉树遍历

    题目描述

    给定一棵二叉树的前序遍历和中序遍历,求其后序遍历(提示:给定前序遍历与中序遍历能够唯一确定后序遍历)。

    输入:

    两个字符串,其长度n均小于等于26。 
    第一行为前序遍历,第二行为中序遍历。 
    二叉树中的结点名称以大写字母表示:A,B,C….最多26个结点。

    输出: 
    输入样例可能有多组,对于每组测试样例, 
    输出一行,为后序遍历的字符串。

    样例输入:

    FDXEAG 
    XDEFAG

    样例输出是多少呢?

    展开全文
  • 在这篇博客之前,花了些时间了解红黑树的内容,但是没有形成自己的知识图谱,也没有一条...首先以最基本的二叉树开始,由浅入深,逐渐了解各个算法的优缺点适用场景,可以解决什么样的问题,优缺点有哪些,实现权衡...
  • 经过进一步完善,二叉树的图形直观显示终于完成了。看效果图: 下面是原代码: 1、main() //***************************************************************************************** #include&lt;...
  • Android中一般使用的数据结构有java中的基础数据结构List,Set,Map。还有一些Android中特有的几个,SparseArray(使用Map时Key是int类型的时候可以用这个代替)等。 继承关系: Collection&lt;–List&lt...
  • Android常用的数据结构

    2016-10-19 14:40:44
    Android中一般使用的数据结构有java中的基础数据结构Set, List, Map。还有一些Android中特有的几个,SparseArray(使用Map时Key是int类型的时候可以用这个代替)等。
  • 一、基本控件介绍 一般新建组件有两种方式:XML中定义和Java代码实现,一般XML中定义较为常用。   ... android:layout_width="wrap_content" android:layout_height="wrap_content" android:text=
  • Android基本知识点 1、常规知识点 1、 Android类加载器 在Android开发中,不管是插件化还是组件化,都是基于Android系统的类加载器ClassLoader来设计的。只不过Android平台上虚拟机运行的是Dex字节码,一种对class...
  • Android开发之数据结构

    2019-11-21 16:17:44
    数组中的数据元素可以是基本数据类型,也可以是引用数据类型; 数组具有下标,下标从0开始计数,用于快速获取数组中的数据,比如a[0],表示数组中的第一个数据; 数组在创建的时候,需要在内存中申请一段固定...
  • 数据结构 数组: 优点:查询快,如果知道索引可以快速存取 缺点:删除慢,大小固定 有序数组: 优点:比无序数组查找块 缺点:删除和插入慢,大小固定 栈: 优点:提供后进先出的存取方式 缺点:...
  • 二叉树是重要的抽象数据类型,解决很多问题时都需要它。通过本课我们学习这种重要的数据结构,本课注重实践,没有过多枯燥的理论,我们的重点放在编码实现各种算法,这对于熟练使用Python语言也是很有益处的。...
  • 1. 链表与数组。 2. 队列和栈,出栈与入栈。 3. 链表的删除、插入、反向。 (1)反向链表的定义: class Node{ public int val; public Node next; public Node(int val){this.val=val;...
  • AndroidAll 项目地址:chiclaim/AndroidAll 简介: Android 程序员的技术栈大全 更多:作者提 Bug 标签: 内容涵盖绝大部分 Android 程序员所需要的技能:「设计模式」「Flutter」「ReactNative」「Kotlin」...
  • 利用递归算法、堆栈打造一个android可擦除思维导图 用SurfaceView实现级联分层图(粗略篇) 效果图打头阵: 这些和亲戚关系图谱,或者思维导图类似,最近公司的医疗项目也用到了这个,记录学习下; 刚开始的...
  • 【摘要】查找—-用关键字标识一个数据元素,查找时根据给定的某个值,在表中确定一个关键字的值等于给定值的记录或数据元素。在计算机中进行查找的方法是根据表中的记录的组织结构确定的。查找功能数据处理的一个...
  • 简介android是不提供树形控件的,如果需要使用树形控件,我们应该怎么做呢? 先看效果 上图是一个明显的树形结构实现原理在逻辑上,它们是包含关系,数据结构上是多叉树,这是毋庸置疑的。但是,显示的时候,...
1 2 3 4 5 ... 20
收藏数 3,829
精华内容 1,531
关键字:

二叉树 数据类型android