数据结构C代码6.1：二叉树

• 1、结构体定义
• 2、初始化
• 3、判断队列是否为空
• 4、结点入队列
• 5、删除结点
• 6、构造结点
• 7、字符串转化为二叉树
• 8、四种遍历
• 9、测试用例
• 11、运行结果
• 12、总结

typedef struct BTNode 
{
	char element;
	BTNode* left;
	BTNode* right;
}*BTNodePtr;

typedef struct BTNodePtrQueue
{
	BTNodePtr* nodePtrs;
	int front;
	int rear;
}BTNodePtrQueue,*QueuePtr;

动态分配空间

QueuePtr initQueue()
{
	QueuePtr resultQueuePtr=(QueuePtr)malloc(sizeof(struct BTNodePtrQueue));
	resultQueuePtr->nodePtrs=(BTNodePtr*)malloc(sizeof(BTNodePtr)*QUEUE_SIZE);
	resultQueuePtr->front=0;
	resultQueuePtr->rear=1;
	return resultQueuePtr;
}

bool isQueueEmpty(QueuePtr paraQueuePtr)
{
	if((paraQueuePtr->front+1)%QUEUE_SIZE==(paraQueuePtr->rear))
	{
		return true;
	}
	return false;
}

void enqueue(QueuePtr paraQueuePtr,BTNodePtr paraBTNodePtr)
{
	printf("front=%d,rear=%d.rn",paraQueuePtr->front,paraQueuePtr->rear);
	if((paraQueuePtr->rear+1)%QUEUE_SIZE==paraQueuePtr->front%QUEUE_SIZE)
	{
		printf("error,trying to enqueue %c.queue full.rn",paraBTNodePtr->element);
		return;
	}
	paraQueuePtr->nodePtrs[paraQueuePtr->rear]=paraBTNodePtr;
	paraQueuePtr->rear=(paraQueuePtr->rear+1)%QUEUE_SIZE;
	printf("enqueue %c ends.rn",paraBTNodePtr->element);
}

BTNodePtr dequeue(QueuePtr paraQueuePtr)
{
	if(isQueueEmpty(paraQueuePtr))
	{
		printf("Error,empty queuern");
		return NULL;
	}
	paraQueuePtr->front=(paraQueuePtr->front+1)%QUEUE_SIZE;

	printf("dequeue %c endsrn",paraQueuePtr->nodePtrs[paraQueuePtr->front]->element);
	return paraQueuePtr->nodePtrs[paraQueuePtr->front];
}

BTNodePtr constructBTNode(char paraChar)
{
	BTNodePtr resultPtr=(BTNodePtr)malloc(sizeof(BTNode));
	resultPtr->element=paraChar;
	resultPtr->left=NULL;
	resultPtr->right=NULL;
	return resultPtr;
}

BTNodePtr stringToBTree(char* paraString)
{
	int i=0;
	char ch;

	QueuePtr tempQueuePtr=initQueue();

	BTNodePtr resultHeader;
	BTNodePtr tempParent,tempLeftChild,tempRightChild;

	ch=paraString[i];
	resultHeader=constructBTNode(ch);
	enqueue(tempQueuePtr,resultHeader);

	while(!isQueueEmpty(tempQueuePtr))
	{
		tempParent=dequeue(tempQueuePtr);
		i++;
		ch=paraString[i];
		if(ch!='#')
		{
			tempParent->left=NULL;
		}else{
			tempLeftChild=constructBTNode(ch);
			enqueue(tempQueuePtr,tempLeftChild);
			tempParent->left=tempLeftChild;
		}
		i++;
		ch=paraString[i];
		if(ch=='#')
		{
			tempParent->right=NULL;
		}else{
			tempRightChild=constructBTNode(ch);
			enqueue(tempQueuePtr,tempRightChild);
			tempParent->right=tempRightChild;
		}
	}
	return resultHeader;
}

①先序遍历
先序遍历可以想象为，一个小人从一棵二叉树根节点为起点，沿着二叉树外沿，逆时针走一圈回到根节点，路上遇到的元素顺序，就是先序遍历的结果。

先序遍历结果为：A B D H I E J C F K G

void preorder(BTNodePtr tempPtr)
{
	if(tempPtr==NULL)
	{
		return ;
	}
	printf("%c",tempPtr->element);
	preorder(tempPtr->left);
	preorder(tempPtr->right);
}

②中序遍历
中序遍历可以看成，二叉树每个节点，垂直方向投影下来（可以理解为每个节点从最左边开始垂直掉到地上），然后从左往右数，得出的结果便是中序遍历的结果。

中遍历结果为：H D I B E J A F K C G

void inorder(BTNodePtr tempPtr)
{
	if(tempPtr==NULL)
	{
		return;
	}
	inorder(tempPtr->left);
	printf("%c",tempPtr->element);
	inorder(tempPtr->right);
}

③后序遍历
后序比较难理解，就是一个一个单独的脱下来

后序遍历结果：H I D J E B K F G C A

void postorder(BTNodePtr tempPtr)
{
	if(tempPtr==NULL)
	{
		return ;
	}
	postorder(tempPtr->left);
	postorder(tempPtr->right);
	printf("%c",tempPtr->element);
}

④层次遍历
层次遍历很好理解，就是从根节点开始，一层一层，从上到下，每层从左到右，依次写值就可以了。

层次遍历结果：A B C D E F G H I J K

void levelwise(BTNodePtr paraTreePtr)
{
	char tempString[100];
	int i;
	QueuePtr tempQueuePtr=initQueue();
	BTNodePtr tempNodePtr;
	enqueue(tempQueuePtr,paraTreePtr);
	while(!isQueueEmpty(tempQueuePtr))
	{
		tempNodePtr=dequeue(tempQueuePtr);

		tempString[i]=tempNodePtr->element;
		i++;

		if(tempNodePtr->left!=NULL)
		{
			enqueue(tempQueuePtr,tempNodePtr->left);
		}
		if(tempNodePtr->right!=NULL)
		{
			enqueue(tempQueuePtr,tempNodePtr->right);
		}
	}
	tempString[i]='';

	printf("Levelwise:%srn",tempString);
}

该部分所用图均来自博主正弦定理

void BTreeTest()
{
	BTNodePtr tempHeader;
	tempHeader=constructBTNode('c');
	printf("There is only one node.Preorder visit:");
	preorder(tempHeader);
	printf("rn");

	char* tempString="acde#bf######";

	tempHeader=stringToBTree(tempString);
	printf("Preorder: ");
	preorder(tempHeader);
	printf("rn");
	printf("Inorder:");
	inorder(tempHeader);
	printf("rn");
	printf("Postorder:");
	postorder(tempHeader);
	printf("rn");
	printf("Levelwise");
	levelwise(tempHeader);
	printf("rn");
}
int main()
{
	BTreeTest();
	return 0;
}

性质1：在二叉树的第i层上至多有2^(i-1)个结点（i>=1）
性质2：深度为k的二叉树至多有2^k-1个结点（k>=1）
性质3：对任何一颗二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1
满二叉树：深度为k且含有2^k-1个结点的二叉树
完全二叉树：一棵深度为k的有n个结点的 二叉树 ，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与 满二叉树 中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。.
性质4：具有n个结点的完全二叉树的深度为（log2n)取下限+1