算法与数据结构学习笔记(一)-查找二叉树

  普通树:https://baike.baidu.com/item/%E6%A0%91%E7%BB%93%E6%9E%84/3399688?fr=aladdin

  二叉树:https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%A0%91

 

  查找二叉树又称搜索二叉树,是一种特殊的二叉树(其实也可以叫被限制的二叉树)。普通的树是即是一种非线性的数据结构,由很多的节点按照父子关系相互关联。对于任意一个节点最多只有2个子节点的树就称为二叉树

  重点!!对于任意一个节点,左子树任意节点的值都小于该节点的值且右子树任意节点的值都大于该节点的值,对于瞒住这样条件的二叉树即为查找二叉树

二.性质与作用 性质:

  性质1:在二叉树的第i层上至多有2i-1个结点(i≥1)。

  性质2:深度为k的二叉树最多有2k-1个结点(k≥1)。

  性质3:一棵二叉树的叶子结点数为n0,度为2的结点数为n2,则n0 = n2 + 1。

  证:结点总数n = n0 + n1 + n2。设B为分支总数,因为除根节点外,其余结点都有一个分支进入,所以n = B + 1。又因为分支是由度为1或2的结点射出,所以B = n1 + 2n2。综上:n = n0 + n1 + n2 = B + 1 = n1 + 2n2 + 1,得出:n0 = n2 + 1。

  性质4:具有n个结点的完全二叉树的深度为floor(log2n) + 1 。

  性质5:如果对一棵有n个结点的完全二叉树(其深度为floor(log2n) + 1 )的结点按层序编号,则对任一结点i(1≤i≤n)有:

    (1) 如果i = 1,则结点i是二叉树的根,无双亲;如果i > 1,则其双亲PARENT(i)是结点 floor((i)/2)。

    (2)如果2i > n,则结点i无左孩子;否则其左孩子LCHILD(i)是结点2i。

    (3)如果2i + 1 > n,则结点i无右孩子;否则其右孩子RCHILD(i)是结点2i + 1。

对于上面的这些性质,我也没去验证,网上Copy的

作用:

  其他作用不清楚,用来存储是没有问题的。顾名思义,对于一个构建完成的查找二叉树,根据定义可知,从跟节点开始,与查找值进行对比,相等则查找成功,大于则继续查找右子树,小于则继续查找左子树。

  而对于查找二叉树,它的时间复杂度为:O(Log2n)到O(n)。原因:因为当二叉树为非常平衡的二叉树(平衡二叉树)时复杂度为O(Log2n)。但是如果二叉树构建得最糟糕时将退化为线性结构。复杂度就为O(n)

              

算法与数据结构学习笔记(一)-查找二叉树

 

 

 

 三.代码实现   (1)建立实体

    首先我们需要两个实体模型来描述该数据结构 1.节点 2.树

      

public class TreeNode { private int value; public int childrenNum = 0; private TreeNode leftNode; private TreeNode rightNode; public TreeNode(int value) { this.value = value; } //getter setter 省略... } 

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wpwszj.html