近些日子在lintCode上做了两道的关于二叉查找树的

作者:编程

Description

Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1...n.

  二叉查找树在数据结构中读书,可是感到本人学的可怜水,近些日子在lintCode上做了两道的有关二叉查找树的题,以为有相比较记录下来,就当是加强记念!

  • 二叉树是 n (n >= 0)个节点的一定量集结,该会集也许为空集或然由一个根节点和两棵互不相交的、分别名叫根节点的左子树和右子树的二叉树组成

Example

Given n = 3, your program should return all 5 unique BST's shown below. 1         3     3      2      1         /     /      /          3     2     1      1   3      2  /     /                         2     1         2                 3

1.二叉查找树I

必赢 1图1

思路

  • 回溯
  • 对每三个点,递归生成它的左子树和右子树
必赢,题意:
给出 n,问由 1...n 为节点组成的不同的二叉查找树有多少种?
  • 折半规律很符合营为二叉树建立模型

代码

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode : val, left, right {} * }; */class Solution {public:    vector<TreeNode*> generateTrees {        vector<TreeNode*> res;        if return res;        res = helper;                return res;    }        vector<TreeNode*> helper(int start, int end){        vector<TreeNode*> res;        if(start > end){            res.push_back;        }        else if(start == end){            TreeNode *tmp = new TreeNode;            res.push_back;        }        else{            for(int i = start; i <= end; ++i){                vector<TreeNode*> left = helper(start, i - 1);                vector<TreeNode*> right = helper(i + 1, end);                                for(int j = 0; j < left.size{                    for(int k = 0; k < right.size{                        TreeNode *root = new TreeNode;                        root->left = left[j];                        root->right = right[k];                        res.push_back;                    }                }            }        }                return res;    }};
样例:
给出n = 3,生成所有5种不同形态的二叉查找树:

1         3     3       2    1
        /     /       /     
  3     2     1       1   3    2
 /     /                       
2     1         2                3

  那个是数据结构中的二叉树中十分大规模。这么些是拔尖Carter兰数的样例

必赢 2图2

(1).Carter兰数

  令h(0)=1,h(1)=1,卡特兰数满意递归式:h(n) = h(0)h(n-1) + h(1)h(n-2)

  • ... + h(n-1)*h(0) (n>=2);该递推公式为:h(n) = C(2n,n)/(n+1),n=0,1,2,3,...
  • 二叉树特点

    • 每一种节点最多有两棵子树
    • 左子树和右子树是有各种的,次序不能够随意颠倒
    • 便是树中某节点独有一棵子树也要分别它是左子树照旧右子树
  • 奇怪二叉树

    • 斜树:全部的节点都唯有左子树的二叉树叫做左斜树,反之右斜树
    • 满二叉树:全部支行节点都存在左子树和右子树,并且存有叶子都在一样层上

    必赢 3满二叉树

    • 一同二叉树:叶子节点只可以出现在最下两层,最下层的叶子一定集中在左部接二连三地方,倒数二层,若有叶子节点,一定都在右部一连地点,若是节点度为 1,则该节点唯有左孩子,既不设有右子树景况,同样节点数的二叉树,完全二叉树的深浅最小

    必赢 4一心二叉树

(2).为何二叉查找树知足Carter兰数呢?

  我们那样来借使
  当唯有四个节点时,明显唯有一种情景,大家于是假若f(1) = 1;
  当只有七个节点时,怎么来思索?大家原则性二个节点,另三个节点照旧放在左子树,要么放在右子树,所以分为二种处境,f(2) = f(1) + f(1)。当中的f(1),大家如此来精晓,第3个f(1)实际上是f(1) * f(0)(这里的f(0)杰出1,为啥f(0)等于1吧?因为没有节点也唯有一种情状啊!),表暗暗表示思是,左子树独有一个节点,右子树没有节点,而第二个f(1)表示为f(0) * f(1),表示的是左子树没有节点,右子树只有三个节点。
  当只有几个也许三个节点以上时,我们只要为n, f(n)的情景就分为左子树为0何况右子树为n - 1(因为有贰个节点被一定了,所以独有n - 1个节点),左子树为1同期右子树为n - 2,左子树为2何况右子树为 n - 3等等...然后大家就能够脱离公式:f(n) = f(0) * f(n - 1) + f(1) * f(n - 2) + ...... + f(n - 2) * f(1) + f(n - 1) * f(1)。

二叉树性质1

  • 在二叉树的第 i 层上至多有 2的i-1次方个节点

(3).动态规划

  依照上边包车型地铁递归公式,大家得以写出动态规划的代码

public int numTrees(int n) {

        int nums[] = new int[n + 1];
        nums[0] = 1;
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j < i; j++) {
                nums[i] += nums[j] * nums[i - 1- j];
            }
        }
        return nums[n];
    }

