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

在這里插入圖片描述
這里還是用到棧的思想,為了方便用了c++的一些內容,把出棧,進棧,讀棧頂元素用一個個函數封裝起來了,前面做了一些處理來使用這些函數。
在這里插入圖片描述

前序非遞歸

在這里插入圖片描述

思想:一直走左邊,依次進棧。等左邊為空的時候,返回,也就是讀棧頂元素,讀一個出一個,并讓cur指向它的右邊,把它的右邊的結點當作根結點,再走一邊上面的過程。
在這里插入圖片描述

中序非遞歸

前序是在訪問根結點時打印,中序是先訪問左結點,所以在指向左結點時打印,也就是一直往左走依次入棧,走到頭返回讀棧頂元素并出棧時打印就行,然后cur等于當前棧頂元素的右子樹,再把這個結點當根結點,再走一邊這樣的過程。
在這里插入圖片描述

后序非遞歸

在這里插入圖片描述
比較難想,要有一個指針last指向上一次操作完整遍歷完的樹的結點也就是這個結點是當前最底下的那個結點。
一直往左并入棧,走到頭把top指上去,如果top的右邊為空,打印并出棧,否則看右邊是不是last如果是也打印出棧,
否則沒有跑到右邊最后一個,(如果跑到了,肯定是打印出棧,最后一個就變了)。cur就等于當前棧頂元素的右子樹。

在這里插入圖片描述

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

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

相關文章

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帳號設置中,系統會報下面的錯誤&…

網絡基礎3(IP段格式,UDP數據報格式,TCP數據報格式)

IP段格式 IP數據報的首部長度和數據長度都是可變長的,但總是4字節的整數倍。 對于IPv4,4位版本字段是4。4位首部長度的數值是以4字節為單位的,最小值為5,也就是說首部長度最小是4x520字節,也就是不帶任何選項的IP首部…

Linux 開發路線

Linux 開發路線: 使用 linux—〉linxu 系統編程開發---〉驅動開發和分析 linux 內核 開始學 linux 內核:最好有三件寶物:《深入理解 linux 內核》《LINUX內核源代碼情景分析》和源代碼。 《深》是綱,《情》是目。最后深入代碼 Linux 內核原理:比較淺顯…