赞
踩
二叉树的概念
二叉树(Binary Tree)是n (n>=0)个节点的有限集合,该集合可以为空集(称为空二叉树),或者由一个根节点和两个互不相交的,分别称为根节点的左子树和右子树的二叉树组成。
二叉树的特点:
1、每个节点最多有两棵子树,即不存在超过度为2的节点。
2、二叉树的子树有左右之分,且左右不能颠倒。
如下图所示,下图就是一个二叉树
1. 满二叉树:一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为K,且结点总数是(2^k) -1 ,则它就是满二叉树。
如下图所示
2.完全二叉树:完全二叉树是由满二叉树引出的。满二叉树要求每一层的节点数都达到最大值,完全二叉树仅要求除最后一层外的节点数达到最大值,也就是说最后一层可以不满。我们可以把满二叉树看错特殊的完全二叉树。
如下图所示
1.若规定根节点的层数为1,则一棵非空二叉树的第i层上最多有2^(i-1) 个结点。
2.若规定根节点的层数为1,则深度为h的二叉树的最大结点数是2^h- 1。
3.任何一棵二叉树, 如果度为0其叶结点个数为 n0, 度为2的分支结点个数为 n2,则有n0=n2+1
4.若规定根节点的层数为1,具有n个结点的满二叉树的深度,h=Log2(n+1)
5.对于具有n个结点的完全二叉树,如果按照从上至下从左至右的数组顺序对所有节点从0开始编号,则对于序号为i的结点有:
(1)若i>0,i位置节点的双亲序号:(i-1)/2;i=0,i为根节点编号,无双亲节点
(2)若2i+1<n,左孩子序号:2i+1,2i+1>=n否则无左孩子
(3)若2i+2<n,右孩子序号:2i+2,2i+2>=n否则无右孩子
- static class TreeNode {
- public char val;
- public TreeNode left;//左孩子的引用
- public TreeNode right;//右孩子的引用
-
- public TreeNode(char val) {
- this.val = val;
- }
- }
- public TreeNode createTree() {
- TreeNode A=new TreeNode('A');
- TreeNode B=new TreeNode('B');
- TreeNode C=new TreeNode('C');
- TreeNode D=new TreeNode('D');
- TreeNode E=new TreeNode('E');
- TreeNode F=new TreeNode('F');
- A.left=B;
- A.right=D;
- B.left=C;
- D.left=E;
- D.right=F;
- return A;
- }
- public void preOrder(TreeNode root) {
- if (root==null){
- return;
- }
- System.out.println(root.val);
- preOrder(root.left);
- preOrder(root.right);
- }
- public void inOrder(TreeNode root) {
- if (root==null){
- return;
- }
- inOrder(root.left);
- System.out.println(root.val);
- inOrder(root.right);
- }
- public void postOrder(TreeNode root) {
- if (root==null){
- return;
- }
- postOrder(root.left);
- postOrder(root.right);
- System.out.println(root.val);
-
- }
- public static int nodeSize;//定义一个全局变量方便保存结点个数
- public void size(TreeNode root) {
- if (root==null){
- return;
- }
- nodeSize++;//不是空就++
- size(root.left);
- size(root.right);
- }
- int size2(TreeNode root) {
- if (root==null){
- return 0;
- }
- int leftSize=size2(root.left);//先求左子树的结点个数
- int rightSize=size2(root.left);//然后求右子树结点的个数
- return leftSize+rightSize+1;//返回左子树和右子树加上1
- }
也许有的小伙伴不明白为什么要加一,加一就是加上本根结点
遍历思路跟上面一样,定义全局变量,满足条件就++,缺点就是只能求一棵树,两棵树就不好求,建议大家用子问题的思路
- public static int leafSize = 0;//和上面一样,方便保存叶子结点个数
- void getLeafNodeCount1(TreeNode root) {
- if (root==null){
- return;
- }
- if (root.left==null&&root.right==null){//满足if里面的条件就说明是叶子结点
- leafSize++;
- }
- getLeafNodeCount1(root.left);
- getLeafNodeCount1(root.right);
- }
如下代码,满足条件就返回1,否则返回零,通过左子树加右子树累加起来,最后返回总数目
- int getLeafNodeCount2(TreeNode root) {
- if (root==null){
- return 0;
- }
- if (root.left==null&&root.right==null){
- return 1;
- }
- int l=getLeafNodeCount2(root.left);
- int r=getLeafNodeCount2(root.right);
- return l+r;
- }
利用一直递归k-1求得左子树和右子树的本层结点个数,最后返回它们的和
- int getKLevelNodeCount(TreeNode root, int k) {
- if (root==null){
- return 0;
- }
- if (k==1){
- return 1;
- }
-
- int l=getKLevelNodeCount(root.left,k-1);
- int r=getKLevelNodeCount(root.right,k-1);
-
- return l+r;
- }
利用递归方法返回左右子树最大高度加上根节点本身
- int getHeight(TreeNode root) {
- if (root==null){
- return 0;
- }
- int leftHigh=getHeight(root.left);
- int rightHigh=getHeight(root.right);
- return Math.max(leftHigh,rightHigh)+1;
- }
- TreeNode find(TreeNode root, char val) {
- if(root == null) {
- return null;
- }
- if(root.val == val) {
- return root;
- }
- TreeNode ret1 = find(root.left,val);
- if(ret1 != null) {
- return ret1;//如果左子树不为空,就说明找到了,返回
- }
- TreeNode ret2 = find(root.left,val);
- if(ret2 != null) {
- return ret2;//如果右子树不为空,就说明找到了,返回
- }
- return null;
- }
- boolean isCompleteTree(TreeNode root) {
- if(root == null) {
- return true;
- }
- Queue<TreeNode> qu = new LinkedList<>();
- qu.offer(root);
- while(!qu.isEmpty()) {
- TreeNode node = qu.poll();
- if(node != null) {
- qu.offer(node.left);
- qu.offer(node.right);
- } else {
- break;
- }
- }
- if(!qu.isEmpty()) {
- TreeNode node = qu.poll();
- if(node != null) {
- return false;
- }
- }
- return true;
- }
本期知识点就到这里,关注我,下期会给大家带来关于二叉树的力扣等练习题
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。