【数据结构_10】二叉树（1）

一、树

树是一种非线性的数据结构，是由n个有限节点组成一个具有层次关系的集合。树的每个节点能够延伸出多个子节点，但每个子节点只能由一个父节点。

树形结构中，子树之间不能有交集，否则就不是树形结构。

二、树的表示形式

1.双亲表示法

class Node{

String val;

Node parent;

}//一般我们不使用这种表示方法，此时拿到根节点，无法知道所有的其他节点了

2.孩子表示法

class Node{

String val;

List<Node> children;

}//最常用的表示方法

3.孩子双亲表示法

class Node{

String val;

List<Node> children;

Node parent;

}

4.孩子兄弟表示法

class Node{

String val;

Node firstChild;

List<Node> brotherNodes;

}

三、二叉树

二叉树是一种树形结构，这棵树上面的所有节点，最多不能超过2个叉。也就是说，二叉树的任意节点的度，不能超过2。

以下这些树可以认为是二叉树。

两种特殊的二叉树：

1.满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树。

2.完全二叉树：叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树

四、二叉树的性质

1.若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有

(i>0)个结点

2.若规定只有根结点的二叉树的深度为1，则深度为K的二叉树的最大结点数是

(k>=0)

3.对任何一棵二叉树,如果其叶结点个数为n0,度为2的非叶结点个数为n2,则有n0＝n2＋1

4.具有n个结点的完全二叉树的深度k为

上取整

5.对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i

的结点有：

若i>0，双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点

若2i+1<n，左孩子序号：2i+1，否则无左孩子

若2i+2<n，右孩子序号：2i+2，否则无右孩子

五、二叉树的存储

树与二叉树的存储有着相同的原理：1.有一个专门的类，节点2.拿到根节点，后续的节点就能够一一拿到。

一般用孩子表示法来表示：

class Node{

String val;

Node left;//左子树

Node right;//右子树

}

如果某个节点只有左子树没有右子树，那么right == null;

树的核心操作—树的遍历

把一个集合中，所有的节点，按照一定的次序，全都访问一遍，访问过程中做到“不重不漏”。

*何为访问？访问是一个统称，表示针对这个数据进行的各种操作，例如，修改，判定，计算......

线性结构的遍历很简单，一个节点只有一个后续，但是二叉树是“非线性结构”，二叉树是有两个叉的。

二叉树拥有四种遍历方式：

区分他们的关键是约定好非线性结果的遍历顺序：

1.先序遍历

先序遍历：基于递归

①先访问当前节点的值

*此处以打印为例，就是打印当前节点的值（根节点）

②递归地针对左子树进行先序遍历

③递归地针对右子树进行先序遍历

*判定空，空树就直接返回

*核心操作有三个：（1）打印（2）左子树递归（3）右子树递归

代码段：

    //先序遍历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+"  ");}

这棵树原来的模样，

前序遍历的结果：A B D E G C F

中序遍历的结果：D B G E A C F

后序遍历的结果：D G E B F C A

*结论：

①对于先序遍历来说，第一个元素就是根节点

对于后序来说，最后一个元素就是根节点

②站在子树的角度

先序遍历中的子树部分，第一个元素，也就是子树的根节点

后序遍历的字数部分，最后一个元素，也就是子树的根节点

③对于中序遍历来说，遍历结果中，根节点左侧的元素就是属于左子树，右侧的元素就是属于右子树

进一步的针对子树的中序遍历部分，子树的根节点在中间，左侧部分是子树的左子树中序遍历结果，右侧部分是子树的右子树的中序遍历结果

4.层序遍历

层序遍历就是按照层位维度，把每一层的元素从左到右地访问出来

层序遍历的实现，需要搭配一个“队列”

①创建队列，队列元素就是Node，先把根节点入队列

②循环地取出队首元素，访问这个元素的值

③把这个元素的左子树和右子树都分别入队列（非空）

④回到②，循环操作

⑤如果队列为空，说明遍历就结束了

    //层序遍历public static void levelOrder(Node root){if(root == null){return;}//创建一个队列Queue<Node> 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);}}}

输出：A B C D E F G