国产无码综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

<menu id="k0iyu"><s id="k0iyu"></s></menu>

<rt id="k0iyu"><ul id="k0iyu"></ul></rt>

【C語言數(shù)據(jù)結(jié)構(gòu)】堆與二叉樹（下）

2年前作者：小小小汐-分類：Toy博客閱讀(14)違法舉報

這篇具有很好參考價值的文章主要介紹了【C語言數(shù)據(jù)結(jié)構(gòu)】堆與二叉樹（下）。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點(diǎn)擊"舉報違法"按鈕提交疑問。

接著上次的，這里主要介紹的是堆排序，二叉樹的遍歷，以及之前講題時答應(yīng)過的簡單二叉樹問題求解

堆排序

給一組數(shù)據(jù)，升序（降序）排列

思路

思考：如果排列升序，我們應(yīng)該建什么堆？

首先，如果排升序，數(shù)列最后一個數(shù)是最大數(shù)，我們的思路是通過向上調(diào)整或者向下調(diào)整，數(shù)組存放的第一個數(shù)不是最小值（小堆）就是最大值（大堆），此時我們將最后一個數(shù)與第一個數(shù)交換，使得最大值放在最后，此時再使用向上調(diào)整或者向下調(diào)整，得到第二大的數(shù)，重復(fù)上述動作，很明顯，我們需要的第一個數(shù)是最大值，因此我們需要建大堆

反之，排降序，建立小堆

代碼文章來源地址http://www.zghlxwxcb.cn/news/detail-805527.html

#include<stdio.h>
void downAdjust(int* pa, int parent, int n)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && pa[child] > pa[child + 1])
		{
			child++;
		}
		if (pa[parent] > pa[child])
		{
			swap(&pa[parent], &pa[child]);
		}
		else
		{
			break;
		}
		parent = child;
		child = parent * 2 + 1;
	}
}
int main()
{
	int arr[] = { 1,3,2,5,7,4,7,4,2,5,6,8};
	int n = sizeof(arr) / sizeof(arr[0]);
	  for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	  {
		downAdjust(arr, i, n);
	  }
		for (int i = n; i > 0; )
		{
			swap(&arr[0], &arr[i - 1]);
			downAdjust(arr, 0, --i);
		}
		for (int i = 0; i < n; i++)
		{
			printf("%d ", arr[i]);
		}

	return 0;
}

topK算法

在一組數(shù)據(jù)中，選出k個最大（最?。┑臄?shù)

思路

如果我們選擇k個最大的數(shù)，假設(shè)數(shù)組的前k個數(shù)就是最大的數(shù)，這 k個數(shù)建立小堆，帶一個數(shù)與后面的從第 k + 1個數(shù)開始，進(jìn)行比較，如果比第一個數(shù)的就換下來，然后向下調(diào)整，直到每個所有數(shù)都比較完了

代碼

