复旦大学961-数据结构-第二章-树（2）-二叉树的遍历，普通树与二叉树的转换

叁歲伎倆 2022-12-11 13:38 117阅读 0赞

[961全部内容链接][961]

### 文章目录 ###

*  二叉树及其性质
 *   *  二叉树的定义
     *  几种特殊的二叉树
     *  二叉树的性质
     *   *  完全二叉树的性质
     *  二叉树的Java定义
 *  二叉树的遍历
 *   *  二叉树的前序遍历（递归）
     *  二叉树的前序遍历（非递归）
     *  二叉树的中序遍历（递归）
     *  二叉树的中序遍历（非递归）
     *  二叉树的后序遍历（递归）
     *  二叉树的后序遍历（非递归）
     *  二叉树的层序遍历
 *  普通树与二叉树的转换
 *   *  普通树转二叉树方法
     *  普通树转二叉树（递归）
     *  普通树转二叉树（非递归）
     *  二叉树转普通树（递归）
     *  二叉树转普通树（非递归）

# 二叉树及其性质 #

## 二叉树的定义 ##

1.  二叉树的定义：每个节点至多有两棵子树，即二叉树中不存在度大于2的节点
2.  二叉树是有序树，即左右子树不能颠倒

## 几种特殊的二叉树 ##

1.  满二叉树：一棵高度为 **2h\-1** 个节点的二叉树，称为满二叉树。就是说，除了最后一层，其他层的节点的度必须都为2。说白了就是把二叉树画满。![在这里插入图片描述][20201001171603204.png_pic_center]
2.  完全二叉树：相对于满二叉树而言，没那么满，少了几个节点（只能最后几个节点少）的二叉树，为完全二叉树。![在这里插入图片描述][2020100117181554.png_pic_center]
3.  二叉排序树：左子树的所有节点的关键字均小于根节点关键字，右子树的所有关键字均大于根节点关键字。且左右子树也是二叉排序树。![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nZmVpXzM1OA_size_16_color_FFFFFF_t_70_pic_center]
4.  平衡二叉树：树上任意一个节点的左右子树的深度之差不大于1

## 二叉树的性质 ##

1. 非 空 二 叉 树 上 的 叶 子 结 点 数 等 于 度 为 2 的 结 点 数 加 1 ， 即 n 0 = n 2 + 1 2. 非 空 二 叉 树 上 第 k 层 上 至 多 有 2 k − 1 个 节 点 ( k ≥ 1 ) 3. 高 度 为 h 的 二 叉 树 至 多 有 2 h − 1 个 结 点 \\begin\{aligned\} & 1. 非空二叉树上的叶子结点数等于度为2的结点数加1，即 n\_0 = n\_2+1 \\\\ & 2. 非空二叉树上第k层上至多有 2^\{k-1\}个节点 (k\\ge 1) \\\\ & 3. 高度为h的二叉树至多有 2^h -1 个结点 \\\\ \\end\{aligned\} 1.非空二叉树上的叶子结点数等于度为2的结点数加1，即n0=n2\+12.非空二叉树上第k层上至多有2k−1个节点(k≥1)3.高度为h的二叉树至多有2h−1个结点

### 完全二叉树的性质 ###

对完全二叉树，从上到下，从左到右的顺序依次编号 1,2,…n，则有以下关系：  
 1. 当 i > 1 时 ， 其 双 亲 的 编 号 为   ⌊ i / n ⌋ 2. 当 i 为 偶 数 时 ， 为 左 孩 子 ， 当 i 为 奇 数 时 ， 为 右 孩 子 3. 当 i ≤ ⌊ n / 2 ⌋ ， 则 节 点 i 为 分 支 节 点 ， 否 则 为 叶 子 结 点 4. 高 度 为 ⌊ log ⁡ 2 n ⌋ + 1 \\begin\{aligned\} & 1. 当i>1时，其双亲的编号为 ~ \\lfloor i/n \\rfloor \\\\ & 2. 当i为偶数时，为左孩子，当i为奇数时，为右孩子 \\\\ & 3. 当 i \\le \\lfloor n/2 \\rfloor ，则节点i为分支节点，否则为叶子结点 \\\\ & 4. 高度为 \\lfloor \\log\_2n\\rfloor +1 \\end\{aligned\} 1.当i>1时，其双亲的编号为 ⌊i/n⌋2.当i为偶数时，为左孩子，当i为奇数时，为右孩子3.当i≤⌊n/2⌋，则节点i为分支节点，否则为叶子结点4.高度为⌊log2n⌋\+1

