首页 > 其他分享 >二叉树的线索化——C语言描述

二叉树的线索化——C语言描述

时间：2023-01-15 16:44:06浏览次数：76  
标签：RightChild BiThrTrNodeTemp BiThrTreeNode int C语言 LeftChild 二叉树 Data 线索

二叉树的线索化——C语言描述

目录

0 测试用例框架

https://blog.csdn.net/m0_59469991/article/details/127137119?csdn_share_tail=%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22article%22%2C%22rId%22%3A%22127137119%22%2C%22source%22%3A%22m0_59469991%22%7D

1 定义

​ 利用叶子节点左右孩子的空指针部分，若无孩子节点，那该节点的孩子指针指向中序遍历的下一个节点。中序遍历的第一个节点指向头节点，中序遍历的最后一个节点指向头节点。头节点的左孩子指向根节点，头节点右孩子指向中序遍历的最后一个节点。这时整个树的结构变成一个双向链表。

2 数据结构

/*BINARY_THREAD_TREE_NODE*/
typedef struct _BINARY_THREAD_TREE_NODE {
	char Data;
	char IfExistDirectLeftNodeFlag;
	char IfExistDirectRightNodeFlag;
	struct _BINARY_THREAD_TREE_NODE *LeftChild;
	struct _BINARY_THREAD_TREE_NODE *RightChild;
}BINARY_THREAD_TREE_NODE;

3 实现方法

void PreOrderTraversePrintBinaryThreadTree(const BINARY_THREAD_TREE_NODE *BiThrTreeNode) {
	//printf("BiThrTreeNode = 0x%lx\n", BiThrTreeNode);
	if (BiThrTreeNode == NULL) {
		return;
	}
	else {
		printf("BiThrTreeNode = 0x%lx, BiThrTreeNode->Data = %c, BiThrTreeNode->LeftChild = 0x%lx, BiThrTreeNode->RightChild = 0x%lx\n", (long unsigned int)BiThrTreeNode, BiThrTreeNode->Data, (long unsigned int)BiThrTreeNode->LeftChild, (long unsigned int)BiThrTreeNode->RightChild);
		//printf("BiThrTreeNode->LeftChild = 0x%lx, BiThrTreeNode->RightChild = 0x%lx\n", BiThrTreeNode->LeftChild, BiThrTreeNode->RightChild);
		PreOrderTraversePrintBinaryThreadTree(BiThrTreeNode->LeftChild);
		PreOrderTraversePrintBinaryThreadTree(BiThrTreeNode->RightChild);
	}
}

void InOrderTraversePrintBinaryThreadTree(const BINARY_THREAD_TREE_NODE *BiThrTreeNode) {
	if (BiThrTreeNode == NULL) {
		return;
	}
	else {
		InOrderTraversePrintBinaryThreadTree(BiThrTreeNode->LeftChild);
		printf("BiThrTreeNode = 0x%lx, BiThrTreeNode->Data = %c, BiThrTreeNode->LeftChild = 0x%lx, BiThrTreeNode->RightChild = 0x%lx\n", (long unsigned int)BiThrTreeNode, BiThrTreeNode->Data, (long unsigned int)BiThrTreeNode->LeftChild, (long unsigned int)BiThrTreeNode->RightChild);
		InOrderTraversePrintBinaryThreadTree(BiThrTreeNode->RightChild);
	}
}

void PostOrderTraversePrintBinaryThreadTree(const BINARY_THREAD_TREE_NODE *BiThrTreeNode) {
	if (BiThrTreeNode == NULL) {
		return;
	}
	else {
		PostOrderTraversePrintBinaryThreadTree(BiThrTreeNode->LeftChild);
		PostOrderTraversePrintBinaryThreadTree(BiThrTreeNode->RightChild);
		printf("BiThrTreeNode = 0x%lx, BiThrTreeNode->Data = %c, BiThrTreeNode->LeftChild = 0x%lx, BiThrTreeNode->RightChild = 0x%lx\n", (long unsigned int)BiThrTreeNode, BiThrTreeNode->Data, (long unsigned int)BiThrTreeNode->LeftChild, (long unsigned int)BiThrTreeNode->RightChild);
	}
}

