精华内容
下载资源
问答
  • 创建二叉树

    2019-09-27 15:21:23
    问题 创建一个二叉树 二叉树有限多个节点的集合,这个...创建二叉树: 创建节点 再创建节点之间的关系 Python代码示例 # !/usr/bin/env python # -*-encoding: utf-8-*- # author:LiYanwei # version:0.1 class T...

    问题

    创建一个二叉树

    二叉树有限多个节点的集合,这个集合可能是:

    1. 空集
    2. 由一个根节点,和两棵互不相交的,分别称作左子树和右子树的二叉树组成

    创建二叉树:

    1. 创建节点
    2. 再创建节点之间的关系

    Python代码示例

    # !/usr/bin/env python
    # -*-encoding: utf-8-*-
    # author:LiYanwei
    # version:0.1
    
    class TreeNode(object):
        def __init__ (self, data, left = None, right = None):
            self.data = data
            self.left = left
            self.right = right
    
        def __str__(self):
            return str(self.data)
    # 节点
    A = TreeNode('A')
    B = TreeNode('B')
    C = TreeNode('C')
    D = TreeNode('D')
    # 节点间的关系
    A.left = B
    A.right = C
    B.right = D
    
    print B.right

    转载于:https://www.cnblogs.com/Py00/p/7726759.html

    展开全文
  • Java创建二叉树并遍历的代码public class BinaryTree {private Node root;/**** 内部节点类* @author yhh*/private class Node{private Node left;private Node right;private int data;public Node(int data){this....

    Java创建二叉树并遍历的代码

    public class BinaryTree {

    private Node root;

    /**

    *

    * 内部节点类

    * @author yhh

    */

    private class Node{

    private Node left;

    private Node right;

    private int data;

    public Node(int data){

    this.left = null;

    this.right = null;

    this.data = data;

    }

    }

    public BinaryTree(){

    root = null;

    }

    /**

    * 递归创建二叉树

    * @param node

    * @param data

    */

    public void buildTree(Node node,int data){

    if(root == null){

    root = new Node(data);

    }else{

    if(data < node.data){

    if(node.left == null){

    node.left = new Node(data);

    }else{

    buildTree(node.left,data);

    }

    }else{

    if(node.right == null){

    node.right = new Node(data);

    }else{

    buildTree(node.right,data);

    }

    }

    }

    }

    /**

    * 前序遍历

    * @param node

    */

    public void preOrder(Node node){

    if(node != null){

    System.out.println(node.data);

    preOrder(node.left);

    preOrder(node.right);

    }

    }

    /**

    * 中序遍历

    * @param node

    */

    public void inOrder(Node node){

    if(node != null){

    inOrder(node.left);

    System.out.println(node.data);

    inOrder(node.right);

    }

    }

    /**

    * 后序遍历

    * @param node

    */

    public void postOrder(Node node){

    if(node != null){

    postOrder(node.left);

    postOrder(node.right);

    System.out.println(node.data);

    }

    }

    public static void main(String[] args) {

    int[] a = {2,4,12,45,21,6,111};

    BinaryTree bTree = new BinaryTree();

    for (int i = 0; i < a.length; i++) {

    bTree.buildTree(bTree.root, a[i]);

    }

    bTree.preOrder(bTree.root);

    bTree.inOrder(bTree.root);

    bTree.postOrder(bTree.root);

    }

    }

    展开全文
  • 前序中序创建二叉树: preOrder:{1,2,4,7,3,5,6,8} inOrder:{4,7,2,1,5,3,8,6}

    前序中序创建二叉树:
    preOrder:{1,2,4,7,3,5,6,8}
    inOrder:{4,7,2,1,5,3,8,6}

    • 找到中序中和先序相同的节点(i=3)、leftLen=i、rightLen=len-leftLen-1;
    • 将先序和中序分为两半,递归调用:(preS+1,inS,leftLen,preorder,inorder) 和 (preS+leften+1,ins+leftlen+1,rightlen.preorder,inorder)

    递归实现:

    public static TreeNode createTree(int preS,int inS,int length,int[]preorder,int[]inorder){
            if (preorder == null || preorder.length ==0){
                return null;
            }
            TreeNode node = new TreeNode(preorder[preS]);
            if(length ==1 && preorder[preS] == inorder[inS])
                return node;
            int i = 0;
            //找到分界点
            while (i <=length-1 && preorder[preS]!= inorder[inS+i])
                i++;
            //左半边长度
            int leftLen = i;
            //右半边长度
            int rightLen = length-leftLen-1;
            if(leftLen>=1){
                node.left=createTree(preS+1,inS,leftLen,preorder,inorder);
            }
            if(rightLen>=1){
                node.right=createTree(preS+leftLen+1,inS+leftLen+1,rightLen,preorder,inorder);
            }
            return node;
        }

    中序后序创建二叉树:
    inOrder:{4,7,2,1,5,3,8,6}
    postOrder={7,4,2,5,8,6,3,1}

    • 找到中序中和后序相同的节点(i=3);
    • 将中和后序分为两半,递归调用:(inS,postE-rightLen-1,leftLen,inorder,postorder)、createTree(inS+leftLen+1,postE-1,rightLen,inorder,postorder)

    递归实现:

    public  TreeNode createTree(int inS,int postE,int length,int[]inorder,int[]postorder){
            if (inorder == null || inorder.length ==0){
                return null;
            }
            TreeNode node = new TreeNode(postorder[postE]);
            if(length ==1 && inorder[inS] == postorder[postE])
                return node;
            int i = 0;
            //找到分界点
            while (i <=length-1 && postorder[postE]!= inorder[inS+i])
                i++;
            //左半边长度
            int leftLen = i;
            //右半边长度
            int rightLen = length-leftLen-1;
            if(leftLen>=1){
                node.left=createTree(inS,postE-rightLen-1,leftLen,inorder,postorder);
            }
            if(rightLen>=1){
                node.right=createTree(inS+leftLen+1,postE-1,rightLen,inorder,postorder);
            }
            return node;
        }
    展开全文
  • Python创建二叉树

    2021-03-28 18:54:35
    Python 创建二叉树前言二叉树节点定义递归构建二叉树 前言 本文的内容是数据结构中二叉树部分最基础的,之所以写一下主要是为了方便刷题的时候,能够在自己电脑上很快的使用这种小的demo进行复杂的练习。 二叉树节点...

    前言

    本文的内容是数据结构中二叉树部分最基础的,之所以写一下主要是为了方便刷题的时候,能够在自己电脑上很快的使用这种小的demo进行复杂的练习。

    二叉树节点定义

    二叉树的节点定义如下:

    class TreeNode():#二叉树节点
        def __init__(self,val,lchild=None,rchild=None):
            self.val=val		#二叉树的节点值
            self.lchild=lchild		#左孩子
            self.rchild=rchild		#右孩子
    

    递归构建二叉树

    本文使用的前序递归构建的方法(其余顺序读者自行变化,本文主要意在如何快速构建能够执行的二叉树)
    例如,我们想构建一个如下图所示的树(其前序遍历结果为:abcde):

    a
    b
    e
    c
    d

    这里我们需要使用到扩展的二叉树,也就是要告诉计算机什么是叶结点,什么是空节点,否侧无法分辨左右节点。例如先序遍历的顺序为"abcde",扩展的二叉树前序序列为:“abc##d##e##”,#代表此处节点为None,如下图:

    a
    b
    e
    c
    None
    None
    d
    None
    None
    None
    None

    既然是使用递归的方法构建二叉树,主要需要理解递归的过程,这种思路将在之后的很多地方用的到。
    要知道如何递归的构建二叉树,我们不能纠结于递归每一层到底干了什么,这样就会一直纠结下去(所有的递归问题都一样)。我们需要注意的是:

    1. 在我们的任务中,终止条件是什么?
    2. 在我们的任务中,本次递归要干嘛?
    3. 在我们的任务中,本次递归要返回给上一次递归的是啥?

    在递归构建二叉树的任务中,我们要做到不纠结于每一层,而是只关注该层在做什么,这样,对于下图左侧的树,我们就可以看作为右侧的树,它只有自己a (a),左子树B (bcd)和右子树C (e)。

    a
    b
    e
    c
    d
    a
    B
    C

    这样我们需要注意的那三个问题的回答自然就有了(做递归问题,心中要想着怎么回答这三个问题):

    1. 在我们的任务中,终止条件是什么?
      [给我们的字符用完,也就不需要再创建节点了]
    2. 在我们的任务中,本次递归要干嘛?
      [本次递归要创建三个节点,一个根节点,一个左节点,一个右节点]
    3. 在我们的任务中,本次递归要返回给上一次递归的是啥?
      [当然是返回一个本层构造好的树的根节点]

    理解了上述三个问题的回答,递归的代码自然可以写出:

    def Creat_Tree(Root,val):
        if len(vals)==0:#终止条件:val用完了
            return Root
        if vals[0]!='#':#本层需要干的就是构建Root、Root.lchild、Root.rchild三个节点。
            Root = TreeNode(vals[0])
            vals.pop(0)
            Root.lchild = Creat_Tree(Root.lchild,val)
            Root.rchild = Creat_Tree(Root.rchild,val)
            return Root#本次递归要返回给上一次的本层构造好的树的根节点
        else:
            Root=None
            vals.pop(0)
            return Root#本次递归要返回给上一次的本层构造好的树的根节点
    

    看懂了上述内容,构建一棵我们想象的二叉树就很简单了,只要输入一个我们心目中前序遍历扩展的二叉树序列即可:

    if __name__ == '__main__':
        Root = None
        strs="abc##d##e##"#前序遍历扩展的二叉树序列
        vals = list(strs)
        Roots=Creat_Tree(Root,vals)#Roots就是我们要的二叉树的根节点。
    
    展开全文
  • 1.广义表创建二叉树 比如:A(B(,G),C(D(F),E)) 2.二叉树输出广义表
  • 创建二叉树,创建节点,再创建节点之间的关系 Python代码示例 # !/usr/bin/env python # -*-encoding: utf-8-*- # author:LiYanwei # version:0.1 class TreeNode(object): def __init__ (self, data, left = ...
  • 递归的方式创建二叉树
  • Java创建二叉树

    千次阅读 2014-07-15 14:09:42
    Java创建二叉树
  • 递归创建二叉树

    千次阅读 2018-10-22 17:42:30
    本文在这里采用递归方法创建二叉树,并且叙述有关二叉树三种遍历方式以及求有关节点的相关问题等。 首先定义一个有关二叉树的结构体,结构体中包含整型的data,以及结构体类型的左右子树left和right。然后是创建...
  • 二叉树的值保存在数组中,以0作为分隔,数字0表示空节点,数组public static final int[] TREE_VALUE = new int[]{1,2,3,0,4,5,0,0,6,0,0,7,0,0,8,0,9,10,0,0,0};表示的二叉树是:/*** 维护构建二叉树的值和值索引*/...
  • 二叉树总结(创建二叉树) 根据前序遍历和中序遍历创建二叉树(注意根据前、中、后序列创建唯一二叉树的时候,一定要有两个遍历序列,且其中一个必须为中序。 我们先定义二叉树的节点结构,一般包含左孩子,右孩子...
  • 动态创建二叉树

    2020-12-06 19:15:31
    #include <iostream> using namespace std; typedef struct _BinaryTree{ ...//create 先序动态创建二叉树 void CreateBitnaryTree(BTreeNode **pNode) { char ch; cin >> ch; if (ch == '#') {
  • 先序创建二叉树

    2020-02-20 09:58:24
    先序序列创建二叉树 #include<iostream> using namespace std; typedef struct Node{ char data; struct Node *lchild,*rchild; }Node,*Lnode; typedef struct LinkNode { Node data; struct LinkNode ...

空空如也

空空如也

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

创建二叉树