用前序中序創建二叉樹(用中序后序創建二叉樹)

定義二叉樹結點
在這里插入圖片描述
比如就拿這個二叉樹
在這里插入圖片描述

前序中序創建

因為前序遍歷的順序是 根 , 左 ,右。
中序的遍歷是 左 根 右。
我們會很不好想,但我們可以用前序和中序把上面那個二叉樹的遍歷一邊

	前序遍歷:ABDEHCFG中序遍歷:DBEHAFCG

然后根據這我們來想
創建的時候,值都是以數組的形式傳進來,所以找到根節點,前序和中序左子樹個數一定相等,都是r。
前序和中序創建左子樹的時候,挨個往后走就行,傳的數組長度也就是個數就是r,左子樹的個數,到右子樹時。此時左子樹創建完,所以前序要跳過r個元素,也就是創建左子樹的個數,并加上根節點,也就是r+1.,創建右子樹時個數就要減去根+左子樹的個數。中序也是如此。

在這里插入圖片描述
程序一開始,要先找到r的大小,也就是中序遍歷和前序遍歷時根結點的位置。
在這里插入圖片描述

中序后序創建

與之前的道理是相似的,先找到根節點所在位置,也就是左子樹個數
在這里插入圖片描述
然后找到根的值,也就是后序數組中的最后一個,然后道理相同,先左,再右
在這里插入圖片描述

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/383400.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/383400.shtml
英文地址,請注明出處:http://en.pswp.cn/news/383400.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

Epoll詳解及源碼分析

文章來源:http://blog.csdn.net/chen19870707/article/details/42525887 Author:Echo Chen(陳斌) Email:chenb19870707gmail.com Blog:Blog.csdn.net/chen19870707 Date:Jan.7th, 2015 1…

非遞歸實現二叉樹(前序,中序,后序)c/c++實現

這里還是用到棧的思想,為了方便用了c的一些內容,把出棧,進棧,讀棧頂元素用一個個函數封裝起來了,前面做了一些處理來使用這些函數。 前序非遞歸 思想:一直走左邊,依次進棧。等左邊為空的時候&…

Linux 中統計一個進程的線程數

如果你想看到 Linux 中每個進程的線程數,有以下幾種方法可以做到這一點。 方法一: /proc proc 偽文件系統,它駐留在 /proc 目錄,這是最簡單的方法來查看任何活動進程的線程數。 /proc 目錄以可讀文本文件形式輸出,提供現有進程和系…

Linux_linux基礎命令(增刪查,權限,Linux下的重要目錄,重要命令(. du, df, top, free, pstack, su, sudo).安裝gcc/g++, gdb, vim )

r:表示可讀w:表示可寫x:表示可執行也可以用數字表示這一點我們會在修改文件權限說明。對于文件夾的rwx表示:r表示可讀及可以查看文件夾內容可以ls查看w表示可寫及可以向文件夾中傳送內容如文件x表示可執行及可以向文件夾中可以cd進…

pthread_create會導致內存泄露

這幾天一直在調試一個系統,系統的功能就是定時發送數據、接收數據然后解析收到的數據,轉換成一定的格式存入數據庫中。我為了并發操作,所以每接收到一個數據包,就調用pthread_create函數創建一個默認屬性的線程進行處理。 系統…

Linux_linux常用工具之make/makefile詳解

make/makefile make/makefile: 項目自動化構建工具 makefile:普通文本文件,記錄了項目的構建流程規則。 make: 一個解釋程序,到當前執行make命令的目錄下尋找makefile文件,并且對makefile 中記錄的項目構建規則進行解釋執行。makefile: 編寫…

Linux_linux常用工具(git,vim ,gcc ,gdb,權限)超詳解

