数据结构和算法|树及二叉树【数据结构】数据结构|树|二叉树|遍历二叉

树形结构
- 概念
- 树和非树(图)的区别
- 树的表示形式
二叉树
- 概念和特点
- 特殊的二叉树：
- 二叉树的相关操作
- - 二叉树的表示
  - 二叉树的遍历
  - 求二叉树节点个数
  - 求二叉树叶子节点的个数
  - 求第 K 层节点个数
  - 在二叉树中寻找指定元素

树形结构我们之前研究的基本都是一对一的问题，而树是一种非线性数据结构，它是由n(n≥0)个结点组成的具有有层次关系的有限集

特点：
当 n=0 时，称为空树，在任何一个非空树中：

有且只有一个根结点

当 n>1 时，其余结点可分为 m(m>0) 个互不相交的有限集T1，T2，…Tm，其中每一个集合本身又是一棵树，并且称为根的子树(SubTree)，每棵子树的根节点有且只有一个前驱，可以有0个或多个后继
如图所示：
.
文章图片

树是递归定义的

概念

名称	概念
节点的度：	一个节点含有的子树的个数称为该节点的度；如上图：A的为2，D的为3
树的度：	一棵树中，最大的节点的度称为树的度；如上图：树的度为3
叶子节点或终端节点：	度为 0 的节点称为叶子节点；如上图：G、H、I、F…等节点为叶节点
双亲节点或父节点：	若一个节点含有子节点，则这个节点称为其子节点的父节点；如上图：A是B的父节点

孩子节点或子节点：	一个节点含有的子树的根节点称为该节点的子节点；如上图：B是A的孩子节点
根节点：	一棵树中，没有双亲节点的结点；如上图：A
节点的层次：	从根开始定义起，根为第1层，根的子节点为第2层，以此类推
树的高度或深度：	树中节点的最大层次；如上图：树的高度为4
非终端节点或分支节点：	度不为0的节点；如上图：B、C、D、E…等节点为分支节点
兄弟节点：	具有相同父节点的节点互称为兄弟节点；如上图：B、C是兄弟节点
堂兄弟节点：	双亲在同一层的节点互为堂兄弟；如上图：D、E互为兄弟节点
节点的祖先：	从根到该结点所经分支上的所有节点；如上图：A是所有节点的祖先
子孙：	以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙
森林：	由 m(m≥0) 棵互不相交的树的集合称为森林

树和非树(图)的区别

子树是不相交的
除了根节点外，每个节点有且仅有一个父节点
一颗 n 个节点的树，有 n-1 条边

文章图片

树的表示形式最常用的方法—孩子兄弟表示法：