int Index = 0;
void PreOrderBuildBiThrTree(BINARY_THREAD_TREE_NODE **BiThrTreeNodePtr, BINARY_THREAD_TREE_NODE_DATA *DataPtr, char IfExistNodeFlag) {
	char IfExistLeftChildNodeFlag = 0;
	char IfExistRightChildNodeFlag = 0;

	// printf("Index = %d\n", Index);
	// printf("PreOrderBuildBiThrTree start\n");
	// printf("IfExistNodeFlag = %d\n", IfExistNodeFlag);
	//Exit condition
	if (IfExistNodeFlag == 0) {
		*BiThrTreeNodePtr = NULL;
		//--Index;
		return;
	}
	else {
		//The level logic
		*BiThrTreeNodePtr = (BINARY_THREAD_TREE_NODE *)malloc(sizeof(BINARY_THREAD_TREE_NODE));
		// printf("*BiThrTreeNodePtr = 0x%lx\n", (long unsigned int )(*BiThrTreeNodePtr));
		// printf("In else, DataPtr[%d] = %c\n", Index, DataPtr[Index].BiThrTreeData);
		(*BiThrTreeNodePtr)->Data = DataPtr[Index].BiThrTreeData;
		(*BiThrTreeNodePtr)->IfExistDirectLeftNodeFlag = DataPtr[Index].IfExistDirectLeftNodeFlag;
		(*BiThrTreeNodePtr)->IfExistDirectRightNodeFlag = DataPtr[Index].IfExistDirectRightNodeFlag;

		IfExistLeftChildNodeFlag = DataPtr[Index].IsExistLeftChildFlag;
		IfExistRightChildNodeFlag = DataPtr[Index].IsExistRightChildFlag;

		// printf("IfExistLeftChildNodeFlag = %d, IfExistRightChildNodeFlag = %d\n", IfExistLeftChildNodeFlag, IfExistRightChildNodeFlag);

		Index++;

		//Next level
		PreOrderBuildBiThrTree(&((*BiThrTreeNodePtr)->LeftChild), DataPtr, IfExistLeftChildNodeFlag);

		// printf("Index = %d\n", Index);

		PreOrderBuildBiThrTree(&((*BiThrTreeNodePtr)->RightChild), DataPtr, IfExistRightChildNodeFlag);
	}

	// printf("PreOrderBuildBiThrTree end\n");
}


BINARY_THREAD_TREE_NODE *BiThrTrPreNode = NULL;
void InOrderThrBiTree(BINARY_THREAD_TREE_NODE *BiThrTrNode) {
	if (BiThrTrNode == NULL) {
		return;
	}
	else {
		InOrderThrBiTree(BiThrTrNode->LeftChild);

		//printf("BiThrTrNode = 0x%lx, BiThrTrNode->Data = %c, BiThrTrNode->LeftChild = 0x%lx, BiThrTrNode->RightChild = 0x%lx\n", (long unsigned int )BiThrTrNode, BiThrTrNode->Data, (long unsigned int )BiThrTrNode->LeftChild, (long unsigned int )BiThrTrNode->RightChild);

		//The Level
		if (BiThrTrNode->LeftChild == NULL) {
			BiThrTrNode->LeftChild = BiThrTrPreNode;
		}

		if (BiThrTrPreNode->RightChild == NULL) {
			BiThrTrPreNode->RightChild = BiThrTrNode;
		}

		BiThrTrPreNode = BiThrTrNode;
		//printf("BiThrTrNode->Data = %c\n", BiThrTrNode->Data);
		InOrderThrBiTree(BiThrTrNode->RightChild);
	}
}


