快捷導(dǎo)航

C++簡(jiǎn)單又輕松建立鏈?zhǔn)蕉鏄?shù)流程

更新時(shí)間：2022年06月07日 09:30:13 作者：葉落秋白

二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是指，用鏈表來(lái)表示一棵二叉樹(shù)，即用鏈來(lái)指示元素的邏輯關(guān)系。通常的方法是鏈表中每個(gè)結(jié)點(diǎn)由三個(gè)域組成，數(shù)據(jù)域和左右指針域，左右指針?lè)謩e用來(lái)給出該結(jié)點(diǎn)左孩子和右孩子所在的鏈結(jié)點(diǎn)的存儲(chǔ)地址

遞歸建立二叉樹(shù)

二叉樹(shù)的結(jié)構(gòu)體

typedef struct Node
{
	int data;
	Node* lchild;
	Node* rchild;
}BiNode,*BiTree;

二叉樹(shù)顧名思義最多只有兩個(gè)子結(jié)點(diǎn)和一個(gè)數(shù)據(jù)域，既然是鏈?zhǔn)侥敲醋咏Y(jié)點(diǎn)定義為結(jié)點(diǎn)指針類(lèi)型，數(shù)據(jù)域就可以根據(jù)需要設(shè)置了，可以是整型也可以是字符型。

二叉樹(shù)初始化

BiTree createBiTree(BiTree &T)
{
	int d;
	cin >> d;
	if (d == 0)
	    T = NULL;
	else
	{
		T = (BiTree)malloc(sizeof(BiNode));
		T->data = d;
		T->lchild = createBiTree(T->lchild);
		T->rchild = createBiTree(T->rchild);
	}
	return T;
}

這個(gè)初始化函數(shù)的返回值為BiTree是一個(gè)結(jié)構(gòu)體指針類(lèi)型，用來(lái)返回初始化后的 T 二叉樹(shù)；整型數(shù)據(jù)d是用來(lái)給二叉樹(shù)的結(jié)點(diǎn)賦值的，當(dāng)輸入0的時(shí)候，該結(jié)點(diǎn)為空結(jié)點(diǎn)；當(dāng)結(jié)點(diǎn)的數(shù)據(jù)域不為零，給該結(jié)點(diǎn)動(dòng)態(tài)分配內(nèi)存空間，并把d賦值給T->data；然后就是對(duì)左右子樹(shù)的遞歸初始化了。

先序遍歷

void PreOrder(BiTree T)//先序
{
	if (T)
	{
		cout << T->data<<" ";
		PreOrder(T->lchild);
		PreOrder(T->rchild);
	}
}

先序遍歷就是先訪(fǎng)問(wèn)根結(jié)點(diǎn)，在訪(fǎng)問(wèn)左子樹(shù)，最后訪(fǎng)問(wèn)右子樹(shù)，這里也寫(xiě)成遞歸形式；先訪(fǎng)問(wèn)當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)，再對(duì)左右子樹(shù)進(jìn)行訪(fǎng)問(wèn)。

中序遍歷

void InOrder(BiTree T)//中序
{
	if (T != NULL)
	{
		PreOrder(T->lchild);
		cout << T->data << " ";
		PreOrder(T->rchild);
	}
}

中序遍歷就是先訪(fǎng)問(wèn)左子樹(shù)，在訪(fǎng)問(wèn)根結(jié)點(diǎn)，最后訪(fǎng)問(wèn)右子樹(shù)，這里也寫(xiě)成遞歸形式；先訪(fǎng)問(wèn)當(dāng)前結(jié)點(diǎn)的左子樹(shù)的數(shù)據(jù)，再對(duì)該結(jié)點(diǎn)的數(shù)據(jù)進(jìn)行訪(fǎng)問(wèn)，最后對(duì)右子樹(shù)進(jìn)行訪(fǎng)問(wèn)。

后序遍歷

void PostOrder(BiTree T)//后序
{
	if (T)
	{
		PreOrder(T->lchild);
		PreOrder(T->rchild);
		cout << T->data << " ";
	}
}