class Node{int value; //树中存储的数据 Node firstChild; //树中第一个孩子引用 Node nextBrother; //下一个兄弟引用 }

画图表示：

文章图片

二叉树概念和特点概念：
对于在某个阶段都是两种结果的情形，比如：0和1、真和假、上和下、对与错、正和反等，都适合用树状结构来建模，而这种树是很特殊的树状结构，叫做二叉树
二叉树(Binary Tree)是 n(n≥0) 个节点的有限集合，该集合或者为空集(称为空二叉树)，或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成
特点：

每个节点最多有两棵子树，二叉树的度大能超过 2
注意不是只有两棵子树，而是最多有，没有子树或者有一棵子树也是可以的
二叉树的子树有左右之分，其子树的次序不能任意颠倒，因此二叉树是有序树
即使树中某节点只有一棵子树，也要区分它是左子树还是右子树

二叉树的基本形态：

空二叉树

只有一个根节点

根节点只有左子树

根节点只有右子树

根结点既有左子树又有右子树

文章图片

特殊的二叉树：满二叉树：
一个二叉树，若每一个层的节点数都达到最大值(即：2)，则就为满二叉树
一个二叉树的层数为 n，且节点总数是 2n-1

文章图片

满二叉树的特点：

叶子只出现在最下一层，出现在其他层就不可能达到平衡
非叶子节点的度一定是2
在同样深度的二叉树中，满二叉树的节点个数最大，叶子个数也最多

完全二叉树：
直观来说：相比于满二叉树来说，完全二叉树右小角缺了一块
完全二叉树是效率很高的数据结构，对于深度为K的，有n个节点的二叉树，当且仅当其每一个节点都与深度为K的满二叉树中编号从1至n的节点一一对应时称之为完全二叉树，满二叉树是一种特殊的完全二叉树

文章图片

完全二叉树的特点：

叶子节点只能出现在最下两层
最下层的叶子一定集中在左边连续位置
倒数第二层，如果有叶子节点，一定出现在右边连续位置
若节点度为1，则该节点只有左子树
同样节点数的二叉树，完全二叉树的深度最小

二叉树的相关操作二叉树的表示
可通过左右孩子来表示

class Node{int val; //存储的数据 Node left; //左子树根节点的引用 Node right; //右子树根节点的引用 Node parent; //双亲的引用(可选) }

二叉树的遍历
遍历：遍历按照一定的顺序访问到集合中的每个元素，不重复不遗漏
由于二叉树不是线性结构，故遍历起来相对复杂
手动构造一棵树：

class Node{char val; //存储的数据 Node left; //左子树根节点的引用 Node right; //右子树根节点的引用 Node parent; //双亲的引用(可选)//提供构造方法 public Node(char val) {this.val = val; } }//构建一棵树 public static Node buildTree(){Node a = new Node('A'); Node b = new Node('B'); Node c = new Node('C'); Node d = new Node('D'); Node e = new Node('E'); a.left = b; a.right = c; b.left = d; b.right = e; return a; }

1.先序遍历
先访问根节点，递归遍历左子树，递归遍历右子树 (根左右)
例图：

文章图片

代码实现：

public static void preOrder(Node root){//若为空树，直接返回 if(root == null){return; } //先访问根节点 System.out.print(root.val+" "); //递归访问左子树 preOrder(root.left); //递归访问右子树 preOrder(root.right); }

2.中序遍历
先递归遍历左子树，访问根节点，再递归遍历右子树 (左根右)
例图：

文章图片

public static void inOrder(Node root){//若为空树，直接返回 if(root == null){return; } //递归访问左子树 inOrder(root.left); //访问根节点 System.out.print(root.val+" "); //递归访问右子树 inOrder(root.right); }

3.后序遍历
先递归遍历左子树，再递归遍历右子树，最后访问根节点 (左右根)
【数据结构和算法|树及二叉树【数据结构】】例图：

文章图片

public static void postOrder(Node root){//若为空树，直接返回 if(root == null){return; } //递归访问左子树 postOrder(root.left); //递归访问右子树 postOrder(root.right); //访问根节点 System.out.print(root.val+" "); }

4.层序遍历
一层一层往下遍历，每层从左向右访问，为非递归操作

public static void levelOrder(Node root){//创建一个空队列并把根节点加入队列中 Queue queue = new LinkedList<>(); queue.offer(root); while( !queue.isEmpty()){//队列非空，取出队首元素 Node cur = queue.poll(); //访问元素 System.out.print(cur.val + " "); //把左右子树入队列 if(cur.left != null){queue.offer(cur.left); } if(cur.right != null){queue.offer(cur.right); } } }

例图：

文章图片

遍历规律：

先序遍历，第一个访问的节点一定是根节点
后续遍历，最后一个访问的节点一定是根节点
中序遍历和后序遍历，第一个访问的节点是树的最左侧节点
针对先 / 后序遍历来说，子树的遍历结果是嵌套在整个遍历结果中的
中序遍历，左子树的遍历结果在根节点的左侧，右子树的遍历结果在根节点的右侧

输出结果：

文章图片

求二叉树节点个数

public static int size(Node root){if(root == null){return 0; } //树节点总数 = 根节点个数(1) + 左子树节点个数 + 右子树节点个数 return 1 + size(root.left) + size(root.right); }输出结果：5

画图分析：
执行顺序和"后序遍历"一模一样

文章图片

求二叉树叶子节点的个数
叶子节点：即度为0的节点

public static int leafSize(Node root){//空树 if(root == null){return 0; } //只有根节点时，根节点就是唯一的叶子节点 if(root.left == null && root.right == null){return 1; } // root叶子节点个数 = root.left叶子节点个数 + root.right叶子节点个数 return leafSize(root.left) + leafSize(root.right); }输出结果：3

画图分析：

文章图片

求第 K 层节点个数

public static int kLevelSize(Node root,int k){//若 k<1 或root为空，则为空树 if(k < 1 || root == null){return 0; } //若 k=1，即为根节点 if(k == 1){return 1; } // k 层节点个数 = 左子树的(k-1)层节点个数 + 右子树的(k-1)层节点个数 return kLevelSize(root.left,k-1) + kLevelSize(root.right,k-1); }输出结果：2

画图分析：

文章图片

在二叉树中寻找指定元素

public static Node find(Node root,char toFind){if(root == null){return null; } if(root.val == toFind){return root; } //递归查找左右子树 Node result = find(root.left,toFind); if(result != null){return result; } return find(root.right,toFind); }

画图分析：