void downAdjust(int* pa, int parent, int n)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && pa[child] > pa[child + 1])
		{
			child++;
		}
		if (pa[parent] > pa[child])
		{
			swap(&pa[parent], &pa[child]);
		}
		else
		{
			break;
		}
		parent = child;
		child = parent * 2 + 1;
	}
}
#include<stdio.h>
int main()
{
	int arr[] = { 1,6,10,3,5,8,46,23,6,25,3,40 };
	int n = sizeof(arr) / sizeof(arr[0]);
	int k = 0;
	scanf("%d", &k);
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		downAdjust(arr, i, n);
	}
	for (int i = k; i < n; i++)
	{
		if (arr[i] > arr[0])
		{
			swap(&arr[i], &arr[0]);
			downAdjust(arr, 0, k);
		}
	}
	for (int i = 0; i < k; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

五. 二叉樹的實(shí)現(xiàn)

1. 鏈接結(jié)構(gòu)搭建二叉樹

代碼

typedef int TLType;
typedef struct TreeList
{
	TLType val;
	struct TreeList* left;
	struct TreeList* right;
}TL;
TL *creatnode(TLType x)
{
	TL*pa = (TL*)malloc(sizeof(TL));
	if (pa == NULL)
	{
		perror("malloc");
		return;
	}
	TL* newnode = pa;
	newnode->left = newnode->right = NULL;
	newnode->val = x;
	return newnode;
}
TL* CreatTree()
{
	TL* tree1 = creatnode(1);
	TL *tree2 = creatnode(2);
	TL* tree3 = creatnode(3);
	TL* tree4 = creatnode(3);
	tree1->left = tree2;
	tree1->right = tree3;
	tree2->left = tree4;
	return tree1;
}
#include<stdio.h>
int main()
{
	TL* p = NULL;
	p = CreatTree();
}

我們搭建了一個這樣的樹結(jié)構(gòu)：

【C語言數(shù)據(jù)結(jié)構(gòu)】堆與二叉樹（下）,數(shù)據(jù)結(jié)構(gòu),c語言

2. 二叉樹的遍歷

二叉樹的遍歷可以分三種：前序，中序，后序，層序

a. 前序遍歷：（根，左子樹，右子樹）

舉例

這棵樹的前序遍歷是怎樣的？（包括空樹，用N表示）

val1 val2 val4 N N val5 N N val3 val6 N N val7 N N

代碼實(shí)現(xiàn)?

#include<stdio.h>
#include<stdlib.h>
typedef int TLType;
typedef struct TreeList
{
	TLType val;
	struct TreeList* left;
	struct TreeList* right;
}TL;
TL *creatnode(TLType x)
{
	TL*pa = (TL*)malloc(sizeof(TL));
	if (pa == NULL)
	{
		perror("malloc");
		return;
	}
	TL* newnode = pa;
	newnode->left = newnode->right = NULL;
	newnode->val = x;
	return newnode;
}
TL* CreatTree()
{
	TL* tree1 = creatnode(1);
	TL *tree2 = creatnode(2);
	TL* tree3 = creatnode(3);
	TL* tree4 = creatnode(4);
	TL* tree5 = creatnode(5);
	TL* tree6 = creatnode(6);
	TL* tree7 = creatnode(7);
	tree1->left = tree2;
	tree1->right = tree3;
	tree2->left = tree4;
	tree2->right = tree5;
	tree3->left = tree6;
	tree3->right = tree7;
	return tree1;
}
#include<stdio.h>
void PrevOrder(TL *root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	printf("%d ", root->val);
	PrevOrder(root->left);
	PrevOrder(root->right);
}
int main()
{
	TL* p = NULL;
	p = CreatTree();
	PrevOrder(p);
}

運(yùn)行結(jié)果：

【C語言數(shù)據(jù)結(jié)構(gòu)】堆與二叉樹（下）,數(shù)據(jù)結(jié)構(gòu),c語言

b. 中序遍歷：（左子樹，根，右子樹）

舉例

這棵樹的中序遍歷是怎樣的？（包括空樹，用N表示）

N val4 N val2 N val5 N val1 N val6 N val3 N val7 N

?代碼實(shí)現(xiàn)

#include<stdio.h>
#include<stdlib.h>
typedef int TLType;
typedef struct TreeList
{
	TLType val;
	struct TreeList* left;
	struct TreeList* right;
}TL;
TL *creatnode(TLType x)
{
	TL*pa = (TL*)malloc(sizeof(TL));
	if (pa == NULL)
	{
		perror("malloc");
		return;
	}
	TL* newnode = pa;
	newnode->left = newnode->right = NULL;
	newnode->val = x;
	return newnode;
}
TL* CreatTree()
{
	TL* tree1 = creatnode(1);
	TL *tree2 = creatnode(2);
	TL* tree3 = creatnode(3);
	TL* tree4 = creatnode(4);
	TL* tree5 = creatnode(5);
	TL* tree6 = creatnode(6);
	TL* tree7 = creatnode(7);
	tree1->left = tree2;
	tree1->right = tree3;
	tree2->left = tree4;
	tree2->right = tree5;
	tree3->left = tree6;
	tree3->right = tree7;
	return tree1;
}
#include<stdio.h>
void InOder(TL* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	InOder(root->left);
	printf("%d ", root->val);
	InOder(root->right);
}
int main()
{
	TL* p = NULL;
	p = CreatTree();
	InOder(p);
}

運(yùn)行結(jié)果：

【C語言數(shù)據(jù)結(jié)構(gòu)】堆與二叉樹（下）,數(shù)據(jù)結(jié)構(gòu),c語言

c. 后序遍歷：（左子樹，右子樹，根）

舉例

這棵樹的后序遍歷是怎樣的？（包括空樹，用N表示）

N N val4 N N val5 val2 N N val6 N N val7 val3 val1

代碼實(shí)現(xiàn)?

#include<stdio.h>
#include<stdlib.h>
typedef int TLType;
typedef struct TreeList
{
	TLType val;
	struct TreeList* left;
	struct TreeList* right;
}TL;
TL* creatnode(TLType x)
{
	TL* pa = (TL*)malloc(sizeof(TL));
	if (pa == NULL)
	{
		perror("malloc");
		return;
	}
	TL* newnode = pa;
	newnode->left = newnode->right = NULL;
	newnode->val = x;
	return newnode;
}
TL* CreatTree()
{
	TL* tree1 = creatnode(1);
	TL* tree2 = creatnode(2);
	TL* tree3 = creatnode(3);
	TL* tree4 = creatnode(4);
	TL* tree5 = creatnode(5);
	TL* tree6 = creatnode(6);
	TL* tree7 = creatnode(7);
	tree1->left = tree2;
	tree1->right = tree3;
	tree2->left = tree4;
	tree2->right = tree5;
	tree3->left = tree6;
	tree3->right = tree7;
	return tree1;
}
void PostOder(TL* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	PostOder(root->left);
	PostOder(root->right);
	printf("%d ", root->val);
}
int main()
{
	TL* p = NULL;
	p = CreatTree();
	PostOder(p);
}

運(yùn)行結(jié)果：

【C語言數(shù)據(jù)結(jié)構(gòu)】堆與二叉樹（下）,數(shù)據(jù)結(jié)構(gòu),c語言

d. 層序遍歷

一排排的遍歷

畫圖舉例

實(shí)現(xiàn)思路?

這里我們借助隊(duì)列（可以先進(jìn)先出），開辟的數(shù)組里面存放根節(jié)點(diǎn)的地址（通過地址可以找到左右子樹，否則如果存值是沒有辦法找到左右子樹），打印完根節(jié)點(diǎn)的值，就釋放，存入左右子樹的節(jié)點(diǎn)

代碼實(shí)現(xiàn)

實(shí)現(xiàn)的二叉樹是這樣的：

【C語言數(shù)據(jù)結(jié)構(gòu)】堆與二叉樹（下）,數(shù)據(jù)結(jié)構(gòu),c語言

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int TLType;
typedef struct TreeList
{
	TLType val;
	struct TreeList* left;
	struct TreeList* right;
}TL;
TL* creatnode(TLType x)
{
	TL* pa = (TL*)malloc(sizeof(TL));
	if (pa == NULL)
	{
		perror("malloc");
		return;
	}
	TL* newnode = pa;
	newnode->left = newnode->right = NULL;
	newnode->val = x;
	return newnode;
}
TL* CreatTree()
{
	TL* tree1 = creatnode(1);
	TL* tree2 = creatnode(2);
	TL* tree3 = creatnode(3);
	TL* tree4 = creatnode(4);
	TL* tree5 = creatnode(5);
	TL* tree6 = creatnode(6);
	TL* tree7 = creatnode(7);
	tree1->left = tree2;
	tree1->right = tree3;
	tree2->left = tree4;
	tree2->right = tree5;
	tree3->left = tree6;
	tree3->right = tree7;
	return tree1;
}
typedef struct QueueNode
{
	struct QueueNode* next;
	TL* data;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Que;


void QueueInit(Que* pq)
{
	assert(pq);

	pq->head = pq->tail = NULL;
	pq->size = 0;
}

void QueueDestroy(Que* pq)
{
	assert(pq);

	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}

	pq->head = pq->tail = NULL;
	pq->size = 0;
}

void QueuePush(Que* pq, TL* x)
{
	assert(pq);

	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	newnode->data = x;
	newnode->next = NULL;

	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}

	pq->size++;
}