void PrintThrTree(BINARY_THREAD_TREE_NODE *BiThrTrNode) {
	BINARY_THREAD_TREE_NODE *BiThrTrNodeTemp = BiThrTrNode->LeftChild;

	//printf("\nPrintThrTree start\n");
	//printf("Root Node, BiThrTrNodeTemp = 0x%lx, BiThrTrNodeTemp->Data = %c, BiThrTrNodeTemp->LeftChild = 0x%lx, BiThrTrNodeTemp->RightChild = 0x%lx\n", (long unsigned int)BiThrTrNodeTemp, BiThrTrNodeTemp->Data, (long unsigned int)BiThrTrNodeTemp->LeftChild, (long unsigned int)BiThrTrNodeTemp->RightChild);
	while (BiThrTrNodeTemp != BiThrTrNode) {
		//printf("test01\n");
		while (BiThrTrNodeTemp->IfExistDirectLeftNodeFlag != 0) {
			BiThrTrNodeTemp = BiThrTrNodeTemp->LeftChild;
		}

		printf("BiThrTrNodeTemp = 0x%lx, BiThrTrNodeTemp->Data = %c, BiThrTrNodeTemp->LeftChild = 0x%lx, BiThrTrNodeTemp->RightChild = 0x%lx\n", (long unsigned int)BiThrTrNodeTemp, BiThrTrNodeTemp->Data, (long unsigned int)BiThrTrNodeTemp->LeftChild, (long unsigned int)BiThrTrNodeTemp->RightChild);

		while ((BiThrTrNodeTemp->IfExistDirectRightNodeFlag == 0) && (BiThrTrNodeTemp->RightChild != BiThrTrNode)) {
			BiThrTrNodeTemp = BiThrTrNodeTemp->RightChild;
			printf("BiThrTrNodeTemp = 0x%lx, BiThrTrNodeTemp->Data = %c, BiThrTrNodeTemp->LeftChild = 0x%lx, BiThrTrNodeTemp->RightChild = 0x%lx\n", (long unsigned int)BiThrTrNodeTemp, BiThrTrNodeTemp->Data, (long unsigned int)BiThrTrNodeTemp->LeftChild, (long unsigned int)BiThrTrNodeTemp->RightChild);
		}

		BiThrTrNodeTemp = BiThrTrNodeTemp->RightChild;
		//printf("BiThrTrNodeTemp = 0x%lx, BiThrTrNodeTemp->RightChild = 0x%lx\n", (long unsigned int )BiThrTrNodeTemp, (long unsigned int )BiThrTrNodeTemp->RightChild);
	}

	printf("PrintThrTree end\n");
}

void BuildBinaryThreadTree(BINARY_THREAD_TREE_NODE **BiThrTreeNode, BINARY_THREAD_TREE_NODE_DATA *DataPtr) {
	char IfExistNodeFlag = 1;
	Index = 0;
	BINARY_THREAD_TREE_NODE *BiThrTrHeadNode = NULL;

	/*HeadNode*/
	*BiThrTreeNode = (BINARY_THREAD_TREE_NODE *)malloc(sizeof(BINARY_THREAD_TREE_NODE));
	BiThrTrHeadNode = *BiThrTreeNode;
	BiThrTrHeadNode->Data = 'H';
	BiThrTrHeadNode->IfExistDirectLeftNodeFlag = 1;
	BiThrTrHeadNode->IfExistDirectRightNodeFlag = 1;
	BiThrTrHeadNode->RightChild = (BINARY_THREAD_TREE_NODE *)malloc(sizeof(BINARY_THREAD_TREE_NODE));
	BiThrTrHeadNode->LeftChild = NULL;

	printf("BuildBinaryThreadTree start\n");
	//printf("BiThrTrHeadNode = 0x%lx\n", (long unsigned int)BiThrTrHeadNode);

	   /*Build tree*/
	PreOrderBuildBiThrTree(&(BiThrTrHeadNode->LeftChild), DataPtr, IfExistNodeFlag);

	BiThrTrPreNode = BiThrTrHeadNode;

	// printf("\nPreOrderTraversePrintBinaryThreadTree\n"); 
	// PreOrderTraversePrintBinaryThreadTree(BiThrTrHeadNode->LeftChild);
	// printf("InOrderTraversePrintBinaryThreadTree\n"); 
	// InOrderTraversePrintBinaryThreadTree(BiThrTrHeadNode->LeftChild);
	// printf("PostOrderTraversePrintBinaryThreadTree\n");
	// PostOrderTraversePrintBinaryThreadTree(BiThrTrHeadNode->LeftChild);

	   /*In Order thread*/
	printf("\nInOrderThrBiTree\n");
	InOrderThrBiTree(BiThrTrHeadNode->LeftChild);

	BiThrTrPreNode->RightChild = BiThrTrHeadNode;
	BiThrTrHeadNode->RightChild = BiThrTrPreNode;

	PrintThrTree(BiThrTrHeadNode);

	printf("BuildBinaryThreadTree end\n");
}

