二叉樹先、中、后遍歷遞歸+非遞歸-創(chuàng)新互聯(lián)

• 二叉樹的創(chuàng)建：采用先序遍歷的順序，依次寫出每個非空節(jié)點的數(shù)值，如果沒有孩子節(jié)點就用$符號代替。并采用遞歸的方式進(jìn)行實現(xiàn)，依次創(chuàng)建根節(jié)點、所有的左子樹、右子樹
• 二叉樹的前、中、后序的遞歸遍歷：本質(zhì)上的遍歷順序都是一樣的，只是打印的時機不同，控制好打印的時機即可。

1. 棧s初始化；
2. 循環(huán)直到p為空且棧s為空
   • 當(dāng)p不空時循環(huán)
     • 輸出p->data;
     • 將指針p的值保存到棧中；
     • 繼續(xù)遍歷p的左子樹
   • 當(dāng)p為空，棧s不空，則
     • 將棧頂元素彈出至p；
     • 準(zhǔn)備遍歷p的右子樹；
       

1. 棧s初始化；
2. 訪問左孩子，左孩子存在繼續(xù)步驟1；
3. 左孩子不存在彈出函數(shù)棧幀；
4. 訪問右孩子，右孩子存在繼續(xù)步驟1；
5. 右孩子不存在彈出函數(shù)棧幀，訪問該節(jié)點；
6. 彈出函數(shù)棧幀，返回上一級函數(shù)棧幀。

• 從當(dāng)前節(jié)點開始遍歷：
  1. 若當(dāng)前節(jié)點存在，就存入棧中，并且置節(jié)點flag為1（第一次訪問），然后訪問其左子樹；
  2. 直到當(dāng)前節(jié)點不存在，需要回退，這里有兩種情況：
     • 當(dāng)棧頂節(jié)點flag為0時，則表明是從左子樹回退，這時需置棧頂節(jié)點flag為2（第二次訪問），然后通過棧頂節(jié)點訪問其右子樹（取棧頂節(jié)點用，但不出棧）
     • 當(dāng)棧頂節(jié)點flag為1時，則表明是從右子樹回退，這時需出棧，并取出棧節(jié)點做訪問輸出。
  3. 不斷重復(fù)12，直到當(dāng)前節(jié)點不存在且?？铡?/li>

• 從上到下，從左到右，則利用隊列存放各子樹結(jié)點的指針，初始時把根節(jié)點入隊，當(dāng)根結(jié)點出隊后，令其左、右孩子結(jié)點入隊（空不入隊），而左孩子出隊時又令它的左右孩子結(jié)點入隊，……由此便可產(chǎn)生按層次輸出的效果。
  

#pragma once
#includeusing namespace std;
typedef char E;
typedef struct TreeNode {E element;
	struct TreeNode* left, * right;
	// 在后序遍歷時，需要左右子樹都被遍歷才行，0表示左子樹遍歷完成，1表示右子樹遍歷完成
	int flag;//標(biāo)志遍歷的狀態(tài)。
}*Node;

//棧
typedef Node T;//二叉樹節(jié)點指針
typedef struct StackNode {T element;
	struct StackNode* next;
} *SNode;

//隊列
typedef struct QueueNode {T element;
	struct QueueNode* next;
}*QNode;

typedef struct Queue {QNode front, rear;
}*LinkedQueue;

Node createBiTree(Node& root);//按照先序順序創(chuàng)建二叉樹

void preOrder(Node root);//遞歸方式進(jìn)行先序遍歷
void inOrder(Node root);//遞歸方式進(jìn)行中序遍歷
void postOrder(Node root);//遞歸方式進(jìn)行后序遍歷

//棧操作
void initStack(SNode head);//初始化棧
int pushStack(SNode head, T element);//入棧
int IsEmpty(SNode head);//判斷棧是否為空
T peekStack(SNode head);//獲取棧頂元素值
T popStack(SNode head);//出棧

void preOrder2(Node root);//非遞歸先序遍歷
void inOrder0(Node root);//非遞歸中序遍歷 低級版
void inOrder2(Node root);//非遞歸中序遍歷 升級版
void postOrder2(Node root);//非遞歸后序遍歷

