樹-順序存儲二叉樹

二叉樹-刪除節點

思考題(課後練習)

  1. 如果要刪除的節點是非葉子節點，現在我們不希望將該非葉子節點為根節點的子樹刪除，需要指定規則, 假如規定如下:
  2. 如果該非葉子節點 A 只有一個子節點 B，則子節點 B 替代節點 A
  3. 如果該非葉子節點 A 有左子節點 B 和右子節點 C，則讓左子節點 B 替代節點 A。
  4. 請大家思考，如何完成該刪除功能, 老師給出提示.(課後練習)

 

 

 

 

順序存儲二叉樹

 

 

順序存儲二叉樹的概念

 

 

    • 基本說明

從數據存儲來看，數組存儲方式和樹的存儲方式可以相互轉換，即數組可以轉換成樹，樹也可以轉換成數組， 看右面的示意圖。

    • 要求:
  1. 右圖的二叉樹的結點，要求以數組的方式來存放 arr : [1, 2, 3, 4, 5, 6, 6]
  2. 要求在遍曆數組 arr 時，仍然可以以前序遍歷，中序遍歷和後序遍歷的方式完成結點的遍歷

 

 

    • 順序存儲二叉樹的特點:

 

 

  1. 順序二叉樹通常只考慮完全二叉樹
  2. 第 n 個元素的左子節點為 2 * n + 1
  3. 第 n 個元素的右子節點為 2 * n + 2
  4. 第 n 個元素的父節點為 (n-1) / 2
  5. n : 表示二叉樹中的第幾個元素(按 0 開始編號如圖所示)

 

 

順序存儲二叉樹遍歷

需求: 給你一個數組 {1,2,3,4,5,6,7}，要求以二叉樹前序遍歷的方式進行遍歷。 前序遍歷的結果應當為

1,2,4,5,3,6,7

程式碼實現

  1 package com.xuge.tree;
  2 
  3 /**
  4  * author: yjx
  5  * Date :2022/5/3122:31
  6  **/
  7 public class ArrayBinaryTreeDemo {
  8   public static void main(String[] args) {
  9     int[] arr = {1, 2, 3, 4, 5, 6, 7};
 10     ArrayBinaryTree tree = new ArrayBinaryTree(arr);
 11     tree.preOrder();
 12     tree.infixOrder(0);
 13   }
 14 }
 15 
 16 //實現順序存儲二叉樹遍歷
 17 class ArrayBinaryTree {
 18   private int[] arr;//存儲數據節點
 19 
 20   public ArrayBinaryTree(int[] arr) {
 21     this.arr = arr;
 22   }
 23   public void preOrder(){
 24     this.preOrder(0);
 25   }
 26   //編寫一個方法，實現對二叉樹前序遍歷
 27 
 28   /**
 29    * @param index 數組下標
 30    */
 31   public void preOrder(int index) {
 32     //如果數組為空或者數組為0
 33     if (arr.length == 0 || arr == null) {
 34       System.out.println("不能遍歷..");
 35       return;
 36     }
 37     //輸出當前這個元素
 38     System.out.println(arr[index]);
 39     //向左遞歸遍歷
 40     if ((index * 2 + 1) < arr.length ) {
 41       preOrder(2 * index + 1);
 42     }
 43 
 44     //向右遞歸遍歷
 45     if ((index * 2 + 2) < arr.length ) {
 46       preOrder(2 * index + 2);
 47     }
 48   }
 49 
 50 
 51 
 52   //編寫一個方法，實現對二叉樹中序遍歷
 53 
 54   /**
 55    * @param index 數組下標
 56    */
 57   public void infixOrder(int index) {
 58     //如果數組為空或者數組為0
 59     if (arr.length == 0 || arr == null) {
 60       System.out.println("不能遍歷..");
 61       return;
 62     }
 63     //向左遞歸遍歷
 64     if ((index * 2 + 1) < arr.length ) {
 65       infixOrder(2 * index + 1);
 66     }
 67 
 68     //輸出當前這個元素
 69     System.out.println(arr[index]);
 70 
 71     //向右遞歸遍歷
 72     if ((index * 2 + 2) < arr.length ) {
 73       infixOrder(2 * index + 2);
 74     }
 75   }
 76 
 77 
 78   //編寫一個方法，實現對二叉樹中序遍歷
 79 
 80   /**
 81    * @param index 數組下標
 82    */
 83   public void postOrder(int index) {
 84     //如果數組為空或者數組為0
 85     if (arr.length == 0 || arr == null) {
 86       System.out.println("不能遍歷..");
 87       return;
 88     }
 89     //向左遞歸遍歷
 90     if ((index * 2 + 1) < arr.length ) {
 91       postOrder(2 * index + 1);
 92     }
 93     //向右遞歸遍歷
 94     if ((index * 2 + 2) < arr.length ) {
 95       postOrder(2 * index + 2);
 96     }
 97     //輸出當前這個元素
 98     System.out.println(arr[index]);
 99   }
100 }

 

 

Tags:

VirMach 便宜 VPS