【Java数据结构】二叉树

1.树型结构

1.1树的概念

        树是一种非线性的数据结构，由n个结点组成的具有条理关系的集合。下面是它的特点：

• 根结点是没有前驱的结点（没有父结点的结点）
  
• 子结点之间互不相交
  
• 除了根结点外，别的结点都只有一个父结点
  
• n个结点有n-1条边
  

下面介绍一些常见的概念：

• 结点的度：该结点有多少子节点，度就为几
  
• 树的度：一个树中每个结点度中最大的那个就是树的度
  
• 叶子结点：度为0的结点（不唯一）
  
• 根结点：没有前驱的结点（也就是没有父结点的结点）
  
• 双亲结点（父结点）：该结点的父结点（唯一）
  
• 孩子结点（子结点）：该结点的子结点（不唯一）
  
• 结构的条理：从根结点为第一层，今后数
  

下面这些就是相识即可：

• 树的高度：有几层树就有多高
  
• 非终端结点（分支节点）：除根结点和叶子结点外的结点
  
• 兄弟结点：雷同父结点之间称兄弟
  
• 堂兄弟结点：父结点在同一层但不是同一个的结点之间称为堂兄弟
  
• 结点的先人：在一棵树上，根结点是全部结点的先人
  
• 子孙：该结点为根，今后层数与它相关的结点都是它的子孙
  
• 森林：由m个互不相交的树组成的就是森林
  

1.2树的表现形式

        树的表现形式分多种，如双亲表示法、孩子表示法、孩子双亲表示法、孩子兄弟表示法等等，常用的就是孩子兄弟表示法。

2.二叉树 

2.1二叉树的概念

         一颗二叉树是结点的一个有限集合， 其中二叉树不存在度大于2的结点，并且二叉树的左子树和右子树是不能互换的，空树也是二叉树。
2.2特殊二叉树

• 满二叉树：满二叉树就是每层的结点数都达到该层最大值。如果由k层，那么结点总数就是2^（k-1）；
  
• 完全二叉树：完全二叉树就是假设有k层，其k-1层中每一层都是满的，在第k层中必须要从左到右依次放结点，如果中心出现空那么就不是二叉树；
  

 
2.3二叉树的性子

• 第i层上最多有2^（i-1）个结点；
  
• 深度为k的二叉树最大结点数为2^k-1（将每一层的结点数相加=>等比数列求和）；
  
• 叶子结点有n0个，度为2的结点有n2个，就会出现n0 = n2 + 1这个式子；
  
• n个结点的完全二叉树的深度k为log (n+)向上取整；
  
• n个结点的二叉树，从上到下，从左到右排序。（1）已知父结点下标为i，求孩子结点下标。左孩子下标：(2*i)+1；右孩子下标：(2*i)+2 ；（2）已知孩子结点下标i，求父结点下标。父结点下标：(i-1)/2;
  

下面是一些关于二叉树性子的题目： 

由于度为0的结点数等于度为2的结点数加1，题目已知度为2的结点数就可以得到度为0的结点数，所以答案选B。

如果总结点数为偶数，那么度为1的结点个数是1个；如果结点为奇数，那么度为1的结点个数为0，再根据n0 =  n2 + 1，就可以求出叶子结点个数，所以答案选A。

由于log (n+1) 向上取整就是这个二叉树的高度，2^9 = 512 < 531 < 2^10 = 1024，所以答案选B。
2.4二叉树的存储

二叉树的存储分顺序存储和类似于链表的链式存储，现在紧张讲解链式存储。
        链式存储是将一个一个结点连起来，一个结点有数据域和引用域（可多个），每个表示法的引用域都不是一样的，举一个例子：

1. // 孩子表示法
2. class Node {
3.    int val; // 数据域
4.    Node left; // 左孩子的引用
5.    Node right; // 右孩子的引用
6. }

复制代码

 2.5二叉树的创建（简单型）

        起首和之前的线性表一样，使用内部类创建结点，然后再创建二叉树对应的结点个数，然后再将它们串连成二叉树，下面是孩子表示法结点创建： 

