devbox
你好赵伟
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

二叉树 - (前序,中序,后序,层序 遍历实现)_本关任务:以顺序结构存储二叉树,编写前序、中序、后序及层次顺序遍历二叉树的算法

作者：你好赵伟 | 2024-06-19 20:37:09

赞

踩

本关任务:以顺序结构存储二叉树,编写前序、中序、后序及层次顺序遍历二叉树的算法

目录

一 . 什么是树

 树的概念

树的表示形式

二.  二叉树

1. 概念 

2. 两种特殊的二叉树

3. 二叉树的性质

4. 二叉树的存储

二叉树的遍历

1. 前序遍历

2. 中序遍历

3 . 后序遍历

二叉树的基本操作

层序遍历

判断完全二叉树

一 . 什么是树

 注意 : 

1.子树是不相交的.

2.除了根节点以外,每个节点有且仅有一个父节点

3,一棵N个节点的树有N-1条边.

 树的概念

1. 结点的度：一个结点含有子树的个数称为该结点的度； 如上图：A的度为6

2. 树的度：一棵树中，所有结点度的最大值称为树的度； 如上图：树的度为6 

3. 叶子结点或终端结点 ：度为 0 的结点称为叶结点； 如上图： B 、 C 、 H 、 I... 等节点为叶结点
4. 双亲结点或父结点 ：若一个结点含有子结点，则这个结点称为其子结点的父结点； 如上图： A 是 B 的父结点
5. 孩子结点或子结点 ：一个结点含有的子树的根结点称为该结点的子结点； 如上图： B 是 A 的孩子结点
6. 根结点 ：一棵树中，没有双亲结点的结点；如上图： A
7. 结点的层次 ：从根开始定义起，根为第 1 层，根的子结点为第 2 层，以此类推

8. 树的高度或深度：树中结点的最大层次； 如上图：树的高度为4


树的表示形式

树的表示方式有很多 , 如 : 双亲表示法,孩子表示法,孩子双亲表示法,孩子兄弟表示法.

我们采用最常用的孩子兄弟表示法.

比较简单 : 就像我们之前学的链表一样.

对于二叉树来说 : 有三个值域 : 分别存储 : 值,  左孩子节点地址,  右孩子节点地址

  1.     public class Node {
  2.         public int val;
  3.         public Node left;
  4.         public Node right;
  5.  
  6.         public Node(int val) {
  7.             this.val = val;
  8.         }
  9.     }

二.  二叉树

1. 概念 : 

二叉树的每个节点的度不能超过2.

 注意 : 对于任意二叉树都是由以下几种情况复合而成的 : 

2. 两种特殊的二叉树

1. 满二叉树: 一棵二叉树，如果 每层的结点数都达到最大值，则这棵二叉树就是满二叉树 。也就是
说， 如果一棵 二叉树的层数为 K ，且结点总数是 2 ^ k  - 1 ，则它就是满二叉树 。

2. 完全二叉树: 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深
度为 K 的 , 有 n 个结点的二叉树，当且仅当其每一个结点都与深度为K 的满二叉树中编号从 0 至 n-1 的
结点一一对应时称之为完全二叉树。 要注意的是 满二叉树是一种特殊的完全二叉树 。

3. 二叉树的性质

1. 若规定 根结点的层数为 1 ，则一棵 非空二叉树的第 i 层上最多有 2 ^ (i - 1) (i>0)个结点.
2. 若规定只有 根结点的二叉树的深度为 1 ，则 深度为 K 的二叉树的最大结点数是 (2^k) - 1(k>=0)
3. 对任何一棵二叉树 , 如果其 叶结点个数为 n0, 度为 2 的非叶结点个数为 n2, 则有 n0 ＝ n2 ＋ 1
4. 具有 n 个结点的完全二叉树的深度 k 为 log(n+1) 上取整

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

        1. 若i>0 ， 双亲序号： (i-1)/2 ； i=0 ， i 为根结点编号 ，无双亲结点
        2. 若2i+1<n ，左孩子序号： 2i+1 ，否则无左孩子
        3. 若2i+2<n ，右孩子序号： 2i+2,   否则无右孩子

4. 二叉树的存储

二叉树的存储结构 分为： 顺序存储 和 类似于链表的链式存储 。
顺序存储用于堆中. 在这里我们使用链式存储

二叉树的遍历

1. 前序遍历

首先我们先用穷举的办法来建一个二叉树 : 

为了方便操作  我们定义一个成员变量root 

  1. public class TreeNode {
  2.     static class Node {
  3.         public int val;
  4.         public Node left;
  5.         public Node right;
  6.  
  7.         public Node(int val) {
  8.             this.val = val;
  9.         }
  10.     }
  11.     Node root = null;
  12.     //创建树
  13.     public void createTree() {
  14.         Node n1 = new Node(11);
  15.         Node n2 = new Node(21);
  16.         Node n3 = new Node(31);
  17.         Node n4 = new Node(41);
  18.         Node n5 = new Node(51);
  19.         Node n6 = new Node(61);
  20.         n1.left = n2;
  21.         n1.right = n3;
  22.         n2.left = n4;
  23.         n2.right = n5;
  24.         n3.right = n6;
  25.         this.root = n1;
  26.     }
  27. }