//隊列操作
int initQueue(LinkedQueue queue);//初始化隊列
int offerQueue(LinkedQueue queue, T element);//入隊列
int isEmpty(LinkedQueue queue);//隊列判空
T pollQueue(LinkedQueue queue);//出隊
void levelOrder(Node root);//層序遍歷
int getDepthTreeNode(Node root);//求二叉樹的深度

#include"MyBinaryTree.h"

//創(chuàng)建二叉樹
//注意采用引用的方式，避免淺拷貝的報錯
//Program received signal SIGSEGV, Segmentation fault
Node createBiTree(Node& root) {char ch;
	cin >>ch;
	if (ch == '$') {root = NULL;
	}
	else {root = (Node)malloc(sizeof(struct TreeNode));
		root->element = ch;
		createBiTree(root->left);//構(gòu)建左子樹
		createBiTree(root->right);//構(gòu)建右子樹
	}
	return root;
}

//遞歸方式進(jìn)行先序遍歷
void preOrder(Node root) {if (root != NULL) {cout<< root->element<< " ";
		preOrder(root->left);
		preOrder(root->right);
	}
}

//遞歸方式進(jìn)行中序遍歷
void inOrder(Node root) {if (root == NULL) return;
	inOrder(root->left);
	cout<< root->element<< " ";
	inOrder(root->right);
}

//遞歸方式進(jìn)行后序遍歷
void postOrder(Node root) {if (root == NULL) return;
	postOrder(root->left);
	postOrder(root->right);
	cout<< root->element<< " ";
}

//初始化棧
void initStack(SNode head) {head->next = NULL;
}

//入棧
int pushStack(SNode head, T element) {SNode node = (SNode)malloc(sizeof(struct StackNode));
	if (node == NULL) return 0;
	node->next = head->next;
	node->element = element;//element都是節(jié)點
	head->next = node;
	return true;
}

//判空
int IsEmpty(SNode head) {return head->next == NULL;
}

//用于獲取棧頂元素的值，但是不出棧,僅僅是值獲取
T peekStack(SNode head) {return head->next->element;//返回棧中的首節(jié)點的地址
}

//出棧
T popStack(SNode head) {SNode top = head->next;
	head->next = head->next->next;
	T e = top->element;
	free(top);
	return e;
}

//非遞歸實現(xiàn)
//先序遍歷
void preOrder2(Node root) {struct StackNode stack;
	initStack(&stack);
	//兩個條件，只有當(dāng)棧為空并且節(jié)點為NULL時才終止循環(huán)
	while (root || !IsEmpty(&stack)) {//先不斷遍歷左子樹，直到?jīng)]有為止
		while (root) {	cout<< root->element<< " ";//然后打印當(dāng)前節(jié)點的元素值
			pushStack(&stack, root);//每遇到一個節(jié)點，就將節(jié)點入棧
			root = root->left;//繼續(xù)遍歷下一個左孩子節(jié)點
		}
		Node node = popStack(&stack);//經(jīng)過前邊的遍歷，明確左子樹全部走完了，就進(jìn)行右子樹的遍歷
		//得到右孩子，如果有右孩子，下一輪會重復(fù)上面的步驟；如果沒有右孩子，那么這里的root就會變成null，
		// 下一輪開始會直接跳過上面的while，繼續(xù)出棧下一個節(jié)點，再找右子樹
		root = node->right;
	}
}
//中序遍歷二叉樹的非遞歸算法:沒有讓空指針進(jìn)棧
void inOrder2(Node root) {struct StackNode stack;
	initStack(&stack);
	//兩個條件，只有當(dāng)棧為空并且節(jié)點為NULL時才終止循環(huán)
	while (root || !IsEmpty(&stack)) {//先不斷遍歷左子樹，直到?jīng)]有為止
		while (root) {	pushStack(&stack, root);//每遇到一個節(jié)點，就將節(jié)點入棧
			root = root->left;//繼續(xù)遍歷下一個左孩子節(jié)點
		}
		Node node = popStack(&stack);//經(jīng)過前邊的遍歷，明確左子樹全部走完了，就進(jìn)行右子樹的遍歷
		cout<< node->element<< " ";//然后打印當(dāng)前節(jié)點的元素值
		//得到右孩子，如果有右孩子，下一輪會重復(fù)上面的步驟；如果沒有右孩子，那么這里的root就會變成null，
		// 下一輪開始會直接跳過上面的while，繼續(xù)出棧下一個節(jié)點，再找右子樹
		root = node->right;
	}
}
//中序遍歷二叉樹的非遞歸算法:讓空指針進(jìn)棧
void inOrder0(Node root) {struct StackNode stack;
	initStack(&stack);
	T p;
	pushStack(&stack, root);//根指針入棧
	while (!IsEmpty(&stack)) {//有棧頂元素 ，并且節(jié)點不為NULL
		while ((p = peekStack(&stack)) && p) {	pushStack(&stack, p->left);//向左走到盡頭
		}
		//直到左孩子為NULL,此時棧頂為整棵樹最左邊的節(jié)點，將NULL進(jìn)棧，循環(huán)結(jié)束
		//彈出棧頂空節(jié)點NULL ，因為子孩子為NULL,不需要打印值
		p = popStack(&stack);//空指針退棧
		if (!IsEmpty(&stack)) {//棧不為空，訪問節(jié)點，向右一步
			//彈出最上面的節(jié)點 ，也就是邏輯中序第一個節(jié)點
			p = popStack(&stack);
			cout<< p->element<< " ";
			pushStack(&stack, p->right);
			//如果有右孩子，則右孩子進(jìn)棧，，接著以右孩子為邏輯根節(jié)點來中序遍歷，判斷右孩子是否有左孩子和右孩子....
			//如果沒有右孩子，就將NULL壓進(jìn)棧，下次循環(huán)會被彈出并不打印
		}
	}
}