4 测试用例

typedef struct _BINARY_THREAD_TREE_NODE_DATA {
	char BiThrTreeData;
	char IfExistDirectLeftNodeFlag;
	char IfExistDirectRightNodeFlag;
	char IsExistLeftChildFlag;
	char IsExistRightChildFlag;
}BINARY_THREAD_TREE_NODE_DATA;

/*BINARY_THREAD_TREE*/
int PreOrderTraverseCmpPreOderBuildBiThrTree(const BINARY_THREAD_TREE_NODE_DATA *CmpNode, int Index, const BINARY_THREAD_TREE_NODE *BiThrTreeNode, int PreOrderTraverseCmpBiThrTreeNum) {
	BINARY_THREAD_TREE_NODE *BiThrTrNodeTemp = BiThrTreeNode->LeftChild;

	printf("\n\nTest PreOrderTraverseCmpPreOderBuildBiThrTree start\n");
	//printf("Root Node, BiThrTrNodeTemp = 0x%lx, BiThrTrNodeTemp->Data = %c, BiThrTrNodeTemp->LeftChild = 0x%lx, BiThrTrNodeTemp->RightChild = 0x%lx\n", (long unsigned int)BiThrTrNodeTemp, BiThrTrNodeTemp->Data, (long unsigned int)BiThrTrNodeTemp->LeftChild, (long unsigned int)BiThrTrNodeTemp->RightChild);
	while (BiThrTrNodeTemp != BiThrTreeNode) {
		//printf("test01\n");
		while (BiThrTrNodeTemp->IfExistDirectLeftNodeFlag != 0) {
			BiThrTrNodeTemp = BiThrTrNodeTemp->LeftChild;
		}

		printf("BiThrTrNodeTemp = 0x%lx, BiThrTrNodeTemp->Data = %c, BiThrTrNodeTemp->LeftChild = 0x%lx, BiThrTrNodeTemp->RightChild = 0x%lx\n", (long unsigned int)BiThrTrNodeTemp, BiThrTrNodeTemp->Data, (long unsigned int)BiThrTrNodeTemp->LeftChild, (long unsigned int)BiThrTrNodeTemp->RightChild);
		printf("CmpNode[Index].BiThrTreeData = %c\n", CmpNode[Index].BiThrTreeData);
		if (CmpNode[Index++].BiThrTreeData == BiThrTrNodeTemp->Data) {
			PreOrderTraverseCmpBiThrTreeNum++;
		}

		while ((BiThrTrNodeTemp->IfExistDirectRightNodeFlag == 0) && (BiThrTrNodeTemp->RightChild != BiThrTreeNode)) {
			BiThrTrNodeTemp = BiThrTrNodeTemp->RightChild;
			printf("BiThrTrNodeTemp = 0x%lx, BiThrTrNodeTemp->Data = %c, BiThrTrNodeTemp->LeftChild = 0x%lx, BiThrTrNodeTemp->RightChild = 0x%lx\n", (long unsigned int)BiThrTrNodeTemp, BiThrTrNodeTemp->Data, (long unsigned int)BiThrTrNodeTemp->LeftChild, (long unsigned int)BiThrTrNodeTemp->RightChild);
			printf("CmpNode[Index].BiThrTreeData = %c\n", CmpNode[Index].BiThrTreeData);
			if (CmpNode[Index++].BiThrTreeData == BiThrTrNodeTemp->Data) {
				PreOrderTraverseCmpBiThrTreeNum++;
			}
		}

		BiThrTrNodeTemp = BiThrTrNodeTemp->RightChild;
		//printf("BiThrTrNodeTemp = 0x%lx, BiThrTrNodeTemp->RightChild = 0x%lx\n", (long unsigned int )BiThrTrNodeTemp, (long unsigned int )BiThrTrNodeTemp->RightChild);
	}

	printf("PreOrderTraverseCompareBinaryThreadTree03 end\n");
	return PreOrderTraverseCmpBiThrTreeNum;
}