bool QueueEmpty(Que* pq)
{
	assert(pq);

	return pq->head == NULL;
}
void QueuePop(Que* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}

	pq->size--;
}

TL* QueueFront(Que* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->head->data;
}




int QueueSize(Que* pq)
{
	assert(pq);

	return pq->size;
}
void leverOrder(TL* root, Que* pq)
{
	QueuePush(pq, root);
	while (!QueueEmpty(pq))
	{
		TL* pa = QueueFront(pq);
		printf("%d ", pa->val);
		QueuePop(pq);
		if (pa->left != NULL)
		{
			QueuePush(pq, pa->left);
		}
		if (pa->right != NULL)
		{
			QueuePush(pq, pa->right);
		}
	}

}
int main()
{
	TL* p = NULL;
	p = CreatTree();
	Que q;
	QueueInit(&q);
	leverOrder(p, &q);
	return 0;
}

運(yùn)行結(jié)果：

【C語言數(shù)據(jù)結(jié)構(gòu)】堆與二叉樹（下）,數(shù)據(jù)結(jié)構(gòu),c語言

3. 簡單二叉樹經(jīng)典問題求解

a. 求二叉樹的節(jié)點(diǎn)個數(shù)

思路

想要求二叉樹的節(jié)點(diǎn)可以分成根節(jié)點(diǎn) + 左子樹 + 右子樹

