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