void CmpPreOderBuildBiThrTree(const BINARY_THREAD_TREE_NODE_DATA *CmpNode, int Index, const BINARY_THREAD_TREE_NODE *BiThrTreeNode, int NodeNum) {
	//unsigned char Index = 0;
	int PreOrderTraverseCmpBiThrTreeNum = 0;
	//Index = 0;

	TestNum++;

	PreOrderTraverseCmpBiThrTreeNum = PreOrderTraverseCmpPreOderBuildBiThrTree(CmpNode, Index, BiThrTreeNode, PreOrderTraverseCmpBiThrTreeNum);
	printf("PreOrderTraverseCmpBiThrTreeNum = %d, NodeNum = %d\n", PreOrderTraverseCmpBiThrTreeNum, NodeNum);
	if (PreOrderTraverseCmpBiThrTreeNum != NodeNum) {
		FaildNum++;
	}
	else {
		PassNum++;
	}
}


/*BINARY_THREAD_TREE*/
void TestBuildBinaryThreadTree(void) {
	/*Test01*/
	//    A
	//  B    C
	BINARY_THREAD_TREE_NODE  *BiThrTreeNodePtr01 = NULL;
	BINARY_THREAD_TREE_NODE_DATA  BiThrTreeNodeData01[] = { {'A', 1, 1, 1, 1}, {'B', 0, 0, 0, 0}, {'C', 0, 0, 0, 0} };
	int NodeNum01 = 3;
	char IfExistNodeFlag01 = 1;
	BINARY_THREAD_TREE_NODE_DATA  CmpBiThrTreeNodeData01[] = { {'B', 0, 0, 0, 0}, {'A', 1, 1, 1, 1}, {'C', 0, 0, 0, 0} };
	int Index01 = 0;

	//    A
	//  B    E
	// C  D  F  G
	BINARY_THREAD_TREE_NODE  *BiThrTreeNodePtr02 = NULL;
	BINARY_THREAD_TREE_NODE_DATA  BiThrTreeNodeData02[] = { {'A', 1, 1, 1, 1}, {'B', 1, 1, 1, 1}, {'C', 0, 0, 0, 0}, {'D', 0, 0, 0, 0},
				 {'E', 1, 1, 1, 1}, {'F', 0, 0, 0, 0}, {'G', 0, 0, 0, 0} };
	int NodeNum02 = 7;

	BINARY_THREAD_TREE_NODE_DATA  CmpBiThrTreeNodeData02[] = { {'C', 0, 0, 0, 0}, {'B', 0, 0, 0, 0}, {'D', 0, 0, 0, 0}, {'A', 1, 1, 1, 1},
				   {'F', 0, 0, 0, 0}, {'E', 1, 1, 1, 1}, {'G', 0, 0, 0, 0} };
	int Index02 = 0;

	//    A
	//  B    C
	//   D    
	BINARY_THREAD_TREE_NODE  *BiThrTreeNodePtr03 = NULL;
	BINARY_THREAD_TREE_NODE_DATA BiThrTreeNodeData03[] = { {'A', 1, 1, 1, 1}, {'B', 0, 1, 0, 1}, {'D', 0, 0, 0, 0}, {'C', 0, 0, 0, 0} };
	int NodeNum03 = 4;
	BINARY_THREAD_TREE_NODE_DATA  CmpBiThrTreeNodeData03[] = { {'B', 0, 0, 0, 0}, {'D', 0, 0, 0, 0}, {'A', 1, 1, 1, 1}, {'C', 0, 0, 0, 0} };
	int Index03 = 0;


	printf("-------Test start----------\n");
	InitNum();

	/*Test01*/
	printf("\n-------Test 01----------\n");
	BuildBinaryThreadTree(&BiThrTreeNodePtr01, BiThrTreeNodeData01);
	CmpPreOderBuildBiThrTree(CmpBiThrTreeNodeData01, Index01, BiThrTreeNodePtr01, NodeNum01);


	/*Test02*/
	printf("\n-------Test 02----------\n");
	BuildBinaryThreadTree(&BiThrTreeNodePtr02, BiThrTreeNodeData02);
	CmpPreOderBuildBiThrTree(CmpBiThrTreeNodeData02, Index02, BiThrTreeNodePtr02, NodeNum02);

	/*Test03*/
	printf("\n-------Test 03----------\n");
	BuildBinaryThreadTree(&BiThrTreeNodePtr03, BiThrTreeNodeData03);
	CmpPreOderBuildBiThrTree(CmpBiThrTreeNodeData03, Index03, BiThrTreeNodePtr03, NodeNum03);

	/*Test Result*/
	printf("\n-------Test result----------\n");
	TestResult();
}

