首页 > 其他分享 >二叉树

二叉树

时间:2022-08-27 22:47:31浏览次数:43  
标签:return 节点 二叉树 null root public

1 树的结构

 

1.1 树的概念: 

树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。
有一个特殊的节点叫根节点,根节点没有前驱。
其余节点被分成互不相交的集合,每个节点又是一颗与树类似的子树,每颗子树只有一个前驱,但可以有0或多个子树。

 

1.2 概念:

 1 节点的度:一个节点含有的子树个数为该节点的度。

 2 树的度:一颗树的最大节点的度。

 3 叶子节点或终端节点:度为0的节点为叶节点。

 4 分支节点或非终端节点:度不为0的节点。

 5  双亲节点或父节点:若一个节点含有子节点这个节点为其的父节点。

 6 孩子节点或子节点: 一个节点含有子树的根节点为该节点的子节点。

 7 根节点:一棵树没有双亲节点(起始节点)。

 8 节点的层次:根为第一层,依次类推。

 9 树的高度或深度:节点的最大层次。

 

1.3 树的表现形式

     

 

 

2 二叉树

 

2.1 概念:

 

一棵二叉树是结点的一个有限集合,该集合或者为空,或者是由一个根节点加上两棵别称为左子树和右子树的二叉 树组成。   特点:1.每个节点最多有两颗子树度不能大于2。            2.二叉树的子树有左右之分,子树顺序不能颠倒,二叉树是有序树。   2.2 二叉树的基本形态:      从左到右依次为 空树,只有根节点的二叉树,只有左子树或者只有右子树的二叉树,左右子树都有的二叉树。  

 

2.3 满二叉树和完全二叉树

 

 1 满二叉树: 一个二叉树每层节点都为最大值,就是满二叉树,如果一个树层数为K,且节点数是2k-1,就是满二叉树。

 2 完全二叉树:对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称

 之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。   2.4二叉树的性质:   1 若根节点层数为1,则非空二叉树的第i层最多有2i-1个节点。(i>0) 2 只有根节点的二叉树的深度为1,深度为K的二叉树最大节点数2k-1。(k>0) 3  对任何一个二叉树,其叶节点个数为n0,度为2的非叶节点个数为n2,则n0=n2+1。 4 有n个节点的完全二叉树它的深度k为log2(n+1)    2k=n+1 5. 对于具有n个结点的完全二叉树,如果按照从上至下从左至右的顺序对所有节点从0开始编号,则对于序号为i 的结点有: 若i>0,双亲序号:(i-1)/2;i=0,i为根节点编号,无双亲节点 若2i+1<n,左孩子序号:2i+1,否则无左孩子 若2i+2<n,右孩子序号:2i+2,否则无右孩子     2.5二叉树的储存   二叉树的链式存储是通过一个个的节点引用起来的,常见有二叉和三叉的表示方法   二叉(孩子表示法)
class BTNode{
    public char val; //数据域
    public BTNode left; //左引用  左子树
    public BTNode right; //有引用 右子树

    public BTNode(char val) {
        this.val = val;
    }
}

 

  三叉(孩子双亲表示法)
class BTNode{
    public char val;  //数据域
    public BTNode left; //左子树
    public BTNode right; //右子树
    public BTNode parent;  //当前节点的根节点
    public BTNode(char val) {
        this.val = val;
    }
}

 

   2.6二叉树的基本操作   2.6.1二叉树的遍历   1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点--->根的左子树--->根的右子树。  2. 中序遍历(Inorder Traversal)——根的左子树--->根节点--->根的右子树。 3. 后序遍历(Postorder Traversal)——根的左子树--->根的右子树--->根节点。                                                                 二叉树练习题    
获取树中节点的个数
public int size3(TreeNode root){
       if (root==null)return 0;
       return size3(root.left)+size3(root.right)+1;
    }

 