git :項目版本控制工具 項目克隆:git clone項目提交:git add(本地倉庫提交) git commit -m “bak msg”(-m 備注信息)同步到服務器:git push origin master(提交到主分支&…

T20調試札記

最近在調試T20的內存,使用的指令在此記錄一下 1. pmap指令查看指定進程中的內存分布。該指令需要在busybox中開啟 pmap -x 111 2.應用與so需要執行strip操作,可以減小存儲空間的大小 mips-linux-gnu-strip libsysutils.so 3.nm指令和file指令可以查…

samba 2.2.7a 編譯

今天在君正T20上編譯samba 2.2.7a 遇到了一些問題,特此記錄一下 1.自己寫一個build.sh腳本,方便后續的再次編譯 #!/bin/sh # export CFLAGS"-O2 -muclibc" export CPPFLAGS"-O2 -muclibc" export CXXFLAGS"-O2 -muclibc&qu…

Linux_linux常用工具------進度條程序

緩沖區對文件讀寫的影響:數據并沒有直接寫入文件,而是寫入到緩沖區(內存)中,等到緩沖區中數據寫滿或者刷新緩沖區的時候,才會將數據真正的寫入文件 fflush(stdout)刷新。 回車與換行…

Ubuntu下QT的安裝詳細教程

本文轉自:http://blog.chinaunix.net/uid-7945126-id-4987195.html 經測試完美解決 ------------------------------------------------------------- 最近需要在Ubuntu下開發桌面軟件,想起了QT。書上介紹的方法太老了,網上找了一大堆安裝方法…

Linux_linux常用工具---閑雜篇(除了vim, 還有哪些常用的牛逼的編輯器, 并能夠橫向對比編輯器之間的區別和優缺點.)

vim自行查找資料, 自行配置插件. 借鑒別人的 " 顯示相關 “”""""""""""""""""""""""""""""""""&…

ubuntu14.04下安裝qt4.8.6 +qt creator

原創作品,允許轉載,轉載時請務必以超鏈接形式標明文章 原始出處 、作者信息和本聲明。否則將追究法律責任。http://248341.blog.51cto.com/238341/1438867以前安裝時沒太注意,安裝qt后發現在qt creator下無法輸入中文,或者中文無法…

網絡基礎一(協議的概念,網絡應用程序設計模式)

協議的概念 什么是協議? 從應用的角度出發,協議可理解為“規則”,是數據傳輸和數據的解釋的規則。 假設,A、B雙方欲傳輸文件。規定: 第一次,傳輸文件名,接收方接收到文件名,應答OK…

ubuntu修改root密碼

sudo passwd root [sudo] password for you :---> 輸入你的密碼,不會顯示 Enter new UNIX password: --- > 設置root 密碼 Retype new UNIX password: --> 重復

linux 消息隊列機制

現在我們來討論第三種也是最后一種System V IPV工具:消息隊列。在許多方面看來,消息隊列類似于有名管道,但是卻沒有與打開與關閉管道的復雜關聯。然而,使用消息隊列并沒有解決我們使用有名管道所遇到的問題,例如管道上…

堆(概念,數據結構中堆與內存堆區的區別 ,堆的基本操作)

堆的特性: 必須是完全二叉樹 用數組實現 任一結點的值是其子樹所有結點的最大值或最小值 最大值時,稱為“最大堆”,也稱大根堆; 在完全二叉樹中,任何一個子樹的最大值都在這個子樹的根結點。最小值時,稱為…

makefile中的shell調用---注意事項

在之前一次編寫makfile時候,有看到相關的makefile中使用$$來引用變量,而且嘗試后發現$$使用居然和${}有類似的功能。當時也沒具體追究相關的用法,當然剛才所說的都是錯誤的觀念 $$:在makefile中會被替換成一個$。 相關資料是這么描…

網絡基礎2(分層模型,通信過程,以太網,ARP協議格式和具體功能詳解)

分層模型 OSI七層模型 OSI模型 1 物理層:主要定義物理設備標準,如網線的接口類型、光纖的接口類型、各種傳輸介質的傳輸速率等。它的主要作用是傳輸比特流(就是由1、0轉化為電流強弱來進行傳輸,到達目的地后再轉化為1、0&#…

為github帳號添加SSH keys

使用git clone命令從github上同步github上的代碼庫時,如果使用SSH鏈接(如我自己的beagleOS項目:gitgithub.com:DamonDeng/beagleOS.git),而你的SSH key沒有添加到github帳號設置中,系統會報下面的錯誤&…