打印结果

-------Test start----------

-------Test 01----------

BuildBinaryThreadTree start

InOrderThrBiTree

BiThrTrNodeTemp = 0xcf3ee0, BiThrTrNodeTemp->Data = B, BiThrTrNodeTemp->LeftChild = 0xcf4d00, BiThrTrNodeTemp->RightChild = 0xcf3ea8

BiThrTrNodeTemp = 0xcf3ea8, BiThrTrNodeTemp->Data = A, BiThrTrNodeTemp->LeftChild = 0xcf3ee0, BiThrTrNodeTemp->RightChild = 0xcf8da0

BiThrTrNodeTemp = 0xcf8da0, BiThrTrNodeTemp->Data = C, BiThrTrNodeTemp->LeftChild = 0xcf3ea8, BiThrTrNodeTemp->RightChild = 0xcf4d00

PrintThrTree end

BuildBinaryThreadTree end

Test PreOrderTraverseCmpPreOderBuildBiThrTree start

BiThrTrNodeTemp = 0xcf3ee0, BiThrTrNodeTemp->Data = B, BiThrTrNodeTemp->LeftChild = 0xcf4d00, BiThrTrNodeTemp->RightChild = 0xcf3ea8

CmpNode[Index].BiThrTreeData = B

BiThrTrNodeTemp = 0xcf3ea8, BiThrTrNodeTemp->Data = A, BiThrTrNodeTemp->LeftChild = 0xcf3ee0, BiThrTrNodeTemp->RightChild = 0xcf8da0

CmpNode[Index].BiThrTreeData = A

BiThrTrNodeTemp = 0xcf8da0, BiThrTrNodeTemp->Data = C, BiThrTrNodeTemp->LeftChild = 0xcf3ea8, BiThrTrNodeTemp->RightChild = 0xcf4d00

CmpNode[Index].BiThrTreeData = C

PreOrderTraverseCompareBinaryThreadTree03 end

PreOrderTraverseCmpBiThrTreeNum = 3, NodeNum = 3

-------Test 02----------

BuildBinaryThreadTree start

InOrderThrBiTree

BiThrTrNodeTemp = 0xcfd648, BiThrTrNodeTemp->Data = C, BiThrTrNodeTemp->LeftChild = 0xcf8dd8, BiThrTrNodeTemp->RightChild = 0xcf8e80

BiThrTrNodeTemp = 0xcf8e80, BiThrTrNodeTemp->Data = B, BiThrTrNodeTemp->LeftChild = 0xcfd648, BiThrTrNodeTemp->RightChild = 0xcfd808

BiThrTrNodeTemp = 0xcfd808, BiThrTrNodeTemp->Data = D, BiThrTrNodeTemp->LeftChild = 0xcf8e80, BiThrTrNodeTemp->RightChild = 0xcf8e48

BiThrTrNodeTemp = 0xcf8e48, BiThrTrNodeTemp->Data = A, BiThrTrNodeTemp->LeftChild = 0xcf8e80, BiThrTrNodeTemp->RightChild = 0xcfd5d8

BiThrTrNodeTemp = 0xcfd5a0, BiThrTrNodeTemp->Data = F, BiThrTrNodeTemp->LeftChild = 0xcf8e48, BiThrTrNodeTemp->RightChild = 0xcfd5d8

