精华内容
下载资源
问答
  • 数组构造二叉树代码

    千次阅读 多人点赞 2016-05-12 14:23:21
    数组构造二叉树代码,用于本地测试二叉树的特性和算法题目。约定:二叉树采用宽度优先遍历来表示二叉树二叉树的节点存储在数组内,数组中的’#’代表空节点。

    最近做二叉树的题目,写完代码想在本地编译运行,结果一时半会想不起树如何构造。而网上竟然也没有类似代码,于是自己写了个。

    约定:二叉树采用宽度优先遍历来数组化,二叉树的节点按照BFS的顺序依次存储在数组内,数组中的’#’代表空节点,末尾的’#’可省略。
    如:

        1
       / \
      2   3
     / \   \
    4   5   6
       / \
      7   8

    这棵树会被序列化为:{1,2,3,4,5,#,6,#,#,7,8},后面的四个#被省略。

              7
           /    \
        2         8
      /   \        \
     1    6        10
          /       /  \
         3        9   11
           \
           5
          /
         4
    //数组应该为{7,2,8,1,6,#,10,#,#,3,#,#,#,9,11,#,#,#,#,#,5,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,4}
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    //二叉树的节点定义
    class TreeNode {
         public:
             int val;
             TreeNode *left, *right;
             TreeNode(int val) {
                 this->val = val;
                 this->left = this->right = NULL;
             }
    };
    
    //从数组的某个位置的元素开始生成树
    TreeNode* createTree(vector<int> list, int start){
    
        if (list[start] == '#') {
            return NULL;
        }
    
        TreeNode* root = new TreeNode(list[start]);
    
        int lnode = 2*start + 1;
        int rnode = 2*start + 2;
        if ( lnode > list.size() -1) {
            root -> left = NULL;
        }else{
            root -> left = createTree(list, lnode);
        }
    
        if (rnode > list.size() -1) {
            root -> right =NULL;
        }else{
            root -> right = createTree(list, rnode);
        }
    
        return root;
    }
    
    //先序遍历函数
    void PreOrderTraverse(TreeNode *T)                
    {
        if(T)
        {
            cout<<T->val<<" ";                
            PreOrderTraverse(T->left);           
            PreOrderTraverse(T->right);           
        }
        return;
    }
    
    
    int main()
    {
        vector<int> datanum = {1,2,3,4,5,'#',6,'#','#',7,8};
        //1,2,3,4,5,'#',6,'#','#',7,8,'#','#','#','#' 后面的#可省略
        TreeNode *t;
        t = createTree(datanum, 0);
    
        printf("The pre order is : ");
        PreOrderTraverse(t);
    
        //下面就可以用构造出的树做测试了
    
        return 0;
    }
    
    
    
    展开全文
  • 比如数组: int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9} 变为二叉树为: 分析: 1、首先要定义每一个结点,每一个结点包括自身值,左结点和右结点,实现get、set方法。 public class Node { public int data;...

    二叉树是每个节点最多有两个子树的树结构。通常子树被称作 “左子树” 和 “右子树”。

    比如数组:
    int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9}

    变为二叉树为:

     

    分析:

    1、首先要定义每一个结点,每一个结点包括自身值,左结点和右结点,实现get、set方法。

    public class Node {
         public int data;      //自己本身值
         public Node left;     //左结点
         public Node right;     //右结点
         public Node() {
         }
         public Node(int data, Node left, Node right) {
              this.data = data;
              this.left = left;
              this.right = right;
         }
         public int getData() {
             return data;
         }
         public void setData(int data) {
             this.data = data;
         }
         public Node getLeft() {
             return left;
         }
         public void setLeft(Node left) {
             this.left = left;
         }
         public Node getRight() {
             return right;
         }
         public void setRight(Node right) {
             this.right = right;
         }
    }

    2、创建二叉树

    public class Demo2 {
        public static List<Node> list = new ArrayList<Node>();      //用一个集合来存放每一个Node
        public void createTree(int[] array) {
        for (int i = 0; i < array.length; i++) {
             Node node = new Node(array[i], null, null);    //创建结点,每一个结点的左结点和右结点为null
             list.add(node); // list中存着每一个结点
        }
        // 构建二叉树
        if (list.size() > 0) {
            for (int i = 0; i < array.length / 2 - 1; i++) {       // i表示的是根节点的索引,从0开始
                 if (list.get(2 * i + 1) != null) { 
                      // 左结点
                      list.get(i).left = list.get(2 * i + 1);
                 }
                 if (list.get(2 * i + 2) != null) {
                      // 右结点
                      list.get(i).right = list.get(2 * i + 2);
                 }
           }
           // 判断最后一个根结点:因为最后一个根结点可能没有右结点,所以单独拿出来处理
           int lastIndex = array.length / 2 - 1;
           // 左结点
           list.get(lastIndex).left = list.get(lastIndex * 2 + 1);
           // 右结点,如果数组的长度为奇数才有右结点
           if (array.length % 2 == 1) {
                list.get(lastIndex).right = list.get(lastIndex * 2 + 2);
           }
       }
    }

    // 遍历,先序遍历
    public static void print(Node node) {
         if (node != null) {
               System.out.print(node.data + " ");
               print(node.left);
               print(node.right);
         }
    }

       public static void main(String[] args) {
            int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
            Demo2 demo = new Demo2();
            demo.createTree(array);
            print(list.get(0));
      }
    }

    结果为:

    1 2 4 8 9 5 3 6 7 

     

    分析:

    array = {1, 2, 3, 4, 5, 6, 7, 8, 9}
    lastIndex = 3;
    i=0
    1
    2 3
    i=1
    2
    4 5
    i=2
    3
    6 7

             1
          2     3
         4 5   6 7
     

    lastIndex=3
    4
    8 9

     

             1
          2     3
         4 5   6 7
        8 9

    展开全文
  • 有序数组转换为平衡二叉树(BST)

    千次阅读 2016-07-04 11:20:49
    把有序数组转换为平衡二叉树。TreeNode* buildTree(vector &nums,int start,int last) { int mid = (start + last) / 2; TreeNode *root = new TreeNode(nums[mid]); if(start == last) { return root; } if...
    把有序数组转换为平衡二叉树。
    
    <pre name="code" class="cpp">TreeNode* buildTree(vector<int> &nums,int start,int last)
    {
    	int mid = (start + last) / 2;
    	TreeNode *root = new TreeNode(nums[mid]);
    	if(start == last)
    	{
    		return root;
    	}
    	if(start <= mid - 1)
    	{
    		root->left = buildTree(nums,start,mid-1);
    	}
    	if(mid+1 <=  last)
    	{
    		root->right = buildTree(nums,mid+1,last);
    	}
    	return root;
    }
    
    TreeNode* sortedArrayToBST(vector<int>& nums) {
    	if(nums.empty())
    		return NULL;
    	return buildTree(nums,0,nums.size()-1);
    }
     
    
    展开全文
  • 请实现两个函数,分别用来序列化和反序列化二叉树。 示例: ...序列化为 "[1,2,3,null,null,4,5]" 注意:本题与主站 297 题相同:https://leetcode-cn.com/problems/serialize-and-deserialize-binar...
    请实现两个函数,分别用来序列化和反序列化二叉树。
    
    示例: 
    
    你可以将以下二叉树:
    
        1
       / \
      2   3
         / \
        4   5
    
    序列化为 "[1,2,3,null,null,4,5]"
    注意:本题与主站 297 题相同:https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/
    
    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
    
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Codec {
    
        public StringBuilder rserialize(TreeNode root, StringBuilder sb){
            if(root == null) sb.append("null,");
            else {
                sb.append(root.val);
                sb.append(",");
    
                rserialize(root.left, sb);
                rserialize(root.right, sb);
            }
            return sb;
        }
        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            return rserialize(root, new StringBuilder()).toString();
        }
    
        public TreeNode rdeserialize(ArrayList<String> list) {
            String s = list.remove(0);
            TreeNode root = null;
            if(!s.equals("null")){
                root = new TreeNode(Integer.parseInt(s));
                root.left = rdeserialize(list);
                root.right = rdeserialize(list);
            }
            return root;
        }
        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            String[] parts = data.split(",");
            ArrayList<String> list = new ArrayList<>(Arrays.asList(parts));
            return rdeserialize(list);
        }
    }
    
    // Your Codec object will be instantiated and called as such:
    // Codec codec = new Codec();
    // codec.deserialize(codec.serialize(root));
    
    展开全文
  • 目录题目根据数组构建二叉树:用队列,依次取一个结点然后按数组顺序构建左右孩子 题目 请实现两个函数,分别用来序列化和反序列化二叉树。 示例: 你可以将以下二叉树: 1 / \ 2 3 / \ 4 5 序列化为 "[1,2,...
  • 输入一个有序的数组,如何实现将这个有序整数数组放到二叉树中? 分析:对于二叉树,可以将这个有序数组插入到二叉搜索树中,毕竟二叉搜索树还是有很多特定的。那么对于创建二叉搜索树来说,就是简单的递归了。关于...
  • 二叉树 定义: 二叉树是结点的有限集合,这个集合或者是空的,或者由一个根结点或两棵互不相交的称为左子树的和右子树的二叉树组成。 特点: 1)每个结点至多有二棵子树(即不存在度大于2的结点) 2)二叉树的...
  • 二叉树 迭代 前 中 后Data structures and algorithms are the heart and soul of computer science and software. One cannot learn programming without understanding how data is organized in code and how to ...
  • 二叉树的常见算法

    2020-04-14 16:33:04
    二叉树的常见算法 二叉树的前序遍历 描述:(1)访问根节点;(2)递归遍历左子树;(3)递归遍历右子树; 题解: //递归前序遍历 import java.util.ArrayList; public void preTraversal(Node node){ ...
  • 序列化二叉树 NowCoder 题目描述: 请实现两个函数,分别用来...1.序列化是指通过前序遍历把二叉树变成数组 2.反序列化是指重建二叉树 public class Solution { public int index = -1; String Serialize(TreeNo...
  • 二叉树数组表示 1. [代码][C/C++]代码 01 #include 02 03 /* 04 *使用数组创建二叉树 05 * 1 初始化二叉树,btree[level] 初始化为...
  • 1 二叉树的二叉链表示意图   二叉链表的每个结点由三个域组成:数据域,左指针域和右指针域。左右指针分别用来保存左右孩子结点的存储地址。 2 二叉链表实现二叉树 2.1 头文件及其定义
  • 二叉树的顺序结构存储(堆的实现)

    千次阅读 2019-05-30 15:40:26
    但是普通的二叉树是不适合用数组来存储,因为可能会存在大量的空间浪费,而完全二叉树是可以用顺序结构来存储的,现实中我们通常把堆(一种二叉树)使用顺序结构数组来存储,需要注意的是这里的堆和我们操作系统虚拟进程...
  • 标签6二叉树数组

    2020-07-13 21:15:21
    标签6二叉树 236. 二叉树的最近公共祖先 解法:思路见代码注释 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { //递归终止条件 if(root == null || p == root || q == root...
  • 众所周知,二叉搜索树的中序遍历(左中右)是一个有序递增数列,高度平衡二叉树左右高度差不超过1,可以从数组中间取值作为根节点,把整棵树分成两部分,之后利用递归分别从左右两个区间取中间值作为左右结点,有点...
  • 数组下标查找数据速度很快,但插入数据需要拷贝数组数组扩容,数据全体向后移动,所以插入数据效率低下。 链表在插入方面表现优良,但查找数据仍要遍历这个链表,查找效率低下。 哈希表(散列表)hash表其实是...
  • c++二叉树

    2021-08-05 21:17:40
    二叉树:如果一棵二叉树只有度为0的结点和度为2的结点,并且度为0的结点在同一层上,则这棵二叉树为满二叉树。 //深度为k,有2^k-1个节点的二叉树。 完全二叉树:在完全二叉树中,除了最底层节点可能没填满外,...
  • 二叉树的顺序存储,指的是使用顺序表(数组)存储二叉树。需要注意的是,顺序存储只适用于完全二叉树。换句话说,只有完全二叉树才可以使用顺序表存储。因此,如果我们想顺序存储普通二叉树,需要提前将普通二叉树...
  • 当链表结构达到8个时候,会将前面的8个链表转换成二叉树结构,而不是以第8个链表为根节点,往后依次形成二叉树,即将数组+链表变成了数组+二叉树,所以最终的结构可能是:数组+链表+二叉树,其中二叉树数组为基础...
  • 第四章 树和二叉树 一、二叉树 1、二叉树的基本概念(逻辑结构) 二叉树的定义 二叉树是n(n>=0)个结点的有限集合。n=0时,二叉树为空树;n>0时,由根结点和两个互不相交的被称为根的左子树和右子数组成。...
  • 二叉树遍历是非常经典的算法题,也是二叉树的一道基础算法题。 但是在平常的笔试面试中,其出现的频率其实并不是特别的高,我推测是这种题目相对来说比较基础,算是一个基础知识点。 比如剑指offer中出现的后序遍历...
  • 定义一个数组,初始化为空。在数组上执行两种操作: 1、增添1个元素,把1个新的元素放入数组。 2、输出并删除数组中最小的数。 使用堆结构实现上述功能的高效算法。 输入 第一行输入一个整数t,代表测试数据的组数。...
  • 二叉树

    2018-09-02 18:00:37
    二叉树是一种树型结构,它的特点是每个结点至多只有两棵子树,并且,二叉树的子树有左右之分,其次序不能任意颠倒。 二叉树具有下列重要特性: 1.在二叉树的第i层上至多有2^(i-1)个结点(i&gt;=1)。 2.深度为k...
  • 二叉树整理

    2021-08-06 02:49:53
    文章目录二叉树树的定义二叉树的定义二叉树的性质二叉树的存储结构二叉树的遍历先序遍历中序遍历后序遍历二叉树的建立二叉树扩展内容二叉树的高度计算二叉树非递归实现先序遍历层次遍历带权路径和结点最大距离最长...
  • 迭代器, 数组和集合的转换, Comparable和Comparator, 二叉树1.迭代器2.数组和集合的转换3. Comparable和Comparator4.有序二叉树 1.迭代器 1.迭代器中使用迭代, 然后直接使用 集合.remove(迭代出的元素) 异常: ...
  • 数据结构——二叉树

    千次阅读 2019-07-18 10:26:32
    二叉树的顺序表示 Lineartree.c #include <stdio.h> #include <string.h> #include <stdlib.h> #include <math.h> #define NIL 0 //初始化二叉树时使用 //判断函数的返回值时使用 ...
  • 所以将完全二叉树看成是一个数组或者链表都是可以的。 完全二叉树的总节点与叶子节点数量的关系 叶子节点数量 = (总结点数量 + 1)/ 2 二叉树的三种遍历方式介绍 先根序:根--->左子树--->右子树 中根序:左子树---...
  • 本篇介绍线索化二叉树、线索化后的中序遍历以及反向输出中序遍历。 注:(不管是前序遍历、中序遍历或者后序遍历,道理都是一样的,只不过顺序不一样,所以本篇的就拿中序遍历作为讲解,方便统一与理解) 文章目录1....

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,810
精华内容 3,924
关键字:

数组化为二叉树