企业官网建设流程全解析

一.了解二叉树

1.1二叉树是什么

二叉树与之前我们学习的链表,顺序表不同,从这一章可能要上 强度了,之前我们学都都是线性结构;
而二叉树则是非线性结构;
== 说个比喻,我们打游戏时,想要进入下一个副本就必须将前一个副本打完,一个接一个,按顺序写,这就是线性结构,都是连在一起的,而非线性结构就是你可以选择分支,打完一个副本后,你可以自己选择岔路口,不一定要按顺序,想先打左边的副本BOSS可以,右边的副本BOSS也可以==
自然界的二叉树:

这是我在网上找的图,大自然确实神奇

二.二叉树基本知识

2.1二叉树基本概念

1)节点的度:节点很容易理解,他的度就是他的下面有多少个子树!

A的度为2,B,C

2)树的度

这个二叉树的度:3

3)叶子节点为:5 D,F,G,H,I

4)父节点:4 A,B,C,E

5)子节点 : 父节点的子树的根节点

6)根节点:A

7)节点层次:4,根节点为第一层

8)树的高度:节点最大层次

…

2.2两种二叉树

①满二叉树

满二叉树是节点最多的一种二叉树

②完全二叉树

这个没法说出准确的定义;只能说二叉树按层从坐到右右子树出现之前必须有左子树

这是一个完全二叉树,但如果把第四层的变为右子树就是错的

这就不是完全二叉树

1.3二叉树的模拟

二叉树有着左右子树;

publicstaticNodeTreeDemo(){NodeA=newNode("A");NodeB=newNode("B");NodeC=newNode("C");NodeD=newNode("D");NodeE=newNode("E");NodeF=newNode("F");NodeG=newNode("G");NodeH=newNode("A");A.left=B;A.right=C;B.left=D;B.right=E;C.left=F;C.right=G;E.left=H;returnA;}

二叉树的四种遍历

2.1先序遍历

1)先根节点
2)遍历左子树
3)遍历右边树
如果为空,达到界限;
这个的先序遍历: A B D E H C F G

publicvoidpreorder(Noderoot){if(root==null){return;}System.out.print(root.val+" ");preorder(root.left);preorder(root.right);}

验证:

publicstaticvoidmain(String[]args){Noderoot=TreeDemo();preorder(root);}

2.2中序遍历

1)遍历左子树
2)根节点
3)遍历右边树
如果为空,达到界限;
这个的先序遍历: D B H E A F C G
验证:

publicstaticvoidmain(String[]args){Noderoot=TreeDemo();// preorder(root);// System.out.println();inOrder(root);}

2.3后序遍历

1)遍历左子树;
2)遍历右子树
3)根节点

publicstaticvoidpostOrder(Noderoot){if(root==null){return;}postOrder(root.left);postOrder(root.right);System.out.print(root.val+" ");}

遍历顺序: D H E B F G C A

2.4层序遍历

1)首先头节点入队列;
2)判断Queue是否为空,然后出栈
3) 判断左节点不为空,入栈;
4)判断右节点不为空,入栈;

publicstaticvoidlevelOrder(Noderoot){if(root==null){return;}Queue<Node>queue=newLinkedList<>();queue.offer(root);while(!queue.isEmpty()){Nodecur=queue.poll();System.out.print(cur.val+" ");if(cur.left!=null){queue.offer(cur.left);}if(cur.right!=null){queue.offer(cur.right);}}}

三.二叉树基本操作

3.1获取数中节点个数

1)节点个数:根节点个数+左子树节点个数+右子树节点个数;
2)递归界限:当节点左右子树都为空,返回1;

publicstaticintsize(Noderoot){if(root==null){return0;}if(root.left==null&&root.right==null){return1;}return1+size(root.left)+size(root.right);}

3.2获取叶子节点个数

1)获取左子树的叶子结点的个数;
2)获取右子树的叶子节点的个数:
3)界限:先判断节点是否为空,返回0,再判断节点的左右是否为空.判断是否叶子节点,返回1;
叶子节点个数:左子树叶子结点+右子树节点个数

publicstaticintgetLeafNodeCount(Noderoot){if(root==null){return0;}if(root.left==null&&root.right==null){return1;}returngetLeafNodeCount(root.left)+getLeafNodeCount(root.right);}

3.3获取第几层数的节点

1)获取二叉树的第K层节点个数,就是左右子树的k-1层数;
2)界限:首先当root为null或者k<=0,返回

publicstaticintgetKLeafCount(Noderoot,intk){if(root==null||k<=0){return0;}if(k==1){return1;}returngetKLeafCount(root.left,k-1)+getKLeafCount(root.right,k-1);}

3.4获取二叉树的深度/高度

1)高度 = 根节点一层+左右子树高度较高的层数;
2)当root为null返回0,root.leftnull&&root.rightnull,返回1;

publicstaticintgetHight(Noderoot){if(root==null){return0;}if(root.left==null&&root.right==null){return1;}return1+Math.max(getHight(root.left),getHight(root.right));}

3.5检测值为val的值是否存在

1)判断是否为空树
2)先看根节点是否有相等的值,然后依次判断左右子树是否有相等的值

publicstaticNodefind(Noderoot,intval){if(root==null){returnnull;}if(root.val.equals(val)){returnroot;}NodeleftRoot=find(root.left,val);if(leftRoot!=null){returnleftRoot;}returnfind(root.right,val);}

3.6判断是否是完全二叉树;

1)首先假设节点都有左右子树
标志变量 fla----->false(还未进入二阶段后面节点都没子节点)
2)节点可能不是左右子树
①.节点是右边子树,直接返回false;
②.节点没有子节点,后面的节点都必须没有节点(二阶段,标志为true);
③.节点只有左子节点,后面的节点都必须没有节点(二阶段,标志为true);

publicbooleanisCompleteTree(TreeNoderoot){if(root==null){returnfalse;}booleanfla=false;Queue<TreeNode>queue=newLinkedList<>();queue.offer(root);while(!queue.isEmpty()){TreeNodecur=queue.poll();if(!fla){if(cur.left!=null&&cur.right!=null){queue.offer(cur.left);queue.offer(cur.right);}elseif(cur.left==null&&cur.right!=null){returnfalse;}elseif(cur.left!=null&&cur.right==null){queue.offer(cur.left);fla=true;}else{fla=true;}}else{if(cur.left!=null||cur.right!=null){returnfalse;}}}returntrue;}