這里的遍歷類似 前序遍歷

代碼

實(shí)現(xiàn)的樹是這樣的：

【C語言數(shù)據(jù)結(jié)構(gòu)】堆與二叉樹（下）,數(shù)據(jù)結(jié)構(gòu),c語言

#include<stdio.h>
#include<stdlib.h>
typedef int TLType;
typedef struct TreeList
{
	TLType val;
	struct TreeList* left;
	struct TreeList* right;
}TL;
TL* creatnode(TLType x)
{
	TL* pa = (TL*)malloc(sizeof(TL));
	if (pa == NULL)
	{
		perror("malloc");
		return;
	}
	TL* newnode = pa;
	newnode->left = newnode->right = NULL;
	newnode->val = x;
	return newnode;
}
TL* CreatTree()
{
	TL* tree1 = creatnode(1);
	TL* tree2 = creatnode(2);
	TL* tree3 = creatnode(3);
	TL* tree4 = creatnode(4);
	TL* tree5 = creatnode(5);
	TL* tree6 = creatnode(6);
	TL* tree7 = creatnode(7);
	tree1->left = tree2;
	tree1->right = tree3;
	tree2->left = tree4;
	tree2->right = tree5;
	tree3->left = tree6;
	tree3->right = tree7;
	return tree1;
}
int TreeSize(TL* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return 1 + TreeSize(root->left) + TreeSize(root->right);
}
int main()
{
	TL* p = NULL;
	p = CreatTree();
	int size = TreeSize(p);
	printf("%d ", size);
	return 0;
}

b. 求樹的高度

思路

求二叉樹的高度，我們需要找到到那個最長的路徑，這里采用分治的思想，如果為空樹，返回 0 （空樹高度為 0），調(diào)用左子樹和右子樹都會 + 1（+ 1可以理解成加上節(jié)點(diǎn)的高度），對比左子樹和右子樹，返回高度最大的那個

注：每求一次左右節(jié)點(diǎn)個數(shù)時，一定要保存，否則會有很大的時間浪費(fèi)

代碼

