C++簡單又輕鬆建立鏈式二元樹流程

2022-06-07 14:08:00

遞迴建立二元樹

二元樹的結構體

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;
}

這個初始化函數的返回值為BiTree是一個結構體指標型別，用來返回初始化後的 T 二元樹；整型資料d是用來給二元樹的結點賦值的，當輸入0的時候，該結點為空結點；當結點的資料域不為零，給該結點動態分配記憶體空間，並把d賦值給T->data；然後就是對左右子樹的遞迴初始化了。

先序遍歷

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

先序遍歷就是先存取根結點，在存取左子樹，最後存取右子樹，這裡也寫成遞迴形式；先存取當前結點的資料，再對左右子樹進行存取。

中序遍歷

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

中序遍歷就是先存取左子樹，在存取根結點，最後存取右子樹，這裡也寫成遞迴形式；先存取當前結點的左子樹的資料，再對該結點的資料進行存取，最後對右子樹進行存取。

後序遍歷

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

後序遍歷就是先存取左子樹，在存取右子樹，最後存取根結點，這裡也寫成遞迴形式；先存取當前結點的左子樹的資料，再對右子樹進行存取，最後存取根結點。

具體例題

參考上面的結構體，設計一個函數，要求能夠同時求出二元樹中所有結點的的個數和二元樹中資料為奇數的和；

我的思考：該函數傳入m和n兩個全域性變數，使用參照傳遞；當樹不為空時，m++,n等於n加該結點資料域的值，接下來進行左右子樹的遞迴呼叫：

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 m = 0,n = 0;

BiTree T=NULL;

countT(T, m, n);

最後輸出m和n的值即可

效果截圖：

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

輸入的格式

注意：輸入的格式必須是樹的先序遍歷形式，因為在這個程式中初始化二元樹就是用的先序的方式

在這個二元樹先序輸入資料：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 << "輸入先序遍歷結點，建立二元樹" << endl;
	T = createBiTree(T);
	cout << "先序遍歷結果" << endl;
	PreOrder(T);
	cout << endl;
	cout << "中序遍歷結果" << endl;
	InOrder(T);
	cout << endl;
	cout << "後序遍歷結果" << endl;
	PostOrder(T);
	cout << endl;
	countT(T, m, n);
	cout << "結點個數為：" << m << endl;
	cout << "資料為：" << n << endl;
}