将上面的代码 图形化 :

 前序遍历 : 根  左   右   依次去遍历

对于二叉树的遍历,使用递归是最好的办法

  1. package demo1;
  2.  
  3. public class TreeNode {
  4.     static class Node {
  5.         public int val;
  6.         public Node left;
  7.         public Node right;
  8.  
  9.         public Node(int val) {
  10.             this.val = val;
  11.         }
  12.     }
  13.     Node root = null;
  14.     //创建树
  15.     public Node createTree() {
  16.         Node n1 = new Node(11);
  17.         Node n2 = new Node(21);
  18.         Node n3 = new Node(31);
  19.         Node n4 = new Node(41);
  20.         Node n5 = new Node(51);
  21.         Node n6 = new Node(61);
  22.         n1.left = n2;
  23.         n1.right = n3;
  24.         n2.left = n4;
  25.         n2.right = n5;
  26.         n3.right = n6;
  27.         return n1;
  28.     }
  29.     public void preorder(Node root) {
  30.         if (root == null) {
  31.             return;
  32.         }
  33.         System.out.print(root.val + " ");
  34.         preorder(root.left);
  35.         preorder(root.right);
  36.     }
  37. }
  38.  
  39.  
  40. package demo1;
  41.  
  42. public class Test {
  43.     public static void main(String[] args) {
  44.         TreeNode treeNode = new TreeNode();
  45.         TreeNode.Node root = treeNode.createTree();
  46.         treeNode.preorder(root);
  47.     }
  48. }

接下来我们来看一下OJ上这道前序遍历的题 : 144. 二叉树的前序遍历 - 力扣（Leetcode）

  1. public List<Integer> preorderTraversal(TreeNode root) {
  2.  
  3. }

它的返回值类型是List<Integer> 

解决的思路有两种 : 

1. 遍历思路

  1. List<Integer> list = new ArrayList<>();
  2.     public List<Integer> preorderTraversal(Node root) {
  3.         pre(root);
  4.         return list;
  5.     }
  6.     public void pre(Node root) {
  7.         if (root == null) {
  8.             return;
  9.         }
  10.         list.add(root.val);
  11.         pre(root.left);
  12.         pre(root.right);
  13.     }

2. 子问题思路

  1. public List<Integer> preorderTraversal(Node root) {
  2.         List<Integer> list = new ArrayList<>();
  3.         if (root == null) {
  4.             return list;
  5.         }
  6.         list.add(root.val);
  7.         List<Integer> left = preorderTraversal(root.left);
  8.         list.addAll(left);
  9.         List<Integer> right = preorderTraversal(root.right);
  10.         list.addAll(right);
  11.  
  12.         return list;
  13.     }

2. 中序遍历

94. 二叉树的中序遍历 - 力扣（Leetcode）

1. 遍历思路解决

  1. List<Integer> list = new ArrayList<>();
  2.     public List<Integer> inorderTraversal(Node root) {
  3.         inorder(root);
  4.         return list;
  5.     }
  6.     public void inorder(Node root) {
  7.         if (root == null) {
  8.             return;
  9.         }
  10.         inorder(root.left);
  11.         list.add(root.val);
  12.         inorder(root.right);
  13.     }

2. 子问题思路解决

  1. public List<Integer> inorderTraversal(TreeNode root) {
  2.         List<Integer> list = new ArrayList<>();
  3.         if (root == null) {
  4.             return list;
  5.         }
  6.         List<Integer> left = inorderTraversal(root.left);
  7.         list.addAll(left);
  8.         list.add(root.val);
  9.         List<Integer> right = inorderTraversal(root.right);
  10.         list.addAll(right);
  11.         return list;
  12.     }

3 . 后序遍历

 遍历思路  :  左   右   根

1. 遍历思路

  1. List<Integer> list = new ArrayList<>();
  2.     public List<Integer> postorderTraversal(TreeNode root) {
  3.         postorder(root);
  4.         return list;
  5.     }
  6.     public void postorder(TreeNode root) {
  7.         if (root == null) {
  8.             return;
  9.         }
  10.         postorder(root.left);
  11.         postorder(root.right);
  12.         list.add(root.val);
  13.     }

2. 子问题思路

  1. public List<Integer> postorderTraversal(TreeNode root) {
  2.         List<Integer> list = new ArrayList<>();
  3.         if (root == null) {
  4.             return list;
  5.         }
  6.         List<Integer> left = postorderTraversal(root.left);
  7.         list.addAll(left);
  8.         List<Integer> right = postorderTraversal(root.right);
  9.         list.addAll(right);
  10.         list.add(root.val);
  11.         return list;
  12.     }