#include<stdio.h>
#include<stdlib.h>
typedef int TLType;
typedef struct TreeList
{
	TLType val;
	struct TreeList* left;
	struct TreeList* right;
}TL;
TL* creatnode(TLType x)
{
	TL* pa = (TL*)malloc(sizeof(TL));
	if (pa == NULL)
	{
		perror("malloc");
		return;
	}
	TL* newnode = pa;
	newnode->left = newnode->right = NULL;
	newnode->val = x;
	return newnode;
}
TL* CreatTree()
{
	TL* tree1 = creatnode(1);
	TL* tree2 = creatnode(2);
	TL* tree3 = creatnode(3);
	TL* tree4 = creatnode(4);
	TL* tree5 = creatnode(5);
	TL* tree6 = creatnode(6);
	TL* tree7 = creatnode(7);
	TL* tree8 = creatnode(8);
	tree1->left = tree2;
	tree1->right = tree3;
	tree2->left = tree4;
	tree2->right = tree5;
	tree3->left = tree6;
	tree3->right = tree7;
	tree4->left = tree8;
	return tree1;
}
int TreeHigh(TL* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int Left = 1 + TreeHigh(root->left);
	int Right = 1 +  TreeHigh(root->right) ;
	return Left > Right ? Left : Right;
}
int main()
{
	TL* p = NULL;
	p = CreatTree();
	int high = TreeHigh(p);
	printf("%d ", high);
	return 0;
}

c. 求根節(jié)點(diǎn)的個數(shù)

思路

判斷是否是根節(jié)點(diǎn)的方法就是判斷它的左右子樹是否是空樹，我們只需要遍歷這棵樹就行，但如果遍歷時，根節(jié)點(diǎn)遇到空樹這也是一種結(jié)束條件

代碼

#include<stdio.h>
#include<stdlib.h>
typedef int TLType;
typedef struct TreeList
{
	TLType val;
	struct TreeList* left;
	struct TreeList* right;
}TL;
TL* creatnode(TLType x)
{
	TL* pa = (TL*)malloc(sizeof(TL));
	if (pa == NULL)
	{
		perror("malloc");
		return;
	}
	TL* newnode = pa;
	newnode->left = newnode->right = NULL;
	newnode->val = x;
	return newnode;
}
TL* CreatTree()
{
	TL* tree1 = creatnode(1);
	TL* tree2 = creatnode(2);
	TL* tree3 = creatnode(3);
	TL* tree4 = creatnode(4);
	TL* tree5 = creatnode(5);
	TL* tree6 = creatnode(6);
	TL* tree7 = creatnode(7);
	TL* tree8 = creatnode(8);
	tree1->left = tree2;
	tree1->right = tree3;
	tree2->left = tree4;
	tree2->right = tree5;
	tree3->left = tree6;
	tree3->right = tree7;
	tree4->left = tree8;
	return tree1;
}
int RootSize(TL* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return RootSize(root->left) + RootSize(root->right);
}
int main()
{
	TL* p = NULL;
	p = CreatTree();
	int root = RootSize(p);
	printf("%d ", root);
	return 0;
}

d. 求倒數(shù)第k排節(jié)點(diǎn)的個數(shù)

思路

這個可以是求樹的高度的變形，將計數(shù)倒過來

代碼?

#include<stdio.h>
#include<stdlib.h>
typedef int TLType;
typedef struct TreeList
{
	TLType val;
	struct TreeList* left;
	struct TreeList* right;
}TL;
TL* creatnode(TLType x)
{
	TL* pa = (TL*)malloc(sizeof(TL));
	if (pa == NULL)
	{
		perror("malloc");
		return;
	}
	TL* newnode = pa;
	newnode->left = newnode->right = NULL;
	newnode->val = x;
	return newnode;
}
TL* CreatTree()
{
	TL* tree1 = creatnode(1);
	TL* tree2 = creatnode(2);
	TL* tree3 = creatnode(3);
	TL* tree4 = creatnode(4);
	TL* tree5 = creatnode(5);
	TL* tree6 = creatnode(6);
	TL* tree7 = creatnode(7);
	TL* tree8 = creatnode(8);
	tree1->left = tree2;
	tree1->right = tree3;
	tree2->left = tree4;
	tree2->right = tree5;
	tree3->left = tree6;
	tree3->right = tree7;
	tree4->left = tree8;
	return tree1;
}

int TreeHigh(TL* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int Left = 1 + TreeHigh(root->left);
	int Right = 1 +  TreeHigh(root->right) ;
	return Left > Right ? Left : Right;
}
int RootKsize(TL* root,int n,int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (n == k)
	{
		return 1;
	}
	return RootKsize(root->left, n - 1, k) + RootKsize(root->right, n - 1, k);
}
int main()
{
	int k = 0;
	scanf("%d", &k);
	TL* p = NULL;
	p = CreatTree();
	int high = TreeHigh(p);
	int rootk = RootKsize(p, high, k);
	printf("%d ", rootk);
	return 0;
}