1. public class BrinaryTree {
2.     static class Node{
3.         public char val;
4.         public Node left;
5.         public Node right;
6.         public Node(char val){
7.             this.val = val;
8.         }
9.     }
10.     //创建二叉树
11.     public Node creatTree(){
12.         Node A = new Node('A');
13.         Node B = new Node('B');
14.         Node C = new Node('C');
15.         Node D = new Node('D');
16.         Node E = new Node('E');
17.         Node F = new Node('F');
18.         Node G = new Node('G');
19.         Node H = new Node('H');
21.         A.left = B;
22.         A.right = C;
23.         B.left = D;
24.         B.right = E;
25.         C.left = F;
26.         C.right = G;
27.         E.right = H;
28.         return A;
29.     }

复制代码

 2.6二叉树的遍历

        以上是三种遍历，如果只是想要相识如何遍历而不是想通过通例本领得到答案的话，上面的方法就是最简单的理解方式。如果是前序遍历起首在结点左边（也可以称结点前面）做一个记号；如果是中序遍历起首在结点下面（也可以称结点中心）做一个记号；如果是后序遍历起首在结点右边（也可以称结点背面）做一个记号，然后从根结点的左边开始，围绕二叉树外延走一圈，最后到的根结点的右边为结束，在这过程中打仗记号的顺序就是遍历的结果。
如果是按照通例思路来讲，就是什么遍历根结点就在哪个位置。好比前序遍历就是根左右，中序遍历就是左根右，后序遍历就是左右根。如果这个结点又是左结点又是根结点，那就根结点，别的的环境一样的。
下面我们用代码来实现这些遍历： 

• 前序遍历
  

不管如何第一步都是判断这棵树是否为空，然后就是打印该根结点，然后用递归将根结点的左边的树遍历一遍，再用递归把根结点右边的树遍历一遍。下面是一棵二叉树的代码及遍历过程：

1. public void preOrder(Node root){
2.         if(root == null)
3.             return ;
4.         System.out.print(root.val+"  ");
5.         preOrder(root.left);
6.         preOrder(root.right);
7.     }

复制代码

前序遍历返回链表结构
如果是返回一个链表结构，那就要利用返回的链表实现遍历，看图更能直观理解意思以及代码。（理解前序后，中序后序都是一个原理）

1.     public List<Node> preOrder2(Node root){
2.         List<Node> ret = new ArrayList<>();
3.         if (root == null)
4.             return ret;
5.         ret.add(root);
6.         List<Node> Left = preOrder2(root.left);
7.         ret.addAll(Left);
8.         List<Node> Right = preOrder2(root.right);
9.         ret.addAll(Right);
10.         return ret;
11.     }

复制代码

•  中序遍历
  

中序遍历原理差不多，开始也是判断是否为空，然后通过递归遍历根结点左边的树，再打印根结点，最后再递归遍历根结点右边的树。

1.     public void inOrder(Node root){
2.         if (root == null)
3.             return;
4.         inOrder(root.left);
5.         System.out.print(root.val+"  ");
6.         inOrder(root.right);
7.     }

复制代码

中序遍历返回链表结构

1.     public List<Node> inOrder2(Node root) {
2.         List<Node> ret = new ArrayList<>();
3.         if (root == null)
4.             return ret;
5.         List<Node> leftTree = inOrder2(root.left);
6.         ret.addAll(leftTree);
7.         ret.add(root);
8.         List<Node> rightTree = inOrder2(root.right);
9.         ret.addAll(rightTree);
10.         return ret;
11.     }

复制代码

• 后序遍历
  

后序遍历也是一样原理，只是换成了左右根，先根遍历结点左边的树，然后遍历根结点右边的树，最后在打印。

1.     public void postOrder(Node root){
2.         if (root == null)
3.             return ;
4.         postOrder(root.left);
5.         postOrder(root.right);
6.         System.out.print(root.val+"  ");
7.     }

复制代码

  后序遍历返回链表结构

1.     public List<Node> postOrder2(Node root) {
2.         List<Node> ret = new ArrayList<>();
3.         if (root == null)
4.             return ret;
5.         List<Node> leftTree = postOrder2(root.left);
6.         ret.addAll(leftTree);
7.         List<Node> rightTree = postOrder2(root.right);
8.         ret.addAll(rightTree);
9.         ret.add(root);
10.         return ret;
11.     }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。