获取叶子节点的个数
public int getLifeNodecount2(TreeNode root){
       if (root==null)return 0;
       if (root.left==null && root.right==null){
           return 1;
       }
       return getLifeNodecount2(root.left)+getLifeNodecount1(root.right);
    }

 获取K层节点的个数

 
 public int getLevelCount(TreeNode root,int k){
       if (root==null||k<=0){
           return 0;
       }if (k==1){
           return 1;
       }
       return getLevelCount(root.left,k-1)+getLevelCount(root.right,k-1);
    }

 获取二叉树的高度

  public int getHeight(TreeNode root){
        if (root==null){
            return 0;
        }
        int left =getHeight(root.left);
        int right =getHeight(root.right);
      return left<right?right+1:left+1;

 

 检测值为value的元素是否存在
public TreeNode ifLive1(TreeNode root,char val){
       if (root==null){
           return null;
       }
       if (root.val==val){
           return root;
       }
    TreeNode ret =ifLive(root.left,val);
       if (ret!=null){
           return ret;
       }
       ret=ifLive(root.right,val);
        if (ret!=null){
            return ret;
        }
        return null;
    }

 检测一颗二叉树是不是完全二叉树

boolean isCompleteTree(TreeNode root) {
        if (root == null) return false;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur != null) {
                queue.offer(cur.left);
                queue.offer(cur.right);
            } else {
                break;
            }
        }
        while (!queue.isEmpty()) {
            TreeNode tmp = queue.poll();
            if (tmp != null) {
                return false;
            }
            queue.poll();
        }
        return true;
    }

 

         

 

 

 

 

  

                       

 

标签:return,节点,二叉树,null,root,public
From: https://www.cnblogs.com/lbwboke/p/16619181.html

相关文章

  • 222.count-complete-tree-nodes 完全二叉树的节点个数
    遍历法遍历所有节点的方法,时间复杂度为\(O(n)\)classSolution{public:intcountNodes(TreeNode*root){if(root==nullptr)return0......
  • 101. 对称二叉树
    101.对称二叉树给你一个二叉树的根节点root,检查它是否轴对称。 示例1:输入:root=[1,2,2,3,4,4,3]输出:true示例2:输入:root=[1,2,2,null,3,null,3]输出:fa......
  • leetcode144:二叉树的前序遍历
    packagecom.mxnet;importjava.util.ArrayList;importjava.util.List;publicclassSolution144{publicstaticvoidmain(String[]args){}/**......
  • leetcode226-翻转二叉树
    翻转二叉树递归classSolution{publicTreeNodeinvertTree(TreeNoderoot){if(root==null)returnroot;TreeNodel=invertTree(roo......
  • leetcode222-完全二叉树的节点个数
    完全二叉树的节点个数递归classSolution{publicintcountNodes(TreeNoderoot){if(root==null)return0;returncountNodes(root.le......
  • 平衡二叉树(AVL)的实现
    平衡二叉树概念平衡二叉排序树(BalancedBinaryTree),因由前苏联数学家Adelson-Velskii和Landis于1962年首先提出的,所以又称为AVL树。平衡二叉树是一种特殊的二叉排序......
  • 二叉树的结构
    https://www.acwing.com/problem/content/description/4274/#include<bits/stdc++.h>#include<string.h>usingnamespacestd;constintN=1010;intpost[N],in[N......
  • 判断是不是平衡二叉树
    staticintflag=0;publicbooleanisBalanced(TreeNoderoot){flag=0;travel12(root);if(flag==1){returnfalse;......
  • leetcode 热题100刷题-二叉树的中序遍历
    题题号:94题目:二叉树的中序遍历难度:简单链接:https://leetcode.cn/problems/binary-tree-inorder-traversal/2022/08/23答案算法思路  本题在课程中是学过的。  ......
  • 2022-8-22 剑指offer-优先队列-每日一题-二叉树-搜索/递归
    剑指OfferII060.出现频率最高的k个数字难度中等36收藏分享切换为英文接收动态反馈给定一个整数数组 nums 和一个整数 k ,请返回其中出现频率前 k 高的元......