二叉树性质2

  • 纵深为 k 的二叉树至多有 2的k次方-1个节点

2.二叉查找树II

二叉树性质3

  • 假使端节点数为 n0,度为 2 的节点数为 n2,则 n0=n2+1
  • 终极节点其实正是卡片节点数,而一棵二叉树除了叶子节点外,剩下的正是度为 1 或 2 的节点数了,大家设 n1 为度是 1 的节点数,则树节点总量是 n=n0+n1+n2
  • 图5 度为2的节点数 n2 = 4,则叶子节点数 n0 = 4+1,树节点总量 n=4+1+5

必赢 5图5

  • 有着 n 个节点的一丝一毫二叉树的纵深为 [log2n]+1 ([x] 表示不超过 x 的最大整数)
  • 如 图1 有 10 个节点,则深度 4 = log 以2为底10的对数 + 1 = 3 + 1
  • 对此一棵有 n 个节点的一心二叉树(其深度为 [log2n]+1)的节点按层序编号(从第 1 层到第 [log2n]+1 层,每层从左到右),对任一节点 i 有:
    • 假若 i =1,则节点 i 是二叉树的根,则无大人,如若 i > 1,则其父母是节点 [i/2](下图节点7,它的父母亲便是 [7/2] = 3)
    • 只要 2i > n,则节点 i 无左子树(节点 i 为叶子节点),不然其左子树是节点 2i,(下图节点6,因为 2*6=12 当先了节点总的数量 10,所以它无左子树,而节点5 因为十三分10,所以它的左子树节点为 10)
    • 假若 2i + 1 > n,则节点 i 无右子树,不然其右子树是节点 2i+1,(下图节点5,因为 2*5+1=11 大于节点总的数量10,所以它无右子树,因为节点2 低于 10,所以它的右子树节点为 7)

必赢 6图6

题意:
给出n,生成所有由1...n为节点组成的不同的二叉查找树

二叉树顺序存款和储蓄

  • 二叉树的顺序存款和储蓄结构正是用一维数组存款和储蓄二叉树中的节点,并且节点的囤积地点,也正是数组的下标要能展示节点之间的逻辑关系,譬喻老人与子节点、兄弟节点的涉嫌

必赢 7图7

  • 对此平时的二叉树,层序编号不能够影响逻辑关系,可是可以将其按完全二叉树编号,把不设有的节点设置为 "^"

必赢 8图8

  • 思量一种极端意况,一棵深度为 k 的右斜树,它独有 k 个节点,却要分配 2的k次方-1 个存储单元空间,那分明是对存款和储蓄空间的萧疏,所以顺序存款和储蓄结构相似只用于完全二叉树

必赢 9图9

样例:
给出n = 3,生成所有5种不同形态的二叉查找树:

1         3     3       2    1
        /     /       /     
  3     2     1       1   3    2
 /     /                       
2     1         2                3

  说真的,那道题真的不晓得怎么写,标签上写的是深搜,不过就是不领会怎么写出来,因为在此之前只写过深搜的搜索题,未有做过深搜的生成类型题!
  最终作者在网络上找的外人的代码,然后精通了,也不知晓明白的是不是科学。
  先来拜望代码

