精华内容
下载资源
问答
  • 主要用到递归思想,自己调用自己,第个问题以来于第...设计二叉树类,其中左右子树属性是其本身类 package beans; import java.util.ArrayList; import java.util.List; public class binaryTree { private ...

    主要用到递归思想,自己调用自己,第一个问题以来于第二问题的解决,第二个依赖于第三个。。。以此类推,当最后一个问题解决时,前面的问题都将解决。

    设计二叉树类,其中左右子树属性是其本身类

    package beans;
    
    import java.util.ArrayList;
    import java.util.List;
    
    
    
    public class binaryTree {
        private Object rootnode;
        private binaryTree leftchild;
        private binaryTree rightchild;
        
        //构造方法初始化
        public  binaryTree() {
        	this.rootnode= null;
        	this.leftchild=null;
        	this.rightchild=null;
    		
    	}
    
        public void	add(Object value) {
        	//如果节点值为null,则把传进来的值赋值给节点
    		if (rootnode==null) {
    			rootnode=value;
    		}else {
    			//如果节点有值,则进行比对,如果小于或者等于节点值,进入下一环
    			if ((Integer)rootnode>=(Integer)value) {
    				/*如果左子树为空,则又新建一个三个属性都为null的二叉树对象给左子树,,
    				用递归的思想,将value值传递给节点(整个递归中每一个环的左子树一直为空)*/
    				if (null == leftchild){
    					leftchild = new binaryTree();}
    				//左子树不为空,则将值与子树的节点对比,对比后发现其左子树又为空,重复上一条的过程
    				    leftchild.add(value);
    				    
    			 //如果节点有值,但是参数value大于节点的值则进入右子树
    			}else {
    				if (null==rightchild) {
    					rightchild=new binaryTree();
    				}
    				rightchild.add(value);
    			}
    		}
    	}
    
    /*中序遍历,同样用到递归思想,这里注意addAll()和add()的区别,addAll是将一个list的所有元素全部添加到另一个list中,而add只是将对象放到lis中t的一个元素中。前序遍历和后序遍历只需要调换   values.add(rootnode);  的位置即可,前序就放左节点遍历的前面,后序就放右节点遍历的后面。
    */
    
        public List<Object> values() {
            List<Object> values = new ArrayList<>();
              
            // 左节点的遍历结果
            if (null != leftchild){
                values.addAll(leftchild.values());         
            }
            // 当前节点
            values.add(rootnode);  
            // 右节点的遍历结果
            if (null != rightchild){
                values.addAll(rightchild.values());         
            }
            return values;
        }
           //镜像二叉树(用递归)
    	public binaryTree mirrorTree(binaryTree tree) {
    		if (tree.leftchild!=null&&tree.rightchild!=null) {
    			binaryTree temp	=new binaryTree();
    	        temp=tree.rightchild;
    	        tree.rightchild=tree.leftchild.mirrorTree(tree.leftchild);
    	        tree.leftchild=temp.mirrorTree(temp);
    		}else if (tree.leftchild!=null&&tree.rightchild==null) {
    			  tree.rightchild=tree.leftchild.mirrorTree(tree.leftchild);
    			  tree.leftchild=null;
    		}else if (tree.leftchild==null&&tree.rightchild!=null) {
    			   tree.leftchild=tree.rightchild.mirrorTree(tree.rightchild);
    			   tree.rightchild=null;			   
    		}
    	
    		return tree;
    	}
    	}
    

    主函数

    package offerPractical;
    
    import java.util.List;
    import java.util.Scanner;
    
    import beans.binaryTree;
    
    public class TreeMirror {
    
    	// 控制台输入字符串转换整形数组
    	public int[] translate(String str) {
    
    		String[] emmer = str.split(",");
    		int[] sum = new int[emmer.length];
    		for (int i = 0; i < emmer.length; i++) {
    			sum[i] = Integer.parseInt(emmer[i]);
    		}
    		return sum;
    	}
    
    	public static void main(String[] args) {
    		// 1将数组进行二叉树排序
    		// 1.1控制台输入一串整形数组,将输入的字符串转成整形数组。
    		TreeMirror treeMirror = new TreeMirror();
    		Scanner scanner = new Scanner(System.in);
    		String string = scanner.next();
    		int[] A = treeMirror.translate(string);
    		// 1.2利用递归的思想,构建二叉树
    		binaryTree bTree = new binaryTree();
    		for (int i = 0; i < A.length; i++) {
    			bTree.add(A[i]);
    		}
    		// 遍历二叉树(中序)
    		List<Object> tree = bTree.values();
    		for (Object object : tree) {
    			System.out.println((Integer) object);
    		}
    		// 构建镜像二叉树(递归)
    		binaryTree bTree2 = bTree.mirrorTree(bTree);
    		// 遍历二叉树(中序)
    		List<Object> tree2 = bTree2.values();
    		System.out.println("镜像二叉树的中序排列");
    		for (Object object : tree2) {
    
    			System.out.println((Integer) object);
    		}
    	}
    
    }
    
    
    展开全文
  • 数组存入二叉树

    2011-08-11 23:42:30
     手工创建二叉树并实现前、中、后序排列很简单,当尝试将数组存入二叉树时,感觉就没那么容易了,当时分析得很简单就是在数组中任意取个数作为根结点,然后将剩余的数与该结点进行比较,比根结点小的放到左结点上...

    将数组存入二叉树

        手工创建二叉树并实现前、中、后序排列很简单,当尝试将数组存入二叉树时,感觉就没那么容易了,当时分析得很简单就是在数组中任意取一个数作为根结点,然后将剩余的数与该结点进行比较,比根结点小的放到左结点上,大的放到右结点上,我本想用一次循环将所有的数字就各归其位,在一次比较中将所有的数分成了两类,一类比根结点大一类比根结点小,虚拟机将它们赋值时就会无所是从。 总想将所有工作一次完成 , 于是就磕死在这个地方了。

     

    真正要实现将数组存入二叉树我的实现方法是:先将数组中的第一个元素作为根结点的数据

    int n = array[0];   

      root = new Node(n);

    然后循环调用向树中加入数据的方法,并向其中传入结点和数组中数据:

    for(int i=1;i<array.length;i++){  

      addTotree(root,array[i]);     

    }                                 

    在将数组中数据加入到树的相应位置时应先创建一个结点对象                                  

    // 把传入的数创建为一个二叉树的节点                  

    Node newnode=new Node(data);           

    然后进行判断传入的数组中的数据与传入结点中的数据的大小,若传入的数据比根结点小且当左子树不为空则递归为空则加到左结点

    if((Integer)node.getObj()>data){

             // 如果左结点不为空                  

             if(node.getLeft()!=null){   

                       // node 左结点赋给 node       

                       node = node.getLeft();  

                       // 递归                    

                       addTotree(node,data);   

                                               

             }else{                       

                                               

                       node.setLeft(newnode);  

                       newnode.setParent(node);

             }                           

    加到右子树的方法同样。

    这样也就将数组全部加到二叉树中了,打印时同样用到了递归

    /**                               

      * 遍历打印二叉树中的元素                     

      * @param root                    

      */                                

    public void printTree(Node root) {

             // 中序遍历                        

             if (root != null) {           

                       printTree(root.getLeft());

                       Object obj = root.getObj();

                       System.out.println(obj);  

                       printTree(root.getRight());

             }                              

    }                                 

    按照中序遍历即可得到按顺序排列的一组数据。

     
    package javastudy.caidan.二叉树0810;
    
    /**
     * 二叉树类
     * 
     * @author 蔡丹
     * 
     */
    public class Tree {
    	private Node root;
    	private Node node;
    	/**
    	 * 程序入口
    	 * @param args
    	 */
    	public static void main(String args[]) {
    		// 创建一个二叉树对象
    		Tree tr = new Tree();
    		int length=10;
    		int [] array=tr.createSrcArray(length);
    		for(int i=0;i<array.length;i++){
    			System.out.print(array[i]+"\t");
    		}
    		System.out.println("\n");
    		// 创建一个根结点
    		Node root = tr.arrayTotree(array);
    		// 遍历打印二叉树
    		tr.printTree(root);
    	}
    	public int[] createSrcArray(int len){
    		// 初始化要排序数组中的值
    		int[] array = new int[len];
    		for(int i=0;i<array.length;i++){
    			// 创建一个随即对象
    			java.util.Random ran = new java.util.Random();
    			// 调用随即对象,每次循环时生成一个0~100间随机数
    			int value = ran.nextInt(100);
    			// 给数组中指定位置填上随机数
    			array[i] = value;
    			
    		}
    		return array;
    	}
    	/**
    	 * 将数组中的数传入树中	
    	 * @param array
    	 * @return
    	 */
    	public Node arrayTotree(int[] array){
    		// 如果为空抛出异常
    		if(array.length==0){
    			throw new RuntimeException("<<<<<<<<<<");
    		}
    		else {
    			int n = array[0];
    			 root = new Node(n);
    			 for(int i=1;i<array.length;i++){
    				 addTotree(root,array[i]);
    			 }
    		}		
    		return root;
    	}
    	
    	/**
    	 * 将数组中的数存到树中相应位置
    	 * @param node
    	 * @param array
    	 */
    	public void addTotree(Node node,int data){
    		
    		//把传入的数创建为一个二叉树的节点
    		Node newnode=new Node(data);		
    		if((Integer)node.getObj()>data){
    			// 如果左结点不为空
    			if(node.getLeft()!=null){
    				// 将node左结点赋给node
    				node = node.getLeft();
    				// 递归
    				addTotree(node,data);
    				
    			}else{
    				
    				node.setLeft(newnode);
    				newnode.setParent(node);
    			}
    			
    		}
    		else{
    			// 如果结点为空
    			if(node.getRight()!=null){
    				//将该结点设为右结点
    				node = node.getRight();
    				// 递归
    				addTotree(node,data);
    			}else{
    				node.setRight(newnode);
    				newnode.setParent(node);
    			}
    		}		
    	}
    	/**
    	 * 遍历打印二叉树中的元素
    	 * @param root
    	 */
    	public void printTree(Node root) {
    		// 中序遍历
    		if (root != null) {
    			printTree(root.getLeft());
    			Object obj = root.getObj();
    			System.out.println(obj);
    			printTree(root.getRight());
    		}
    	}
    }
    
    展开全文
  • 根据个有序数组,构造颗二叉搜索树 思路:因为数组有序,所以数组中间节点是该二叉树的根节点,因为二叉树的定义是右子树都大于根节点,左子树都小于根节点,构造完根节点后,分别截取数组的前半段和后半段分别...

    根据一个有序数组,构造一颗二叉搜索树

    思路:因为数组有序,所以数组中间节点是该二叉树的根节点,因为二叉树的定义是右子树都大于根节点,左子树都小于根节点,构造完根节点后,分别截取数组的前半段和后半段分别递归构造左子树和右子树

     

     1 package com.rui.microsoft;
     2 
     3 public class Test86_BuildBSTByArray {
     4 
     5     public static void main(String[] args) {
     6         int[] a = {1,2,3,4,5};
     7         Test86_BuildBSTByArray app = new Test86_BuildBSTByArray();
     8         Node root = app.build(a, 0, a.length-1);
     9         System.out.println(root.value);
    10     }
    11     
    12     Node build(int[] a, int start, int end){
    13         if(start > end) return null;
    14         int mid = start + (end - start) / 2;
    15         Node root = new Node(a[mid]);
    16         root.left = build(a, start, mid - 1);
    17         root.right = build(a, mid+1,end);
    18         return root;
    19     }
    20     
    21     static class Node{
    22         int value;
    23         Node left;
    24         Node right;
    25         Node(int v){
    26             this.value = v;
    27         }
    28     }
    29 }

     

    转载于:https://www.cnblogs.com/aalex/p/5057440.html

    展开全文
  • 输入二叉树数组,函数能够生成对应的二叉树的结构 代码 const deserialize = (data) => { let res = '' for (let v of data) { res = res + v + ','; } for (let i = 0; i <= data.length; i++) ...

    需求

    • 输入一个二叉树的数组,函数能够生成对应的二叉树的结构

    代码

    const deserialize = (data) => {
    
        let res = ''
        for (let v of data) {
            res = res + v + ',';
        }
        for (let i = 0; i <= data.length; i++) {
            res = res + 'null' + ','
        }
        data = res;
    
        function TreeNode(val) {
            this.val = val;
            this.left = null;
            this.right = null;
        }
        if (data.length === 0) return null;
        const list = data.split(',');   // split成数组
        list.splice(list.length - 1);
        let list_Pointer = 1;
        let queue_pointer = 0;
        const root = new TreeNode(list[0])
        let queue = [root];
    
        while (list_Pointer !== list.length) {
            if (queue[0] === null) {
                queue.shift();
                queue_pointer++;
                continue;
            }
            if (queue_pointer === list_Pointer) {
                list_Pointer = list_Pointer + 2;
            }
            if (list[list_Pointer] === 'null') {
                queue[0].left = null;
            } else {
                queue[0].left = new TreeNode(list[list_Pointer]);
            }
            if (list[list_Pointer + 1] === 'null') {
                queue[0].right = null;
            } else {
                queue[0].right = new TreeNode(list[list_Pointer + 1]);
            }
            queue.push(queue[0].left);
            queue.push(queue[0].right);
            queue.shift();
            queue_pointer++
            list_Pointer = list_Pointer + 2;
        }
        return root
    };
    
    const test2 = deserialize([1,2,3,4]);
    

    注意事项

    这里的二叉树的每一个节点的val值不是Number类型的,而是字符串类型的

    展开全文
  • leetcode字符串生成二叉树、链表前言、leetcode字符串生成二叉树1.1、golang版本1.1.1 使用方式1.2、java版本(待更新)二、leetcode字符生成链表2.1、golang版本2.1.1 使用方式2.2 java版本(待更新)总结 ...
  • 根据个字符数组创建二叉树 以’#‘代表节点为空,标识到非’#'创建节点并且赋值这个节点 思想:递归 ```c struct node{ char data; struct node*lchild;//指向左孩子 struct node * rchild;//指向右孩子 }...
  • // 思路,利用先序遍历和中序遍历将树构建出来,再用后续遍历遍历树,放在数组中,再输入结果 // ps: 直接输出也可以,写注释的时候才想到可以直接输出 // 先序遍历第个一定是根节点 // 中序遍历表示着遍历的顺序...
  • python 数组构建完全二叉树

    千次阅读 2019-08-20 08:56:52
    二叉树:树中除了叶子节点,每个节点都有两个子...二叉树主要有两种实现方式,数组形式和链表形式,其中数组形式是利用完全二叉树的性质5: 性质5:如果对棵有n个结点的完全二叉树的结点按层序编号,则对任一...
  • Java实现生成二叉树

    2021-01-15 14:42:36
    (2)如果有一串数组元素:6,3,2,5,4,1,8,7,9 , 组成的二叉树应该是怎样的? (3)过程解析: 1:首先二叉树包含三个信息,左节点,右节点,还有当前节点value。 2:在创建时肯定是拿一个元素做根节点,然后把后续...
  • 本文主要实现,根据数据动态创建二叉树的功能。 实现结果如下: ----->1 ----->2 ----->3 ----->4 ----->6 ----->5
  • 先定义个root = arr[mid]; root.left 递归左半部分 root.right 递归右半部分 返回root function sortedArrayToBST (arr) { if (!arr.length) { return null; } if (arr.length === 1) { return arr[0]; }...
  • 编写个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀,返回空字符串 “”。 示例 1: 输入: [“flower”,“flow”,“flight”] 输出: “fl” 示例 2: 输入: [“dog”,“racecar”,“car”] 输出: ...
  • 在写LeetCode题时,有时候会遇到一些问题,想要...字符串生成二叉树: 这个方法主要借鉴下面这篇文章: leetcode小函数, 根据字符串生成二叉树 //输入字符 [1,2,3,4,5] #include<vector> #include <io...
  • 自动生成完全二叉树

    2021-04-20 18:56:15
    基本思路就是直接生成一数组长度length的节点 然后利用完全二叉树的性质和数组的下标把它们起来 要用到的完全二叉树的性质 分支节点个数 = 总节点个数 整除 2 (在数学中就是 除以二 再向下取整) 序.
  • 用广义表表示二叉树结构如下: (A (B (,D (E,E),C)) 算法如下: #include <stdio.h> #include <stdlib.h> // 定义节点 typedef struct Node{ char data; struct Node* lChild; struct Node* ...
  • 将字符的内容转换为二叉树

    千次阅读 2019-10-23 17:46:27
    问题:从控制台中输入一串“A(B(C,D(,E)),F(G,H(M,N(,Q))))“,将其转化建立一棵二叉树。 从这个问题我们可以知道,首先我们需要一个将这个字符串所表示的二叉树用代码的方式建立起来。我们先来看看这个字符串所...
  • 二叉树生成) 层次遍历序列

    千次阅读 2020-03-05 14:45:23
    输入二叉树的层次遍历序列,生成对应的二叉树。 如输入1##, 生成一个根节点值为1的树。
  • 输入leetcode测试用例[1,2,null,3]类型字符,返回根节点指针。判断逻辑和leetcode一致,null结点无须额外输入null子结点,并且自动舍弃无效结点,例如输入[1,null,2,null,null,3],算法会自动舍弃结点3. 网上找的...
  • 通过字符(括号表示法)创建二叉树(C语言实现) 实现步骤 假设采用括号表示法表示的二叉树字符str是正确的,用ch 扫描str,其中只有四类字符,其处理如下。 若ch=’(’, 源代码 头文件 #include"btree....
  • 如果有4个节点的话,那么上图1 的位置就会变成二叉树结构了。 上述就是这个树形结构的说明了。 将它解析为数组格式的话就要运用递归的方法了: //声明个变量用来存储结果 var res = []; ...
  • 之前我实现了通过二叉树的中序遍历顺序,加上前后序任意种遍历顺序,最后在内存中生成二叉树的方法(点我去看看)。今天我再实现种根据二叉树的数据及其对应的顺序存储下标值(从1开始),在内存中生成对应的...
  • 最长公共前缀 题目描述: 编写个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀,返回空字符串 “”。 算法: 横向+纵向扫描,for循环嵌套。第个for循环纵向扫描首个字符串的每位字符,第二个...
  • 数组和字符

    2020-01-07 14:01:25
    leetcode 724.寻找数组的中心索引 leetcode 747. 至少是其他数字两倍的最大数
  • 二叉树专题

    千次阅读 2016-07-16 13:47:04
    输入:数组二叉树层序遍历)、总和 输出:所有满足总和的路径 详细描述:首先给定个层次遍历的结果,然后重建二叉树,最后根据指定总格通过深度优先遍历得到所有路径。(也可以加入分支限界) 2.根据层序...
  • 树状数组主要是将数组分成段段并求和, 要真正理解透彻还是需要好好看看资料的, 其中与位运算相关的lowbit(x)特别有用, 另外就是更新与求和两个操作也是树状数组必须的, 复杂度都是O(lgn), 应该说时间上...
  • 将按层次遍历的方式输入的数组 构造成二叉树 将按先序遍历的方式输入的数组 构造成二叉树 将按中序遍历的方式输入的数组 构造成二叉树 将按后序遍历的方式输入的数组 构造成二叉树 根据前序遍历序列...
  • 输入leetcode测试用例类型字符,返回根节点指针。判断逻辑和leetcode一致,null结点无须额外输入null子结点,并且自动舍弃无效结点,例如输入[1,null,2,null,null,3],算法会自动舍弃结点3. 网上找的都是错的,...
  • 二叉树+++

    2021-09-12 23:26:26
    文章目录1、生成二叉树1.1由列表生成个二叉树:1.2由字符生成个二叉树2、遍历二叉树3、二叉树属性3.1 对称3.2 深度查询3.2节点数的统计3.3平衡3.4路径和4、 二叉树的操作5、祖先6、二叉搜索树 1、生成二叉树 ...
  • 用文件创建二叉树

    千次阅读 2019-01-07 18:34:04
    用文件创建二叉树 本次使用到的类有: fstream类 string类 #include"fstream"...第个把文件转化为数组,第二个把数组转化为二叉树。 文件转化为数组 在这里,我使用了结构体。 struct No...
  • 二叉树的序列化与反序列化思路1:BFS思路2:DFS知识点:数组转成队列(数组 -(Arrays.asList)-> 列表 -(构造器)->队列) 297. 二叉树的序列化与反序列化 题目链接:...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 25,695
精华内容 10,278
关键字:

给一串数组生成二叉树