//后序遍歷
void postOrder2(Node root) {struct StackNode stack;
	initStack(&stack);
	while (root || !IsEmpty(&stack)) {while (root) {	pushStack(&stack, root);
			root->flag = 0;//首次入棧，只能代表左子樹遍歷完成，所以設(shè)置flag為0
			root = root->left;
		}
		root = peekStack(&stack);//獲取節(jié)點
		if (root->flag == 0) {//如果僅僅遍歷左子樹，那么flag就等于0
			root->flag = 1;//此時標(biāo)記為1表示遍歷右子樹
			root = root->right;
		}
		else {	cout<< root->element<< " ";//當(dāng)flag為1時，表示左右都遍歷完成，這時再將值打印出來
			popStack(&stack);//這時再把對應(yīng)的節(jié)點出棧，因為左右都遍歷完了
			root = NULL;//置NULL，下一輪直接跳過while，然后繼續(xù)取棧中剩余的節(jié)點，重復(fù)上述操作
		}
	}
}

//初始化對列
int initQueue(LinkedQueue queue) {//設(shè)置頭節(jié)點，并將隊頭和隊尾同時指向頭節(jié)點
	QNode node = (QNode)malloc(sizeof(struct QueueNode));
	if (node == NULL) return 0;
	queue->front = queue->rear = node;
	return true;
};

//入隊
int offerQueue(LinkedQueue queue, T element) {//入隊，將新的節(jié)點入隊放在隊尾，并修改rear的指向
	QNode node = (QNode)malloc(sizeof(struct QueueNode));
	if (node == NULL) return 0;
	node->element = element;
	queue->rear->next = node;
	queue->rear = node;
	return true;
}

//判空
int isEmpty(LinkedQueue queue) {//當(dāng)隊頭和隊尾指針同時指向同一個節(jié)點時，說明隊列為空隊列
	return queue->front == queue->rear;
}

//出隊
T pollQueue(LinkedQueue queue) {//queue->front —— 頭節(jié)點
	//queue->front->next->element --隊頭結(jié)點中存儲的節(jié)點的地址
	T e = queue->front->next->element;
	//queue->front->next --隊頭
	QNode qNode = queue->front->next;
	//更新鏈隊列頭節(jié)點
	queue->front->next = queue->front->next->next;
	//qNode=qNode->next;
	//如果隊列中只有一個節(jié)點，將隊尾指針指向設(shè)置好的頭節(jié)點
	if (queue->rear == qNode) queue->rear = queue->front;
	free(qNode);
	//返回刪除的舊的隊頭節(jié)點的節(jié)點地址，并沒有物理刪除，只是釋放隊列的節(jié)點空間
	return e;
}