## 二叉树的Java定义 ##

class BinaryNode<AnyType> { 
    	
    	    AnyType element;
    	    BinaryNode<AnyType> left;
    	    BinaryNode<AnyType> right;
    	
    	    public BinaryNode(AnyType x) { 
    	        this.element = x;
    	    }
    	
    	}

# 二叉树的遍历 #

## 二叉树的前序遍历（递归） ##

public static void preOrder(BinaryNode root) { 
        if (root == null) return;
        System.out.print(root.element + " "); // 输出根节点
        preOrder(root.left);  // 访问左节点
        preOrder(root.right); // 访问右节点
    }

## 二叉树的前序遍历（非递归） ##

public static void preOrder(BinaryNode root) { 
         Stack stack = new Stack();  // 初始化栈
         BinaryNode node = root;
         while (node != null || stack.size() > 0) { 
             if (node != null) { 
                 System.out.print(node.element + " ");  // 输出根节点
                 stack.add(node);    // 根节点入栈
                 node = node.left;   // 访问根节点左子树
             } else { 
                 BinaryNode temp = (BinaryNode)stack.pop();  //左子树为空，其父节点出栈（获取该父节点）
                 node = temp.right;  // 访问其右节点
             }
         }
     }

基本思路：

1.  初始化栈，用于存放结点指针。
2.  访问根节点，若根节点不为空，则输出根节点内容，然后将根节点入栈，然后对其左子树做同样操作
3.  第2步一直循环，直到左子树为空，然后从栈顶弹出一个节点，然后对其右子树重复2步骤，直到最后栈为也空

易错点：

1.  while循环时，**node!=null 的条件一定要加**，否则，访问右节点后的下一轮循环时，栈有可能是空的，若没有 node!=null 的条件，则会无法访问右子树
2.  根节点可以在外部访问后入栈，也可以和上面代码一样不访问，等到到循环中也会对其访问
3.  **节点出栈后不能对其访问**，因为在入栈之前就已经访问过了
4.  栈顶出站后，别忘了**强制类型转换**

## 二叉树的中序遍历（递归） ##

public static void inOrder(BinaryNode root) { 
     	if (root == null) return;
        inOrder(root.left);  // 访问左节点
        System.out.print(root.element + " "); // 输出根节点
        inOrder(root.right); // 访问右节点
    }

## 二叉树的中序遍历（非递归） ##

public static void inOrder(BinaryNode root) { 
        Stack stack = new Stack();  //初始化栈
        BinaryNode node = root;
        while (node != null || stack.size() > 0) { 
            if (node != null) { 
                stack.push(node);  // 根节点入栈
                node = node.left;  // 访问左节点
            } else { 
                BinaryNode tempNode = (BinaryNode) stack.pop();  // 当该节点为空时，弹出该节点的父节点（即该节点的父节点没有左孩子）
                System.out.print(tempNode.element + " ");  // 输出该节点的父节点
                node = tempNode.right;  // 访问其右节点
            }
        }
    }

基本思路：

1.  初始化栈，用于存放结点指针
2.  从根节点开始，若根节点存在，则入栈，然后对其左子树做同样步骤
3.  若发现左子树为空，则从栈中弹出一个节点，输出，然后对其右子树重复2步骤，直到栈为空