e. 判斷是否是相同的樹

思路

采用前序，先比較根節(jié)點(diǎn)是否相同，再比較左右子樹是否相同

代碼

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int TLType;
typedef struct TreeList
{
	TLType val;
	struct TreeList* left;
	struct TreeList* right;
}TL;
TL* creatnode(TLType x)
{
	TL* pa = (TL*)malloc(sizeof(TL));
	if (pa == NULL)
	{
		perror("malloc");
		return;
	}
	TL* newnode = pa;
	newnode->left = newnode->right = NULL;
	newnode->val = x;
	return newnode;
}
TL* CreatTree1()
{
	TL* tree1 = creatnode(1);
	TL* tree2 = creatnode(2);
	TL* tree3 = creatnode(3);
	TL* tree4 = creatnode(4);
	TL* tree5 = creatnode(5);
	TL* tree6 = creatnode(6);
	TL* tree7 = creatnode(7);
	TL* tree8 = creatnode(8);
	tree1->left = tree2;
	tree1->right = tree3;
	tree2->left = tree4;
	tree2->right = tree5;
	tree3->left = tree6;
	tree3->right = tree7;
	tree4->left = tree8;
	return tree1;
}
TL* CreatTree2()
{
	TL* tree1 = creatnode(1);
	TL* tree2 = creatnode(2);
	TL* tree3 = creatnode(3);
	TL* tree4 = creatnode(4);
	TL* tree5 = creatnode(5);
	TL* tree6 = creatnode(6);
	TL* tree7 = creatnode(7);
	tree1->left = tree2;
	tree1->right = tree3;
	tree2->left = tree4;
	tree2->right = tree5;
	tree3->left = tree6;
	tree3->right = tree7;
	return tree1;
}
bool IsSameTree(TL* root1,TL* root2)
{
	if (root1 == NULL && root2 == NULL)
	{
		return true;
	}
	if (root1 == NULL || root2 == NULL)
	{
		return false;
	}
	if (root1->val != root2->val)
	{
		return false;
	}
	return IsSameTree(root1->left, root2->left) && IsSameTree(root1->right, root2->right);
}
int main()
{
	TL* p = NULL;
	p = CreatTree1();
	TL* q = CreatTree2();
	printf("%d ", IsSameTree(p, q));
	return 0;
}

f. 找到某個值，返回節(jié)點(diǎn)的地址

思路

前序遍歷完數(shù)組，如果對比左右子樹，判斷是否找到節(jié)點(diǎn)的地址

代碼

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int TLType;
typedef struct TreeList
{
	TLType val;
	struct TreeList* left;
	struct TreeList* right;
}TL;
TL* creatnode(TLType x)
{
	TL* pa = (TL*)malloc(sizeof(TL));
	if (pa == NULL)
	{
		perror("malloc");
		return;
	}
	TL* newnode = pa;
	newnode->left = newnode->right = NULL;
	newnode->val = x;
	return newnode;
}
TL* CreatTree()
{
	TL* tree1 = creatnode(1);
	TL* tree2 = creatnode(2);
	TL* tree3 = creatnode(2);
	TL* tree4 = creatnode(4);
	TL* tree5 = creatnode(5);
	TL* tree6 = creatnode(6);
	TL* tree7 = creatnode(7);
	TL* tree8 = creatnode(8);
	tree1->left = tree2;
	tree1->right = tree3;
	tree2->left = tree4;
	tree2->right = tree5;
	tree3->left = tree6;
	tree3->right = tree7;
	tree4->left = tree8;
	return tree1;
}
TL* FindRoot(TL* root,int m)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->val == m)
	{
		return root;
	}
	TL* Left = FindRoot(root->left, m);
	TL* Right = FindRoot(root->right, m);
	if (Left == NULL && Right == NULL)
	{
		return NULL;
	}
	if (Left == NULL && Right != NULL)
	{
		return Right;
	}
	else 
	{
		return Left;
	}
	
}
int main()
{
	TL* p = NULL;
	p = CreatTree();
	int m = 0;
	scanf("%d", &m);
	TL *root = FindRoot(p,m);
	if (root == NULL)
	{
		printf("找不到\n");
	}
	else
	{
		printf("%d ", root->val);
	}
	return 0;
}