public List<TreeNode> generateTrees(int n) {
        List<TreeNode> list = new ArrayList<>();
        if(n < 0) {
            return null;
        }
        list = createTree(1, n);
        return list;
    }

    private List<TreeNode> createTree(int start, int end) {
        List<TreeNode> list = new ArrayList<>();
        if (start > end) {
            list.add(null);
            return list;
        }
        for (int i = start; i <= end; i++) {
            List<TreeNode> left = createTree(start, i - 1);
            List<TreeNode> right = createTree(i + 1, end);
            for (int j = 0; j < left.size(); j++) {
                for (int k = 0; k < right.size(); k++) {
                    TreeNode node = new TreeNode(i);
                    node.left = left.get(j);
                    node.right = right.get(k);
                    list.add(node);
                }
            }
        }
        return list;
    }

  小编是这么敞亮的:举例n个节点,它有分为n - 1种意况,跟上边的Carter兰数一样,然后我们独家组织当前节点的左子树和右子树,通过递回来构造。由于有n

  • 1种景况,所以得有四个循环来组织。

二叉链表

  • 二叉树种种节点最多有多个子节点,所感觉它设计三个数据域与两个指针域
lchild data rchild
  • 二叉树的遍历是指从根节点触发,遵照某种次序依次拜候二叉树中具备的节点,使得各类节点都被访谈三回且仅被访谈一遍

1. 前序遍历

  • 先拜会根节点,然后前序遍历左子树,再前序遍历右子树,遍历顺序为:ABDGHCEIF

必赢 10avtTz.png

2. 中序遍历

  • 中序遍历根节点的左子树,然后访问根节点,最终中序遍历右子树,遍历顺序为:GDHBAEICF

必赢 11av1Sa.png

3. 承袭遍历

  • 从左到右先叶子后节点的不二等秘书籍遍历左右子树,最后访谈根节点,遍历顺序为:GHDBIEFCA

必赢 12av64S.png

4. 层序遍历

  • 从树的根节点开首访谈,从上而下逐层遍历,在同样层中,从左到右顺序对节点各个访问,遍历顺序为:ABCDEFGHI

必赢 13avKP2.png

import java.util.ArrayList;import java.util.List;public class BinTree { private BinTree root; // 根节点 private BinTree lChild; // 左子树 private BinTree rChild; // 右子树 private Object data; // 数据域 private List<BinTree> datas; // 存储的所有节点 public BinTree(BinTree lChild, BinTree rChild, Object data) { this.lChild = lChild; this.rChild = rChild; this.data = data; } public BinTree(Object data) { this.data = data; } public BinTree() { } public void createTree(Object[] objs) { datas = new ArrayList<>(); for (Object object : objs) { datas.add(new BinTree; } root = datas.get;// 将第一个节点作为根节点 for (int i = 0; i < datas.size() / 2; i++) { datas.get.lChild = datas.get(i * 2 + 1); // 设置左子树 if ((i * 2 + 2) < datas.size { // 避免越界 datas.get.rChild = datas.get(i * 2 + 2); // 设置右子树 } } } // 前序遍历:从根节点开始,先遍历左子树,再遍历右子树 public void preorder(BinTree root) { if (root != null) { System.out.println(root.getData; preorder(root.lChild); preorder(root.rChild); } } // 中序遍历:从根节点先遍历左子树,在根节点,最后右子树 public void inorder(BinTree root) { if (root != null) { inorder(root.lChild); System.out.println(root.getData; inorder(root.rChild); } } // 后续遍历:从左到右最后再根节点 public void afterorder(BinTree root){ if(root != null){ afterorder(root.lChild); afterorder(root.rChild); System.out.println(root.getData; } } public Object getData() { return data; } public BinTree getRoot() { return root; } public static void main(String[] args) { BinTree binTree = new BinTree(); Object[] objects = new Object[]{1, 2, 3, 4, 5, 6, 7, 8,9,10}; binTree.createTree; binTree.afterorder(binTree.getRoot; }}

本文由必赢娱乐_官网(welcome!)发布,转载请注明来源

关键词: