首頁 Java java教程 透過先序遍歷和中序遍歷後的序列還原二元樹

透過先序遍歷和中序遍歷後的序列還原二元樹

Jun 23, 2017 pm 03:36 PM
序列 透過 遍歷

當我們有一個

先序遍歷序列:1,3,7,9,5,11

中序遍歷序列:9,7,3,1,5, 11

我們可以很輕鬆的用筆寫出對應的二元樹。但是用程式碼又該如何實現?

下面我們來簡單談談基本想法。

首先,先序遍歷的順序是根據根-左孩子-右孩子 的順序遍歷的,那麼我們可以率先確認的是先序遍歷序列的第一個數字就是根節點,然後中序遍歷是根據左孩子-根-右孩子 的順序遍歷的。我們透過先序遍歷確認了根節點,那麼我們只需要在中序遍歷中找到根節點的位置,然後就可以很好地區分出,那些屬於左子樹的節點,那些是屬於右子樹的節點了。如下圖:

我們確定數字1為根節點,然後根據中序遍歷的遍歷順序確定,中序遍歷序列中數字1的左邊全部為左子樹節點,右邊全部為右子樹。透過左子樹節點的個數,得出先序遍歷序列中從根節點往後的連續3個數是屬於左子樹的,剩下的為右子樹。這樣再在左右子樹的序列中重複以上步驟,最後找到沒有子節點為止。

實作程式碼如下:

  1 package com.tree.traverse;  2   3 import java.util.ArrayList;  4 import java.util.List;  5   6 /**  7  * @author Caijh  8  *  9  * 2017年6月2日 下午7:21:10 10  */ 11  12 public class BuildTreePreOrderInOrder { 13  14     /**  15      *              1 
 16      *             / \ 17      *            3   5 
 18      *           /     \ 19      *          7       11 20      *       /  
 21      *      9       
 22      */   23     public static int treeNode = 0;//记录先序遍历节点的个数 24     private List<Node> nodeList = new ArrayList<>();//层次遍历节点的队列 25     public static void main(String[] args) { 26         BuildTreePreOrderInOrder build = new BuildTreePreOrderInOrder(); 27         int[] preOrder = { 1, 3, 7, 9, 5, 11}; 28         int[] inOrder = { 9, 7, 3, 1, 5, 11}; 29          30         treeNode = preOrder.length;//初始化二叉树的节点数 31         Node root = build.buildTreePreOrderInOrder(preOrder, 0, preOrder.length - 1, inOrder, 0, preOrder.length - 1); 32         System.out.print("先序遍历:"); 33         build.preOrder(root); 34         System.out.print("\n中序遍历:"); 35         build.inOrder(root); 36         System.out.print("\n原二叉树:\n"); 37         build.prototypeTree(root); 38     } 39  40     /** 41      * 分治法 42      * 通过先序遍历结果和中序遍历结果还原二叉树 43      * @param preOrder    先序遍历结果序列 44      * @param preOrderBegin     先序遍历起始位置下标 45      * @param preOrderEnd    先序遍历末尾位置下标 46      * @param inOrder    中序遍历结果序列 47      * @param inOrderBegin    中序遍历起始位置下标 48      * @param inOrderEnd     中序遍历末尾位置下标 49      * @return 50      */ 51     public Node buildTreePreOrderInOrder(int[] preOrder, int preOrderBegin, int preOrderEnd, int[] inOrder, int inOrderBegin, int inOrderEnd) { 52         if (preOrderBegin > preOrderEnd || inOrderBegin > inOrderEnd) { 53             return null; 54         } 55         int rootData = preOrder[preOrderBegin];//先序遍历的第一个字符为当前序列根节点 56         Node head = new Node(rootData); 57         int divider = findIndexInArray(inOrder, rootData, inOrderBegin, inOrderEnd);//找打中序遍历结果集中根节点的位置 58         int offSet = divider - inOrderBegin - 1;//计算左子树共有几个节点,节点数减一,为数组偏移量 59         Node left = buildTreePreOrderInOrder(preOrder, preOrderBegin + 1, preOrderBegin + 1 + offSet, inOrder, inOrderBegin,inOrderBegin + offSet); 60         Node right = buildTreePreOrderInOrder(preOrder, preOrderBegin + offSet + 2, preOrderEnd, inOrder, divider + 1, inOrderEnd); 61         head.left = left; 62         head.right = right; 63         return head; 64     } 65     /** 66      * 通过先序遍历找到的rootData根节点,在中序遍历结果中区分出:中左子树和右子树 67      * @param inOrder    中序遍历的结果数组 68      * @param rootData    根节点位置 69      * @param begin    中序遍历结果数组起始位置下标 70      * @param end    中序遍历结果数组末尾位置下标 71      * @return return中序遍历结果数组中根节点的位置 72      */ 73     public int findIndexInArray(int[] inOrder, int rootData, int begin, int end) { 74         for (int i = begin; i <= end; i++) { 75             if (inOrder[i] == rootData) 76                 return i; 77         } 78         return -1; 79     } 80     /** 81      * 二叉树先序遍历结果 82      * @param n 83      */ 84     public void preOrder(Node n) { 85         if (n != null) { 86             System.out.print(n.val + ","); 87             preOrder(n.left); 88             preOrder(n.right); 89         } 90     } 91     /** 92      * 二叉树中序遍历结果 93      * @param n 94      */ 95     public void inOrder(Node n) { 96         if (n != null) { 97             inOrder(n.left); 98             System.out.print(n.val + ","); 99             inOrder(n.right);100         }101     }102     /**103      * 还原后的二叉树104      * 二叉数层次遍历105      * 基本思想:106      *     1.因为推导出来的二叉树是保存在Node类对象的子对象里面的,(类似于c语言的结构体)如果通过递归实现层次遍历的话,不容易实现107      *     2.这里采用List队列逐层保存Node对象节点的方式实现对二叉树的层次遍历输出108      *     3.如果父节点的位置为i,那么子节点的位置为,2i 和 2i+1;依据这个规律逐层遍历,通过保存的父节点,找到子节点。并保存,不断向下遍历保存。109      * @param tree110      */111     public void prototypeTree(Node tree){112         //用list存储层次遍历的节点113         if(tree !=null){114             if(tree!=null)115                 nodeList.add(tree);116             nodeList.add(tree.left);117             nodeList.add(tree.right);118             int count=3;119             //从第三层开始120             for(int i=3;count<treeNode;i++){121                 //第i层第一个子节点的父节点的位置下标122                 int index = (int) Math.pow(2, i-1-1)-1;123                 /**124                  * 二叉树的每一层节点数遍历125                  * 因为第i层的最大节点数为2的i-1次方个,126                  */127                 for(int j=1;j<=Math.pow(2, i-1);){128                     //计算有效的节点的个数,和遍历序列的总数做比较,作为判断循环结束的标志129                     if(nodeList.get(index).left!=null)130                         count++;131                     if(nodeList.get(index).right!=null)132                         count++;133                     nodeList.add(nodeList.get(index).left);134                     nodeList.add(nodeList.get(index).right);135                     index++;136                     if(count>=treeNode)//当所有有效节点都遍历到了就结束遍历137                         break;138                     j+=2;//每次存储两个子节点,所以每次加2139                 }140             }141             int flag=0,floor=1;142             for(Node node:nodeList){143                 if(node!=null)144                     System.out.print(node.val+" ");145                 else146                     System.out.print("# ");//#号表示空节点147                 flag++;148                 /**149                  * 逐层遍历输出二叉树150                  * 
151                  */152                 if(flag>=Math.pow(2, floor-1)){153                     flag=0;154                     floor++;155                     System.out.println();156                 }157             }158         }159     }160     /**161      * 内部类162      * 1.每个Node类对象为一个节点,163      * 2.每个节点包含根节点,左子节点和右子节点164      */165     class Node {166         Node left;167         Node right;168         int val;169         public Node(int val) {170             this.val = val;171         }172     }173 }
登入後複製

執行結果:

最後逐層輸出二元樹的基本思想:
* 1.因為推導出來的二元樹是保存在Node類別物件的子物件裡面的,(類似於c語言的結構體)如果透過遞歸實作層次遍歷的話,不容易實作
* 2.這裡採用List佇列逐層保存Node物件節點的方式實作對二元樹的層次遍歷輸出
* 3.如果父節點的位置為i,那麼子節點的位置為,2i 和2i+1;依據這個規律逐層遍歷,透過保存的父節點,找到子節點。並保存,不斷向下遍歷保存。

以上是透過先序遍歷和中序遍歷後的序列還原二元樹的詳細內容。更多資訊請關注PHP中文網其他相關文章!

本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

Video Face Swap

Video Face Swap

使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱門文章

<🎜>:泡泡膠模擬器無窮大 - 如何獲取和使用皇家鑰匙
3 週前 By 尊渡假赌尊渡假赌尊渡假赌
北端:融合系統,解釋
3 週前 By 尊渡假赌尊渡假赌尊渡假赌
Mandragora:巫婆樹的耳語 - 如何解鎖抓鉤
3 週前 By 尊渡假赌尊渡假赌尊渡假赌

熱工具

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器

SublimeText3漢化版

SublimeText3漢化版

中文版,非常好用

禪工作室 13.0.1

禪工作室 13.0.1

強大的PHP整合開發環境

Dreamweaver CS6

Dreamweaver CS6

視覺化網頁開發工具

SublimeText3 Mac版

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)

熱門話題

Java教學
1665
14
CakePHP 教程
1423
52
Laravel 教程
1321
25
PHP教程
1269
29
C# 教程
1249
24
Java如何遍歷資料夾並取得所有檔案名 Java如何遍歷資料夾並取得所有檔案名 Mar 29, 2024 pm 01:24 PM

Java是一種流行的程式語言,具有強大的檔案處理功能。在Java中,遍歷資料夾並取得所有檔案名稱是一種常見的操作,可以幫助我們快速定位和處理特定目錄下的檔案。本文將介紹如何在Java中實作遍歷資料夾並取得所有檔案名稱的方法,並提供具體的程式碼範例。 1.使用遞歸方法遍歷資料夾我們可以使用遞歸方法遍歷資料夾,遞歸方法是一種自身呼叫自身的方式,可以有效地遍歷資料夾中

PHP glob()函數使用範例:遍歷指定資料夾中的所有文件 PHP glob()函數使用範例:遍歷指定資料夾中的所有文件 Jun 27, 2023 am 09:16 AM

PHPglob()函數使用範例:遍歷指定資料夾中的所有文件在PHP開發中,經常需要遍歷指定資料夾中的所有文件,以實現檔案批次操作或讀取。 PHP的glob()函數正是用來實現這種需求的。 glob()函數可以透過指定一個通配符匹配模式,來取得指定資料夾中符合條件的所有檔案的路徑資訊。在這篇文章中,我們將會示範如何使用glob()函數來遍歷指定資料夾中的所有文件

Java Iterator 與 Iterable 的深入比較:優缺點分析 Java Iterator 與 Iterable 的深入比較:優缺點分析 Feb 19, 2024 pm 04:20 PM

概念差異:Iterator:Iterator是一個接口,代表一個從集合中取得值的迭代器。它提供了MoveNext()、Current()和Reset()等方法,讓你遍歷集合中的元素,並對目前元素進行操作。 Iterable:Iterable也是一個接口,代表一個可迭代的物件。它提供了Iterator()方法,用於傳回一個Iterator對象,以便於遍歷集合中的元素。使用方式:Iterator:要使用Iterator,需要先取得一個Iterator對象,然後呼叫MoveNext()方法來移動到下一

如何使用Python實作二元樹的遍歷 如何使用Python實作二元樹的遍歷 Jun 09, 2023 pm 09:12 PM

作為一種常用的資料結構,二元樹經常被用來儲存資料、搜尋和排序。遍歷二元樹是非常常見的操作之一。 Python作為一種簡單易用的程式語言,有許多方法可以實作二元樹的遍歷。本文將介紹如何使用Python實現二元樹的前序、中序和後序遍歷。二元樹的基礎在學習二元樹的遍歷之前,我們需要先了解二元樹的基本概念。二元樹由節點組成,每個節點都有一個值和兩個子節點(左子節點和右子

Python 3.x 中如何使用os模組遍歷目錄中的文件 Python 3.x 中如何使用os模組遍歷目錄中的文件 Jul 29, 2023 pm 02:57 PM

Python3.x中如何使用os模組遍歷目錄中的檔案在Python中,我們可以使用os模組來進行檔案和目錄的操作。 os模組是Python標準庫中的重要模組,提供了許多和作業系統相關的功能。在本文中,我們將介紹如何使用os模組來遍歷一個目錄中的所有檔案。首先,我們需要導入os模組:importos接下來,我們可以使用os.walk()函數來遍歷目錄。

Java Iterator 與 Iterable:解鎖 Java 集合的強大力量 Java Iterator 與 Iterable:解鎖 Java 集合的強大力量 Feb 19, 2024 pm 07:00 PM

在Java中,集合(collection)是一組元素的集合,提供了統一的介面和方法來儲存、檢索和操作這些元素。 Iterator和Iterable是兩個重要的Java接口,它們提供了遍歷集合元素的通用機制。 Iterator介面定義了用於遍歷集合的hasNext()和next()方法。 hasNext()方法用於檢查集合中是否還有未遍歷的元素,next()方法用於傳回目前元素並將其移至下一個元素。 Iterable介面定義了iterator()方法,該方法傳回一個Iterator對象,用於遍歷集合中的元

在C++中遞歸插入和遍歷鍊錶 在C++中遞歸插入和遍歷鍊錶 Sep 10, 2023 am 09:21 AM

我們得到了用於形成鍊錶的整數值。任務是使用遞歸方法先插入然後遍歷單鍊錶。在末尾遞歸新增節點如果head為NULL→將節點加入head否則加入head(head→next)遞歸遍歷節點如果head為NULL→退出否則列印(head→next)範例輸入−1-2-7-9 -10輸出輸出strong>−鍊錶:1→2→7→9→10→NULL輸入−12-21-17-94-18輸出−鍊錶:12→21→17→94→18→NULL下面程式中使用的方法如下在這種方法中,我們將使用函數新增節點並遍歷單鍊錶並遞

Java Iterator與Iterable:集合遍歷的金鑰,揭開其神秘面紗 Java Iterator與Iterable:集合遍歷的金鑰,揭開其神秘面紗 Feb 20, 2024 am 10:27 AM

Iterator簡介Iterator是Java中用於遍歷集合的介面。它提供了一組方法,讓您以順序的方式存取集合中的元素。您可以使用Iterator來遍歷List、Set和Map等集合類型。示範程式碼:Listlist=newArrayList();list.add("one");list.add("two");list.add("three");Iteratoriterator=list.iterator();while(iter

See all articles