数据结构二叉树基础以及四种遍历方式（递归和迭代）

╰+哭是因爲堅強的太久メ 2023-07-09 14:25 73阅读 0赞

## 数据结构二叉树基础 ##

### 文章目录 ###

*   *  数据结构二叉树基础
     *  一、二叉树的基本概念
     *  二、特殊的二叉树
     *  三、二叉树的4种遍历方式

## 一、二叉树的基本概念 ##

**节点的度**：一个节点含有的子树的个数称为该节点的度；  
\*\*树的度：\*\*一棵树中，最大的节点的度称为树的度；  
**叶子节点或终端节点**：度为0的节点称为叶节点；  
**双亲节点或父节点**：若一个节点含有子节点，则这个节点称为其子节点的父节点；  
**孩子节点或子节点**：一个节点含有的子树的根节点称为该节点的子节点；  
\*\*根结点：\*\*一棵树中，没有双亲结点的结点；  
\*\*树的高度或深度：\*\*树中节点的最大层次

**一棵二叉树**是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子树和右子树的二叉 树组成。

**二叉树的特点：**

1.  每个结点最多有两棵子树，即二叉树不存在度大于 2 的结点。
2.  二叉树的子树有左右之分，其子树的次序不能颠倒

## 二、特殊的二叉树 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x6aF85OTk5OQ_size_16_color_FFFFFF_t_70]  
1，**完全二叉树:** 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n 个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全 二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x6aF85OTk5OQ_size_16_color_FFFFFF_t_70 1]  
2， **满二叉树:** 一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果 一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。

## 三、二叉树的4种遍历方式 ##

**二叉树遍历方式**：前序遍历、中序遍历、后序遍历、层序遍历。

根据访问结点操作发生位置命名

1.  NLR：前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
2.  LNR：中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。
3.  LRN：后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根 的左子树和根的右子树。NLR、LNR和LRN分别又称为前序遍历、中序遍历和后序遍历。  
**前序遍历**  
**递归代码代码如下：**

//传一棵树的根节点
        public void treeNLR(Node root) {
        
            //先判断该树是否为空树
            if (null == root) {
        
                return;
            }
            //先打印根
            System.out.println(root.val);
            //在打印左子树
            treeNLR(root.left);
            //最后打印右子树
            treeNLR(root.right);
        }

**迭代代码如下：**

public List<Integer> preorderTraversal(TreeNode root) {
        
         LinkedList<Integer> out = new LinkedList<>();
            LinkedList<TreeNode> stack = new LinkedList<>();
            if (null == root) {
        
                return out;
            }
            stack.add(root);
            while (!stack.isEmpty()) {
        
                TreeNode node = stack.pollLast();
                out.add(node.val);
                if (node.right != null) {
        
                    stack.add(node.right);
                }
                if (node.left != null) {
        
                    stack.add(node.left);
                }
            }
            return out;
        }

**中序遍历**代码如下：

//传一棵树的根节点
        public void treeLNR(Node root) {
        
            //先判断该树是否为空树
            if (null == root) {
        
                return;
            }
            //先打印左子树
            treeLNR(root.left);
            //在打印根
            System.out.println(root.val);
            //最后打印右子树
            treeLNR(root.right);
        }
    }

**迭代代码如下：**

//中序遍历
        public List<Integer> inorderTraversal(TreeNode root) {
        
            Stack<TreeNode> stack = new Stack<>();
            LinkedList<Integer> out = new LinkedList<>();
    
            while (root != null || !stack.isEmpty()) {
        
                while (root != null) {
        
                    stack.push(root);
                    root = root.left;
                }
                root = stack.pop();
                out.add(root.val);
                root = root.right;
            }
            return out;
        }

**后序遍历**代码如下：

//传一棵树的根节点
        public void treeLRN(Node root) {
        
            //先判断该树是否为空树
            if (null == root) {
        
                return;
            }
            //先打印左子树
            treeLRN(root.left);
            //在打印右子树
            treeLRN(root.right);
            //最后在打印根
            System.out.println(root.val);
        }

**迭代代码如下：**

public List<Integer> postorderTraversal(TreeNode root) {
        
            LinkedList<TreeNode> stack = new LinkedList<>();
            LinkedList<Integer> output = new LinkedList<>();
            if (root == null) {
        
                return output;
            }
            stack.add(root);
            while (!stack.isEmpty()) {
        
                TreeNode node = stack.pollLast();
                output.addFirst(node.val);
                if (node.left != null) {
        
                    stack.add(node.left);
                }
                if (node.right != null) {
        
                    stack.add(node.right);
                }
            }
            return output;
        }

**二叉树的层序遍历**

**用队列来实现二叉树的层序遍历**

我是通过**迭代**的方法实现：  
先得到一个根节点；判断是否为null；  
不为空的基础上 ，将root添加到队列中，然后进行迭代，  
将队列首元素删除并返回，加入到list集合中，然后将root的左节点和右节点加入队列（在不为空的前提下），然后以此类推，就完成了二叉树的层序遍历。

//二叉树 层序遍历
        public ArrayList<Integer> PrintFromTopToBottom(Node root){
        
            ArrayList<Integer> ret = new ArrayList<>();
            if (root==null) {
        
                return ret;
            }
            Queue<Node> queue = new LinkedList<>();//定义队列
            queue.offer(root);
            while (!queue.isEmpty()) {
        
                Node node = queue.poll();
                ret.add(node.val);
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            return ret;
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x6aF85OTk5OQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200229102324757.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x6aF85OTk5OQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x6aF85OTk5OQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200229102305426.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x6aF85OTk5OQ==,size_16,color_FFFFFF,t_70