数据结构之树型结构

相关概念

重点概念：后续学习将会反反复复出现

对我们当前学习稍微不重要：

树的表示

树有很多种表示方式，如：双亲表示法，孩子表示法、孩子双亲表示法（AVL树、红黑树、B树会用到）、孩子兄弟表示法等等。我们了解一下孩子兄弟表示法：

代码表示：

class Node{int value;//我们当前学习就是简简单单的存个int数字Node firstChild;Node nextNorther;}

二叉树

二叉树：每一个节点的度小于等于2；其实就是每一个节点的孩子个数不超过两个。二叉树的有次序是指你把右子树放左边画出来，结果就是两个不同的树
任意二叉树都是由以下的情况组合的：

满二叉树：每层的结点数都达到最大值；如果层数是k；满二叉树的节点个数为2^k-1

完全二叉树：你按左右到上下编号1-n一定是连续的

二叉树性质

前提：规定第一层是根节点的二叉树
1：第i层最多节点个数：2^(i-1)
2：深度为k；总节点个数最多是2^k-1 (完全二叉树的情况)

3：非常重要；任意的二叉树；叶子节点个数比度为2的节点个数多一个（度为0就是叶子，不涉及到度为1的节点）
n0=n2+1 （如果要把n1也扯上关系；使用n-1=n00+n11+n2*2；n是总节点个数；解释：一颗n个节点的树有N-1条边；而叶子节点不产生边；度为1的节点只产生一条边；度为2的节点产生两条边）
比如有4层：
其实就是；2的4次方等于2的3次方+2都平方+2的1次方+2的0次方+1。
题目：
某二叉树共有399个结点，其中有199个度为2的结点，则该二叉树中的叶子结点数为（）
A不存在这样的二叉树
B200
C198
D199

4：具有n个结点的完全二叉树的深度k为log(n+1)向上取整
不受到你最后层节点个数影响，最后层一个跟2的n-1个是一样，因为用最大节点个数推导出来的
5：对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i的结点有：
若i>0，双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点若2i+1<n，左孩子序号：2i+1，否则无左孩子
若2i+2<n，右孩子序号：2i+2，否则无右孩子
注意：完全二叉树度为1的节点要么是1个，要么是0个。奇数个节点就没有度为1的节点，偶数个节点就有一个度为1的节点。如果题目告诉你2n个节点；那就说明有度为1的节点

二叉树储存

如何遍历：
先序：根—>左子树---->右子树(这个比较容易理解)
中序：左子树—>根—>右子树（先访问左子树，然后你左子树又得按照中序进行）
后序：左子树–>右子树—>根

实现一颗二叉树

创建

//创建一颗树
class  tree{//树的节点，还是内部类实现，类似链表class Listnode{//一个节点包含三个域char val;Listnode left;//左边Listnode right;//右边public Listnode(char val) {this.val = val;}}public Listnode create(){//先把节点和值创建好，然后再绑关系Listnode A=new Listnode('A');Listnode B=new Listnode('B');Listnode C=new Listnode('C');Listnode D=new Listnode('D');Listnode E=new Listnode('E');Listnode F=new Listnode('F');Listnode G=new Listnode('G');//这里的B和C是节点A.left=B;A.right=C;B.left=D;B.right=E;C.left=F;C.right=G;return A;//返回根节点}

遍历（前中后序）

前序：

   public void print1(Listnode root){if(root==null) {return ;}System.out.println(root.val);print1(root.left);print1(root.right);}

中序：这次我们就不打印；遍历把值存在顺序表里

    public List<Character> print2(Listnode root){List<Character> list=new ArrayList<>();if(root==null){return list;}//System.out.println(root.val);list.add(root.val);print2(root.left);print2(root.right);return list;}

后序：

public List<Character> print3(Listnode root){List<Character> ret=new ArrayList<>();if(root==null){return ret;}//System.out.println(root.val);ret.add(root.val);//先把头放进去，然后左边放一个表，右边放一个表，最后放到retList<Character> s=print3(root.left);ret.addAll(s);List<Character> s1=print3(root.right);ret.addAll(s1);return ret;
}

获取树中节点个数

//获取树中节点的个数int num=0;public int size(Listnode root){//遍历计数器if(root==null) {return 0;}num++;size(root.left);size(root.right);return num;}//子问题计数public int size1(Listnode root){if(root==null) {return 0;}int tmp =size1(root.left)+size1(root.right)+1;//(把走到每个节点都分为左边、右边和它自己)return tmp;}

获取叶子节点个数

   // 获取叶子节点的个数int ret3=0;public  void getLeafNodeCount(Listnode root){
//自己为空，肯定就结束了if(root==null){return ;}//如果左边和右边同时为空就计数if(root.left==null&&root.right==null){ret3++;}getLeafNodeCount(root.left);getLeafNodeCount(root.right);}// 子问题思路-求叶子结点个数public  int getLeafNodeCount1(Listnode root){
//自己为空，肯定就结束了if(root==null){return 0;}//如果左边和右边同时为空就计数if(root.left==null&&root.right==null){return 1;}return getLeafNodeCount1(root.left)+getLeafNodeCount1(root.right);}

获取第k层节点个数

   // 获取第K层节点的个数,直接子问题public  int getKLevelNodeCount(Listnode root,int k){
//我们之前不是求了一棵树节点个数吗；假设我要求k层，在k-1的左右子树的和if(root==null||k<=0) {return -1;}if(k==1){//这时候条件就不再是root.left==null&&root.right==null；而是k-1层的孩子节点我都要计算return 1;}int tmp=getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);return tmp;}

获取二叉树高度

非常巧妙：递归的结束root==null；返回上一级到叶子节点；发现height1>height2不成立；叶子节点的右边+1；如果是root.left遍历下的就返回给这里的值。画个图就好理解

  // 获取二叉树的高度public int getHeight(Listnode root) {if(root==null){return 0;}int height1=  getHeight(root.left);int height2= getHeight(root.right);if (height1>height2){return height1+1;//加1是关键，每结束一层+1}elsereturn height2+1;}

检测值为value元素是否存在

   // 检测值为value的元素是否存在public Listnode find(Listnode root, int val) {if (root == null) {return null;}if (root.val == val) {return root;}find(root.left, val);//这里应该把find(root.left,val)存到ret里，避免下面用这个又要重复再递归一次if (find(root.left, val).val == val) {return root;}     //如果我在左边找到就不去右边//如果我在右边找到就直接结束，如果都没找到find(root.right, val);if (find(root.right, val).val == val) {return root;}return null;}

层序遍历（需要队列来实现）

因为二叉树；没法按这种顺序来遍历；就得依靠别的数据结构

这样子它的打印顺序就是从左到右；画图分析好

判断是否为完全二叉树（需要队列来实现）

队列；逻辑：按层次遍历弹出，把Null也放入队列里，当弹出Null的时候发现队列全为Null，就说明是完全二叉树
。不全为null就不是完全二叉树。

   // 判断一棵树是不是完全二叉树   ，这题逻辑还是非常清晰public boolean isCompleteTree(TreeNode root) {if(root == null) {return true;}Queue<TreeNode> qu = new LinkedList<>();qu.offer(root);while (!qu.isEmpty()) {TreeNode cur = qu.poll();if(cur != null) {qu.offer(cur.left);qu.offer(cur.right);}else {break;}}//判断队列剩下的值 是否有 非null的数据while (!qu.isEmpty()) {TreeNode pop = qu.poll();if(pop != null) {return false;}}return true;}