后序遍歷就是先訪(fǎng)問(wèn)左子樹(shù)，在訪(fǎng)問(wèn)右子樹(shù)，最后訪(fǎng)問(wèn)根結(jié)點(diǎn)，這里也寫(xiě)成遞歸形式；先訪(fǎng)問(wèn)當(dāng)前結(jié)點(diǎn)的左子樹(shù)的數(shù)據(jù)，再對(duì)右子樹(shù)進(jìn)行訪(fǎng)問(wèn)，最后訪(fǎng)問(wèn)根結(jié)點(diǎn)。

具體例題

參考上面的結(jié)構(gòu)體，設(shè)計(jì)一個(gè)函數(shù)，要求能夠同時(shí)求出二叉樹(shù)中所有結(jié)點(diǎn)的的個(gè)數(shù)和二叉樹(shù)中數(shù)據(jù)為奇數(shù)的和；

我的思考：該函數(shù)傳入m和n兩個(gè)全局變量，使用引用傳遞；當(dāng)樹(shù)不為空時(shí)，m++,n等于n加該結(jié)點(diǎn)數(shù)據(jù)域的值，接下來(lái)進(jìn)行左右子樹(shù)的遞歸調(diào)用：

void countT(BiTree T, int &m, int &n)
{
	if (T == NULL) return ;
	if (T->data % 2 != 0) n += T->data;
	m++;
	countT(T->lchild, m, n);
	countT(T->rchild, m, n);
}

從主函數(shù)中這樣調(diào)用：

int m = 0,n = 0;

BiTree T=NULL;

countT(T, m, n);

最后輸出m和n的值即可

效果截圖：

注意輸出的格式，必須是樹(shù)的形式，下面解析一下

輸入的格式

注意：輸入的格式必須是樹(shù)的先序遍歷形式，因?yàn)樵谶@個(gè)程序中初始化二叉樹(shù)就是用的先序的方式

在這個(gè)二叉樹(shù)先序輸入數(shù)據(jù)：3 4 6 0 8 0 0 0 11 13 0 0 0

全部源碼

粘貼到C++編譯器就能使用

#include<iostream>
using namespace std;
typedef struct Node
{
	int data;
	Node* lchild;
	Node* rchild;
}BiNode,*BiTree;
BiTree createBiTree(BiTree &T)
{
	int d;
	cin >> d;
	if (d == 0)
	    T = NULL;
	else
	{
		T = (BiTree)malloc(sizeof(BiNode));
		T->data = d;
		T->lchild = createBiTree(T->lchild);
		T->rchild = createBiTree(T->rchild);
	}
	return T;
}
void PreOrder(BiTree T)//先序
{
	if (T)
	{
		cout << T->data<<" ";
		PreOrder(T->lchild);
		PreOrder(T->rchild);
	}
}
void InOrder(BiTree T)//中序
{
	if (T)
	{
		InOrder(T->lchild);
		cout << T->data << " ";
		InOrder(T->rchild);
	}
}
void PostOrder(BiTree T)//后序
{
	if (T)
	{
		PostOrder(T->lchild);
		PostOrder(T->rchild);
		cout << T->data << " ";
	}
}
void countT(BiTree T, int &m, int &n)
{
	if (T == NULL) return ;
	if (T->data % 2 != 0) n += T->data;
	m++;
	countT(T->lchild, m, n);
	countT(T->rchild, m, n);
}
int main()
{
	int m = 0,n = 0;
	BiTree T=NULL;
	cout << "輸入先序遍歷結(jié)點(diǎn)，建立二叉樹(shù)" << endl;
	T = createBiTree(T);
	cout << "先序遍歷結(jié)果" << endl;
	PreOrder(T);
	cout << endl;
	cout << "中序遍歷結(jié)果" << endl;
	InOrder(T);
	cout << endl;
	cout << "后序遍歷結(jié)果" << endl;
	PostOrder(T);
	cout << endl;
	countT(T, m, n);
	cout << "結(jié)點(diǎn)個(gè)數(shù)為：" << m << endl;
	cout << "數(shù)據(jù)為：" << n << endl;
}