到了這里，關(guān)于【C語言數(shù)據(jù)結(jié)構(gòu)】堆與二叉樹（下）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來自互聯(lián)網(wǎng)用戶投稿，該文觀點(diǎn)僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務(wù)，不擁有所有權(quán)，不承擔(dān)相關(guān)法律責(zé)任。如若轉(zhuǎn)載，請注明出處：如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實(shí)不符，請點(diǎn)擊違法舉報進(jìn)行投訴反饋，一經(jīng)查實(shí)，立即刪除！

分享到：

領(lǐng)支付寶紅包贊助服務(wù)器費(fèi)用

數(shù)據(jù)結(jié)構(gòu)_樹與二叉樹
目錄 1. 樹的基本概念 1.1 樹的定義 1.2 基本術(shù)語 1.3 樹的性質(zhì) 1.4 相關(guān)練習(xí) 2. 二叉樹的概念 2.1 二叉樹的概念及其主要特性 2.2 二叉樹的存儲結(jié)構(gòu) 2.2.1 順序存儲結(jié)構(gòu) 2.2.2 鏈?zhǔn)酱鎯Y(jié)構(gòu) 2.3 相關(guān)練習(xí) 3. 二叉樹的遍歷和線索二叉樹 3.1 二叉樹的遍歷 3.1.1 先序遍歷 3.1.2 中序遍歷 3.1
2024年02月04日
瀏覽(22)
【數(shù)據(jù)結(jié)構(gòu)】樹與二叉樹（中）
目錄前言：一、順序存儲結(jié)構(gòu)：二、堆： 1.堆的性質(zhì)： 2.堆的性質(zhì)： 3.堆的實(shí)現(xiàn)： Ⅰ.堆的初始化： ?Ⅱ.堆的插入（含向上調(diào)整）： ?Ⅲ.堆的刪除（含向下調(diào)整算法）： Ⅳ.取堆頂?shù)臄?shù)據(jù)： Ⅴ.堆中的數(shù)據(jù)個數(shù)： Ⅵ.堆的判空： ?Ⅶ.堆的銷毀：總結(jié)： ? ? ? ? 上篇文章中，
2024年02月16日
瀏覽(21)
數(shù)據(jù)結(jié)構(gòu)：圖文詳解樹與二叉樹（樹與二叉樹的概念和性質(zhì)，存儲，遍歷）
目錄一.樹的概念二.樹中重要的概念三.二叉樹的概念滿二叉樹完全二叉樹四.二叉樹的性質(zhì) 五.二叉樹的存儲六.二叉樹的遍歷前序遍歷中序遍歷? 后序遍歷? 樹是一種非線性數(shù)據(jù)結(jié)構(gòu) ，它由節(jié)點(diǎn)和邊組成。樹的每個節(jié)點(diǎn)可以有零個或多個子節(jié)點(diǎn)，其中一個節(jié)點(diǎn)被指定為
2024年02月04日
瀏覽(25)
數(shù)據(jù)結(jié)構(gòu)與算法——樹與二叉樹
??各位小伙伴久等了，本專欄新文章出爐了?。?！我又回來啦，接下來的時間里，我會持續(xù)把數(shù)據(jù)結(jié)構(gòu)與算法專欄更新完。 ??樹型結(jié)構(gòu)?? 是一類重要的 ?非線性數(shù)據(jù)結(jié)構(gòu) ，其中以樹和二叉樹最為常用，直觀來看，樹是以分支關(guān)系定義的層次結(jié)構(gòu)。樹型結(jié)構(gòu)在客觀世界中
2024年02月11日
瀏覽(16)
【數(shù)據(jù)結(jié)構(gòu)與算法】樹與二叉樹
除了之前我們講的棧、隊(duì)列、鏈表等線性結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)中還有著一對多的非線性結(jié)構(gòu) ——— 樹。樹是有 n 個結(jié)點(diǎn)組成的有限集，當(dāng)n=0時為空樹，在任意一顆非空樹中，有且僅有一個特定的根結(jié)點(diǎn) ；當(dāng)n1時，其余結(jié)點(diǎn)又可以分為一棵樹，稱為根的子樹。如下圖所示: A為
2023年04月09日
瀏覽(25)
【數(shù)據(jù)結(jié)構(gòu)】詳解二叉樹與堆與堆排序的關(guān)系
??個人主頁：平凡的小蘇 ??學(xué)習(xí)格言：別人可以拷貝我的模式，但不能拷貝我不斷往前的激情 ??C語言專欄：https://blog.csdn.net/vhhhbb/category_12174730.html ??數(shù)據(jù)結(jié)構(gòu)專欄：https://blog.csdn.net/vhhhbb/category_12211053.html ? ? ? ? 家人們更新不易，你們的??點(diǎn)贊??和?關(guān)注?真的對我
2024年02月02日
瀏覽(24)
【數(shù)據(jù)結(jié)構(gòu)】樹與二叉樹（十三）：遞歸復(fù)制二叉樹（算法CopyTree）
??二叉樹是一種常見的樹狀數(shù)據(jù)結(jié)構(gòu)，它由結(jié)點(diǎn)的有限集合組成。一個二叉樹要么是空集，被稱為空二叉樹，要么由一個根結(jié)點(diǎn)和兩棵不相交的子樹組成，分別稱為左子樹和右子樹。每個結(jié)點(diǎn)最多有兩個子結(jié)點(diǎn)，分別稱為左子結(jié)點(diǎn)和右子結(jié)點(diǎn)。引理5.1：二叉樹中層數(shù)
2024年02月01日
瀏覽(18)
【數(shù)據(jù)結(jié)構(gòu)】24王道考研筆記——樹與二叉樹
樹是n個結(jié)點(diǎn)的有限集合，n=0時，稱為空樹。非空樹滿足：除了根節(jié)點(diǎn)外，任何一個結(jié)點(diǎn)都有且僅有一個前驅(qū) 結(jié)點(diǎn)的層次（深度）：從上往下數(shù) 結(jié)點(diǎn)的高度：從下往上數(shù) 樹的高度（深度）：總共有多少層結(jié)點(diǎn)的度：有幾個孩子（分支）樹的度：各節(jié)點(diǎn)的度的最大值森林：
2024年02月13日
瀏覽(28)
數(shù)據(jù)結(jié)構(gòu)與算法——樹與二叉樹篇詳解
樹形結(jié)構(gòu)是一種非常重要的非線性結(jié)構(gòu) ，樹形結(jié)構(gòu)中數(shù)據(jù)元素之間具有一對多的邏輯關(guān)系。 1.1.1 樹的定義樹是由n(n=0)個結(jié)點(diǎn)所構(gòu)成的有限集合當(dāng)n=0時，稱為空樹當(dāng)n0時，n個結(jié)點(diǎn)滿足以下條件有且僅有一個稱為根的結(jié)點(diǎn) 其余結(jié)點(diǎn)可分為m個互不相交的有限集合，且每一個
2024年02月06日
瀏覽(24)
數(shù)據(jù)結(jié)構(gòu)之樹與二叉樹——算法與數(shù)據(jù)結(jié)構(gòu)入門筆記（五）
本文是算法與數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)筆記第五篇，將持續(xù)更新，歡迎小伙伴們閱讀學(xué)習(xí)。有不懂的或錯誤的地方，歡迎交流前面章節(jié)介紹的都是線性存儲的數(shù)據(jù)結(jié)構(gòu)，包括數(shù)組、鏈表、棧、隊(duì)列。本節(jié)帶大家學(xué)習(xí)一種非線性存儲的數(shù)據(jù)結(jié)構(gòu)，即樹（tree）。不管是在面試時，還是日
2024年02月08日
瀏覽(45)

<rt id="ucwom"></rt>