## 二叉树的后序遍历（递归） ##

public static void postOrder(BinaryNode root) { 
        if (root == null) return;
        postOrder(root.left);  // 访问左节点
        postOrder(root.right); // 访问右节点
        System.out.print(root.element + " "); // 输出根节点
    }

## 二叉树的后序遍历（非递归） ##

/** * 1. 从根节点开始，依次往下遍历左孩子，并入栈 * 2. 若左孩子为空，访问栈顶，判断栈顶的右孩子是否为空，若不为空，且没有被访问过，则重复1. * 3. 若右孩子为空，或被访问过，则栈顶出栈并输出。 */
     public static void postOrder(BinaryNode root) { 
         Stack stack = new Stack(); // 初始化栈
         BinaryNode node = root;
         BinaryNode rightNode = null; // 用于判断右节点是否被遍历过
         while (node != null || stack.size() > 0) { 
             if (node != null) {   // 节点不为空，入栈，并访问其左孩子
                 stack.add(node);
                 node = node.left;
             } else { 
                 BinaryNode topNode = (BinaryNode) stack.peek();  // 读栈顶元素
                 if (topNode.right != null && topNode.right != rightNode) {   // 栈顶的右孩子不为空且没有被访问过
                     node = topNode.right;  // 访问栈顶右孩子，并入栈
                     stack.add(node);    
                     node = node.left;   // 重复1，访问栈顶右孩子的左孩子
                 } else { 
                     stack.pop();  // 栈顶的右孩子为空，或被访问过，则栈顶出栈，并输出
                     System.out.print(topNode.element + " ");
                     rightNode = topNode;  // 记录当前节点，以便于栈顶元素判断右孩子是否被访问过
                     node = null;  // 每次出栈访问完一个节点，就相当于遍历完以该节点为根的子树，需将node重置为null，这样下一轮，就会认为左子树为空，然后去判断右子树去了，否则，左孩子就会不断地入栈出栈，陷入死循环。
                 }
             }
         }
     }

基本思路：

1.  从根节点开始，依次往下遍历左孩子，并入栈
2.  若左孩子为空，访问栈顶，判断栈顶的右孩子是否为空，若不为空，且没有被访问过，则对右孩子重复1.
3.  若右孩子为空，或被访问过，则栈顶出栈并输出。

易错点：

1.  初始化时，要初始化一个节点变量，用于存放上次被访问的右孩子指针。用于判断是否右孩子被访问过
2.  每次访问（输出）完节点后，需要将当前的node变量置空，以便可以再对上面的结点出栈，否则就在卡在“输出当前节点，然后下一轮，当前节点不为空，入栈，访问左子树，左子树为空，且右子树访问过了，栈顶出栈，输出当前节点，然后无限循环下去”。

**while中的判断思路**，这个到考场容易想不起来，容易乱：

1.  节点是否为空，若不为空，则入栈，然后访问其左节点
2.  若节点为空，然后再分情况讨论  
    2.1 栈顶节点（相当于该空节点的父节点）的右子树不为空，且没有被访问过，则访问其右子树，然后再访问其右子树的左子树，结束进入下一轮循环  
    2.2 若栈顶节点右子树为空，则出栈，输出栈顶节点，然后记录最近访问过的节点（rightNode），将node置空，结束进入下一轮循环。

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

public static void levelOrder(BinaryNode root) { 
        if (root == null) return;
        Queue q = new ArrayDeque();  // 初始化队列
        q.add(root);  // 根节点入队
        while (q.size() > 0) { 
            BinaryNode tempNode = (BinaryNode) q.poll();  // 如果队列不为空，出队并输出
            System.out.print(tempNode.element+ " ");
            if (tempNode.left != null) q.add(tempNode.left); // 将该节点的左孩子和右孩子依次入队
            if (tempNode.right != null) q.add(tempNode.right);
        }
    }