BiThrTrNodeTemp = 0xcfd5d8, BiThrTrNodeTemp->Data = E, BiThrTrNodeTemp->LeftChild = 0xcfd5a0, BiThrTrNodeTemp->RightChild = 0xcfd4c0

BiThrTrNodeTemp = 0xcfd4c0, BiThrTrNodeTemp->Data = G, BiThrTrNodeTemp->LeftChild = 0xcfd5d8, BiThrTrNodeTemp->RightChild = 0xcf8dd8

PrintThrTree end

BuildBinaryThreadTree end

Test PreOrderTraverseCmpPreOderBuildBiThrTree start

BiThrTrNodeTemp = 0xcfd648, BiThrTrNodeTemp->Data = C, BiThrTrNodeTemp->LeftChild = 0xcf8dd8, BiThrTrNodeTemp->RightChild = 0xcf8e80

CmpNode[Index].BiThrTreeData = C

BiThrTrNodeTemp = 0xcf8e80, BiThrTrNodeTemp->Data = B, BiThrTrNodeTemp->LeftChild = 0xcfd648, BiThrTrNodeTemp->RightChild = 0xcfd808

CmpNode[Index].BiThrTreeData = B

BiThrTrNodeTemp = 0xcfd808, BiThrTrNodeTemp->Data = D, BiThrTrNodeTemp->LeftChild = 0xcf8e80, BiThrTrNodeTemp->RightChild = 0xcf8e48

CmpNode[Index].BiThrTreeData = D

BiThrTrNodeTemp = 0xcf8e48, BiThrTrNodeTemp->Data = A, BiThrTrNodeTemp->LeftChild = 0xcf8e80, BiThrTrNodeTemp->RightChild = 0xcfd5d8

CmpNode[Index].BiThrTreeData = A

BiThrTrNodeTemp = 0xcfd5a0, BiThrTrNodeTemp->Data = F, BiThrTrNodeTemp->LeftChild = 0xcf8e48, BiThrTrNodeTemp->RightChild = 0xcfd5d8

CmpNode[Index].BiThrTreeData = F

BiThrTrNodeTemp = 0xcfd5d8, BiThrTrNodeTemp->Data = E, BiThrTrNodeTemp->LeftChild = 0xcfd5a0, BiThrTrNodeTemp->RightChild = 0xcfd4c0

CmpNode[Index].BiThrTreeData = E

BiThrTrNodeTemp = 0xcfd4c0, BiThrTrNodeTemp->Data = G, BiThrTrNodeTemp->LeftChild = 0xcfd5d8, BiThrTrNodeTemp->RightChild = 0xcf8dd8

CmpNode[Index].BiThrTreeData = G

PreOrderTraverseCompareBinaryThreadTree03 end

PreOrderTraverseCmpBiThrTreeNum = 7, NodeNum = 7

-------Test 03----------

BuildBinaryThreadTree start

InOrderThrBiTree

BiThrTrNodeTemp = 0xcfd680, BiThrTrNodeTemp->Data = B, BiThrTrNodeTemp->LeftChild = 0xcfd610, BiThrTrNodeTemp->RightChild = 0xcfd6f0

BiThrTrNodeTemp = 0xcfd6f0, BiThrTrNodeTemp->Data = D, BiThrTrNodeTemp->LeftChild = 0xcfd680, BiThrTrNodeTemp->RightChild = 0xcfd7d0

BiThrTrNodeTemp = 0xcfd7d0, BiThrTrNodeTemp->Data = A, BiThrTrNodeTemp->LeftChild = 0xcfd680, BiThrTrNodeTemp->RightChild = 0xcfd488

BiThrTrNodeTemp = 0xcfd488, BiThrTrNodeTemp->Data = C, BiThrTrNodeTemp->LeftChild = 0xcfd7d0, BiThrTrNodeTemp->RightChild = 0xcfd610

PrintThrTree end

BuildBinaryThreadTree end

Test PreOrderTraverseCmpPreOderBuildBiThrTree start

BiThrTrNodeTemp = 0xcfd680, BiThrTrNodeTemp->Data = B, BiThrTrNodeTemp->LeftChild = 0xcfd610, BiThrTrNodeTemp->RightChild = 0xcfd6f0