//層序遍歷
void levelOrder(Node root) {struct Queue queue;//創(chuàng)建隊列
	initQueue(&queue);
	offerQueue(&queue, root);//先把根節(jié)點入隊
	while (!isEmpty(&queue)) {Node node = pollQueue(&queue);
		cout<< node->element<< " ";
		if (node->left) //如果左、右孩子,依次將左、右孩子入隊
			offerQueue(&queue, node->left);
		if (node->right)
			offerQueue(&queue, node->right);
	}
}

//求二叉樹的深度
int getDepthTreeNode(Node root) {if (root == NULL) {return 0;
	}
	else {int lLength = getDepthTreeNode(root->left);
		int rlength = getDepthTreeNode(root->right);
		int max = rlength >lLength ? (rlength + 1) : (lLength + 1);
		return max;
	}
};

#include"MyBinaryTree.h"
int main() {cout<< "1--創(chuàng)建二叉樹"<< endl;
	cout<< "2--先序遍歷二叉樹【遞歸方式】"<< endl;
	cout<< "3--中序遍歷二叉樹【遞歸方式】"<< endl;
	cout<< "4--后序遍歷二叉樹【遞歸方式】"<< endl;
	cout<< "5--先序遍歷二叉樹【非遞歸方式】"<< endl;
	cout<< "6--中序遍歷二叉樹【非遞歸方式1】"<< endl;
	cout<< "7--中序遍歷二叉樹【非遞歸方式2】"<< endl;
	cout<< "8--后序遍歷二叉樹【非遞歸方式】"<< endl;
	cout<< "9--層序遍歷二叉樹"<< endl;
	cout<< "10--求二叉樹的深度"<< endl;
	cout<< "-1--退出"<< endl;
	int option;
	Node t;//定義一個Node的指針
	t = NULL;//不進(jìn)行初識，就會報錯
	do {cout<< "請輸入選擇:";
		cin >>option;
		switch (option)
		{case 1:
			cout<< "請按先序輸入二叉樹中節(jié)點的值(一個字符)$字符表示空樹:";
			t = createBiTree(t);
			if (t) {		cout<< "創(chuàng)建二叉樹成功！"<< endl;
			}
			break;
		case 2:
			cout<< "前序遍歷【遞歸實現(xiàn)】:";
			preOrder(t);
			cout<< endl;
			break;
		case 3:
			cout<< "中序遍歷二叉樹【遞歸方式】";
			inOrder(t);
			cout<< endl;
			break;
		case 4:
			cout<< "后序遍歷二叉樹【遞歸方式】";
			postOrder(t);
			cout<< endl;
			break;
		case 5:
			cout<< "先序遍歷二叉樹【非遞歸方式】";
			preOrder2(t);
			cout<< endl;
			break;
		case 6:
			cout<< "中序遍歷二叉樹【非遞歸方式1】";
			inOrder0(t);
			cout<< endl;
			break;
		case 7:
			cout<< "中序遍歷二叉樹【非遞歸方式2】";
			inOrder2(t);
			cout<< endl;
			break;
		case 8:
			cout<< "后序遍歷二叉樹【非遞歸方式】";
			postOrder2(t);
			cout<< endl;
			break;
		case 9:
			cout<< "層序遍歷二叉樹【非遞歸實現(xiàn)】";
			levelOrder(t);
			cout<< endl;
			break;
		case 10:
			cout<< "二叉樹的深度為:";
			cout<< getDepthTreeNode(t)<< endl;
			break;
		case -1:
			cout<< "謝謝使用！再見！"<< endl;
			return 0;
		default:
			cout<< "請輸入正確的操作！";
			break;
		}

	} while (option != -1);
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)站欄目：二叉樹先、中、后遍歷遞歸+非遞歸-創(chuàng)新互聯(lián)
URL鏈接：http://bm7419.com/article10/dpdhgo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站收錄、品牌網(wǎng)站設(shè)計、網(wǎng)站制作、網(wǎng)站改版、響應(yīng)式網(wǎng)站、外貿(mào)建站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)