# 普通树与二叉树的转换 #

普通树Java定义

public class TreeNode<AnyType> { 
        AnyType element;
        TreeNode<AnyType> firstChild;
        TreeNode<AnyType> nextSibling;  // sibling: 兄弟姐妹
    
        public TreeNode (AnyType x) { 
            this.element = x;
        }
    }

## 普通树转二叉树方法 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nZmVpXzM1OA_size_16_color_FFFFFF_t_70_pic_center 1]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nZmVpXzM1OA_size_16_color_FFFFFF_t_70_pic_center 2]

1.  在兄弟节点之间加一连线。
2.  对每个节点，只保留它与第一个孩子的连线，而与其他孩子的连线全部抹掉
3.  以树根为轴心，顺时针旋转45°

二叉树转普通树反过来即可

## 普通树转二叉树（递归） ##

private static void transferToBinaryTree(TreeNode treeNode, BinaryNode binaryNode) { 
        if (treeNode.firstChild != null) { 
            binaryNode.left = new BinaryNode(treeNode.firstChild.element);
            transferToBinaryTree(treeNode.firstChild, binaryNode.left);
        }
        if (treeNode.nextSibling != null) { 
            binaryNode.right = new BinaryNode(treeNode.nextSibling.element);
            transferToBinaryTree(treeNode.nextSibling, binaryNode.right);
        }
    }
    
    /** * 1. 首先构造根节点。然后开始递归 * 2. 判断firstChild是否为空，若不为空，则链接到二叉树的左孩子，递归进入下一层firstChild，否则到3 * 3. 判断nextSibling（右兄弟）是否为空，若不为空，则链接到二叉树的右孩子，递归进入下一层nextSibling，否则退出到上层递归。 */
    public static BinaryNode transferToBinaryTree(TreeNode treeRoot) { 
        if (treeRoot == null) return null;
        BinaryNode binaryRoot = new BinaryNode(treeRoot.element);
        transferToBinaryTree(treeRoot, binaryRoot);
        return binaryRoot;
    }

## 普通树转二叉树（非递归） ##

todo ，应该不考，有时间再弄

## 二叉树转普通树（递归） ##

private static void transferToTree(BinaryNode binaryNode, TreeNode treeNode) { 
        if (binaryNode.left != null) { 
            treeNode.firstChild = new TreeNode(binaryNode.left.element);
            transferToTree(binaryNode.left, treeNode.firstChild);
        }
        if (binaryNode.right != null) { 
            treeNode.nextSibling = new TreeNode(binaryNode.right.element);
            transferToTree(binaryNode.right, treeNode.nextSibling);
        }
    }
    
    /** * 1. 构造普通树的根节点，然后开始递归 * 2. 判断是否有左孩子，若有左孩子，则链接到tree的左节点，然后递归进入下一层，否则进入3 * 3. 判断是否有右孩子，若有右孩子，则链接到tree的nextSibling（右兄弟），然后递归下一层。 */
    public static TreeNode transferToTree(BinaryNode root) { 
        if (root == null) return null;
        TreeNode treeNode = new TreeNode(root.element);
        transferToTree(root, treeNode);
        return treeNode;
    }

## 二叉树转普通树（非递归） ##

todo，应该不考，有时间弄

[961]: https://blog.csdn.net/zhaohongfei_358/article/details/111414370
[20201001171603204.png_pic_center]: /images/20221123/ec85a7a12e0f406aa957167fee516a47.png
[2020100117181554.png_pic_center]: /images/20221123/d7c11e528f7f49eab2e25fb9a2ef20e0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nZmVpXzM1OA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/e00f6e6c82e0477082b748db6e9faa62.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nZmVpXzM1OA_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/a2032cd3f3e346baa72a69fd6c0f9b18.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nZmVpXzM1OA_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/71b7c9763c5a47c1ba1822189b18d083.png