CmpNode[Index].BiThrTreeData = B

BiThrTrNodeTemp = 0xcfd6f0, BiThrTrNodeTemp->Data = D, BiThrTrNodeTemp->LeftChild = 0xcfd680, BiThrTrNodeTemp->RightChild = 0xcfd7d0

CmpNode[Index].BiThrTreeData = D

BiThrTrNodeTemp = 0xcfd7d0, BiThrTrNodeTemp->Data = A, BiThrTrNodeTemp->LeftChild = 0xcfd680, BiThrTrNodeTemp->RightChild = 0xcfd488

CmpNode[Index].BiThrTreeData = A

BiThrTrNodeTemp = 0xcfd488, BiThrTrNodeTemp->Data = C, BiThrTrNodeTemp->LeftChild = 0xcfd7d0, BiThrTrNodeTemp->RightChild = 0xcfd610

CmpNode[Index].BiThrTreeData = C

PreOrderTraverseCompareBinaryThreadTree03 end

PreOrderTraverseCmpBiThrTreeNum = 4, NodeNum = 4

-------Test result----------

Print test result;

TestNum = 3, PassNum = 3, FaildNum = 0

标签：RightChild,BiThrTrNodeTemp,BiThrTreeNode,int,C语言,LeftChild,二叉树,Data,线索
From： https://www.cnblogs.com/meditatorss/p/17053707.html

相关文章

  • 算法刷题 Day 16 | 104.二叉树的最大深度 111.二叉树的最小深度 222.完全二叉树的节点
    今日内容：二叉树的最大深度559.n叉树的最大深度二叉树的最小深度完全二叉树的节点个数迭代法，大家可以直接过，二刷有精力的时候再去掌握迭代法。详细布置104......
  • 编程：C语言内存的堆栈模型
    内存：C语言内存的堆栈模型    一、C语言内存的堆栈模型 1、栈：栈底是高地址，栈顶是低地址。栈空间的地址生长方向：从高地址到低地址。 2、堆：堆底是低地......
  • c语言——函数及递归
    程序中一旦调用了某个函数，该函数就会完成特定的计算，然后返回到调用它的地方函数分为库函数和自定义函数一、库函数io函数都在头文件stdio中字符串操作函数都在头文件string......
  • C语言中类型转换的两种方式
    类型转换1.定义：不同类型的数据混合运算时需要进行类型转换（conversion），将不同类型的数据转换成相同类型的数据后再进行计算。2.分类：（1）隐式类型转换*编译系统自动进行转换。*在......
  • 如何用电脑写C语言
    大学教学都是用的devidc++或者c语言实操系统，我们以c语言实操系统为例1.浏览器打开：​​点击下载​​用baidu云或者网站上显示支持的网站下载软件即可，如图所示2.下载完成后双......
  • C语言中~与!的区别
    !是逻辑非or否定​凡是a的值不为0的，!a就等于0；​如果a的值为0，则!a的值为1而~这个是按位取反比如inta=2;用二进制表示为00000010;则!a=0......
  • 【LeeCode】637.二叉树的层平均值
    【题目描述】给定一个非空二叉树的根节点 ​​​root​​​ ,以数组的形式返回每一层节点的平均值。与实际答案相差 ​​​10-5​​​ 以内的答案可以被接受。​​http......
  • 【LeeCode】199.二叉树的右视图
    【题目描述】给定一个二叉树的 根节点 ​​​​root​​​​，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值​​​​https://leetcode.cn/proble......
  • c语言数组
    所谓数组，就是一个集合，里面存放了相同类型的数据元素，且是由连续的内存位置组成的一、一维数组1.定义方式：1）数据类型数组名[数组长度];2）数据类型数组名[数组长度]={值1，值2，.........
  • C语言那些事儿 1,认识C语言并在编译环境中书写HelloWord
    网友说：C语言和C++区别是什么？我想学C++，因为C语言听起来好low啊。首先啊，小伙子有这个问题和想法是对的，我之前也问过同样的问题~那么，既然你问了，我也就浅浅的讲一讲，我也就不说的......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99