二叉樹交換左右子樹遞歸以及非遞歸演算法

来源:https://www.cnblogs.com/ucas-2023-An/archive/2022/11/20/16909250.html
-Advertisement-
Play Games

遞歸方式基本思想: 1、當待處理節點非空時,判斷其左右孩子是否不同時為空:若是,轉到2、否則分別遞歸調用左右子樹進行操作。 2、新建一個輔助結點,執行交換操作。 3、遞歸調用非空的左右子樹進行操作。 BiTree *exchangeChild(BiTree *&T){ if(T==null) ret ...


遞歸方式基本思想:

  • 1、當待處理節點非空時,判斷其左右孩子是否不同時為空:若是,轉到2、否則分別遞歸調用左右子樹進行操作。
  • 2、新建一個輔助結點,執行交換操作。
  • 3、遞歸調用非空的左右子樹進行操作。
BiTree *exchangeChild(BiTree *&T){
	if(T==null) return null;//當結點為null直接return null
	if(T->lchild!=null||T->rchild!=null){//當待處理結點左右孩子不同時為空時交換
		BiTNode *temp=T->lchild;//輔助結點,用於交換
		T->lchild=T->rchild;
		T->rchild=temp;
	}
	//遞歸交換左右子樹
	exchangeChild(T->lchild);
	exchangeChild(T->rchild);
	return T;
}

非遞歸方式基本思想:

需要利用隊列進行操作:

  • 1、當待處理結點非空時入隊。
  • 2、當隊非空時,轉到3、,否則代表操作完成,直接return 根結點。
  • 3、隊頭元素出隊,判斷其左右孩子是否不同時為空:若是,轉到4、否則將非空的左右孩子依次入隊,執行2、。
  • 4、新建一個輔助結點,執行交換操作。並將非空的左右孩子依次入隊,執行2、。
BiTree *exchangeChild(BiTree *&T){
	BiTNode *temp;              //輔助結點,用於交換結點
	InitQueue(Q);               //利用隊列實現,初始化隊列
	if(T!=null) EnQueue(Q,T);   //當結點不為空時入隊
	while(!IsEmpty(Q)){         //當隊非空時
		DeQueue(Q,T);       //隊首元素出隊
		if(T->lchild!=null||T->rchild!=null){//當隊首元素的左右孩子不同時為空時執行交換操作
			temp=T->lchild;
			T->lchild=T->rchild;
			T->rchild=temp;
		}
		//對非空的孩子結點入隊,繼續執行上述操作
		if(T->lchild!=null){
			EnQueue(Q,T->lchild);
		}
		if(T->rchild!=null){
			EnQueue(Q,T->rchild);
		}
	}
	return T;//返回根結點
}
                             若有錯誤,歡迎指正
                              我們一起進步!


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • C++的運算符重載:使對象的運算表現得和編譯器內置類型一樣 如下代碼,如果T是整形,那很好理解,但是如果 T 是一個 Student 類, a + b ?怎麼操作,兩個學生類怎麼相加? 這個就是我們要說的運算符重載問題 template T sum(T a,T b){ return a + b; / ...
  • 一般,做資料庫表設計時,很多情況下,我們都至少需要一個日期欄位來記錄操作相關。 而這種表示日期的欄位,我們使用 datetime 類型比較多,但是如果使用 datetime 類型,直接前端拿日期時,我們會發現拿到日期格式是 2022-11-20T11:10:00.000+00:00 這種的,但我們一 ...
  • C++ 讀取文件及保留小數方法 做圖論作業時,需要從文件中讀取整型數據。之前都是在標準輸入輸出流中讀取和輸出。今小記一下。 讀取文件 使用文件流ifstream 最簡潔的方法是使用文件流: ifstream infile(filename) 假設 test.txt 文件中存放5 6: ifstrea ...
  • 一.小結 1.電腦是儲存和處理數據的電子設備 2.電腦包括硬體和軟體兩個部分 3.硬體是電腦中可以看見的物理部分 4.電腦程式,也就是通常所說的軟體,是一些看不見的指令,它們控制硬體完成任務 5.電腦程式設計就是編寫電腦執行的指令(即代碼) 6.中央處理器(CPU)是電腦的大腦。它是內 ...
  • 接上回,聊聊函子 functor。 functor 是一個容器。該容器的 value 屬性指向被包裹的數據;該容器的 map 方法對容器進行映射變換。 以下代碼實現一個最普通的 functor,稱之為 Just, 根據 map 的傳參 fn 對 value 進行變換: class Just<T> { ...
  • 指定ID 在類中聲明並定義按鈕控制項的起始ID,以控制項的類型和功能對動態控制項ID進行分組,每組最好定義一個自己的起始ID方便管理: #define IDC_CONTROL_START 1000 #define IDC_BTN_START IDC_CONTROL_START+100 #define ID ...
  • 以python 3為例關於迴圈中經常出現賦值問題的幾個形式(要賦值的變數a,迴圈變數b)就比如for i in range(n): 相對於b來說 1:a += b 是對每次b在迴圈過程中的值進行求和,每次迴圈中b與b之間沒有聯繫 2:b += b 是將每次b的值繼續帶入下一次迴圈中,會對下一次迴圈的 ...
  • 1.1 冪等性的概念 Methods can also have the property of "idempotence" in that (aside from error or expiration issues) the side-effects of N > 0 identical req ...
一周排行
    -Advertisement-
    Play Games
  • 隨著Aspire發佈preview5的發佈,Microsoft.Extensions.ServiceDiscovery隨之更新, 服務註冊發現這個屬於老掉牙的話題解決什麼問題就不贅述了,這裡主要講講Microsoft.Extensions.ServiceDiscovery(preview5)以及如何 ...
  • 概述:通過使用`SemaphoreSlim`,可以簡單而有效地限制非同步HTTP請求的併發量,確保在任何給定時間內不超過20個網頁同時下載。`ParallelOptions`不適用於非同步操作,但可考慮使用`Parallel.ForEach`,儘管在非同步場景中謹慎使用。 對於併發非同步 I/O 操作的數量 ...
  • 1.Linux上安裝Docken 伺服器系統版本以及內核版本:cat /etc/redhat-release 查看伺服器內核版本:uname -r 安裝依賴包:yum install -y yum-utils device-mapper-persistent-data lvm2 設置阿裡雲鏡像源:y ...
  • 概述:WPF界面綁定和渲染大量數據可能導致性能問題。通過啟用UI虛擬化、非同步載入和數據分頁,可以有效提高界面響應性能。以下是簡單示例演示這些優化方法。 在WPF中,當你嘗試綁定和渲染大量的數據項時,性能問題可能出現。以下是一些可能導致性能慢的原因以及優化方法: UI 虛擬化: WPF提供了虛擬化技術 ...
  • 引言 上一章節介紹了 TDD 的三大法則,今天我們講一下在單元測試中模擬對象的使用。 Fake Fake - Fake 是一個通用術語,可用於描述 stub或 mock 對象。 它是 stub 還是 mock 取決於使用它的上下文。 也就是說,Fake 可以是 stub 或 mock Mock - ...
  • 為.net6在CentOS7上面做準備,先在vmware虛擬機安裝CentOS 7.9 新建CentOS764位的系統 因為CentOS8不更新了,所以安裝7;簡單就一筆帶過了 選擇下載好的操作系統的iso文件,下載地址https://mirrors.aliyun.com/centos/7.9.20 ...
  • 經過前面幾篇的學習,我們瞭解到指令的大概分類,如:參數載入指令,該載入指令以 Ld 開頭,將參數載入到棧中,以便於後續執行操作命令。參數存儲指令,其指令以 St 開頭,將棧中的數據,存儲到指定的變數中,以方便後續使用。創建實例指令,其指令以 New 開頭,用於在運行時動態生成並初始化對象。方法調用指... ...
  • LiteDB 是一個輕量級的嵌入式 NoSQL 資料庫,其設計理念與 MongoDB 類似,但它是完全使用 C# 開發的,因此與 C# 應用程式的集成非常順暢。與 SQLite 相比,LiteDB 提供了 NoSQL(即鍵值對)的數據存儲方式,並且是一個開源且免費的項目。它適用於桌面、移動以及 We ...
  • 1 開源解析和拆分文檔 第三方的工具去對文件解析拆分,去將我們的文件內容給提取出來,並將我們的文檔內容去拆分成一個小的chunk。常見的PDF word mark down, JSON、HTML。都可以有很好的一些模塊去把這些文件去進行一個東西去提取。 優勢 支持豐富的文檔類型 每種文檔多樣化選擇 ...
  • OOM是什麼?英文全稱為 OutOfMemoryError(記憶體溢出錯誤)。當程式發生OOM時,如何去定位導致異常的代碼還是挺麻煩的。 要檢查OOM發生的原因,首先需要瞭解各種OOM情況下會報的異常信息。這樣能縮小排查範圍,再結合異常堆棧、heapDump文件、JVM分析工具和業務代碼來判斷具體是哪 ...