二叉树的基本操作

  1. package demo2;
  2.  
  3. public class BinaryTree {
  4.     static class Node {
  5.         public int val;
  6.         public Node left;
  7.         public Node right;
  8.  
  9.         public Node(int val) {
  10.             this.val = val;
  11.         }
  12.     }
  13.     Node root = null;
  14.     //创建树
  15.     public Node createTree() {
  16.         Node n1 = new Node(11);
  17.         Node n2 = new Node(21);
  18.         Node n3 = new Node(31);
  19.         Node n4 = new Node(41);
  20.         Node n5 = new Node(51);
  21.         Node n6 = new Node(61);
  22.         n1.left = n2;
  23.         n1.right = n3;
  24.         n2.left = n4;
  25.         n2.right = n5;
  26.         n3.right = n6;
  27.         return n1;
  28.     }
  29.     int count = 0;
  30.     // 获取树中节点的个数
  31.     int size(Node root) {
  32.         preorder(root);
  33.         return count;
  34.     }
  35.     public void preorder(Node root) {
  36.         if (root == null) {
  37.             return;
  38.         }
  39.         count++;
  40.         preorder(root.left);
  41.         preorder(root.right);
  42.     }
  43.     // 获取叶子节点的个数
  44.     // 子问题思路-求叶子结点个数
  45.     int getLeafNodeCount(Node root) {
  46.         if (root == null){
  47.             return 0;
  48.         }
  49.         if (root.left == null && root.right == null) {
  50.             return 1;
  51.         }
  52.         return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
  53.     }
  54.  
  55.     // 获取第K层节点的个数
  56.     int getKLevelNodeCount(Node root,int k) {
  57.         if (root == null) {
  58.             return 0;
  59.         }
  60.         if (k == 1) {
  61.             return 1;
  62.         }
  63.         return getKLevelNodeCount(root.left,k - 1) + getKLevelNodeCount(root.right,k - 1);
  64.     }
  65.     // 获取二叉树的高度
  66.     int getHeight(Node root) {
  67.         if (root == null) {
  68.             return 0;
  69.         }
  70.         int leftHeight = getHeight(root.left);
  71.         int rightHeight = getHeight(root.left);
  72.         return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
  73.     }
  74.     // 检测值为value的元素是否存在
  75.     Node find(Node root, int val) {
  76.         if (root == null) {
  77.             return null;
  78.         }
  79.         if (root.val == val) {
  80.             return root;
  81.         }
  82.         Node left = find(root.left,val);
  83.         if (left != null) {
  84.             return left;
  85.         }
  86.         Node right = find(root.right,val);
  87.         if (right != null) {
  88.             return right;
  89.         }
  90.         return null;
  91.     }
  92. }
  1. package demo2;
  2.  
  3. public class Test {
  4.     public static void main(String[] args) {
  5.         BinaryTree binaryTree = new BinaryTree();
  6.         BinaryTree.Node root = binaryTree.createTree();
  7.         System.out.print("树的节点个数 : ");
  8.         System.out.println(binaryTree.size(root));
  9.         System.out.print("树的叶子节点个数 : ");
  10.         System.out.println(binaryTree.getLeafNodeCount(root));
  11.         System.out.print("第3层的节点个数 : ");
  12.         System.out.println(binaryTree.getKLevelNodeCount(root,3));
  13.         System.out.print("树的高度 : ");
  14.         System.out.println(binaryTree.getHeight(root));
  15.         System.out.println("找到21这个节点 : ");
  16.         BinaryTree.Node node = binaryTree.find(root,21);
  17.         System.out.println(node.val);
  18.     }
  19. }

层序遍历

思路 : 从上往下  从左往右 依次遍历

  1. public List<List<Integer>> levelOrder(TreeNode root) {
  2.         List<List<Integer>> lists = new ArrayList<>();
  3.         Queue<TreeNode> queue = new LinkedList<>();
  4.         if (root != null) {
  5.             queue.offer(root);
  6.         }
  7.         while (!queue.isEmpty()) {
  8.             int size = queue.size();
  9.             List<Integer> list = new ArrayList<>();
  10.             while (size-- > 0) {
  11.                 TreeNode node = queue.poll();
  12.                 list.add(node.val);
  13.                 if (node.left != null) {
  14.                     queue.offer(node.left);
  15.                 } 
  16.                 if (node.right != null) {
  17.                     queue.offer(node.right);
  18.                 }
  19.             }
  20.             lists.add(list);
  21.         }
  22.         return lists;
  23.     }

判断完全二叉树

 

  1. // 判断一棵树是不是完全二叉树
  2.     boolean isCompleteTree(Node root) {
  3.         Queue<Node> queue = new LinkedList<>();
  4.         if (root == null) {
  5.             return true;
  6.         }
  7.         queue.offer(root);
  8.         while (!queue.isEmpty()) {
  9.             BinaryTree.Node node = queue.poll();
  10.             if (node == null) {
  11.                 break;
  12.             }
  13.             queue.offer(node.left);
  14.             queue.offer(node.right);
  15.         }
  16.         while (!queue.isEmpty()) {
  17.             if (queue.poll() != null) {
  18.                 return false;
  19.             }
  20.         }
  21.         return true;
  22.     }

希望可以帮到大家~~~~~

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/你好赵伟/article/detail/737590
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号