数据结构---二叉树的代码实现

一、二叉树的创建

1.1.完全二叉树的创建

1.2.非完全二叉树的创建

二、二叉树的递归遍历

2.1.前序遍历

2.2.中序遍历

2.3.后序遍历

三、二叉树的非递归遍历

3.1.前序遍历

3.2.中序遍历

3.3.后序遍历

3.4.层次遍历

四、树的高度

五、总结

以下代码均在内核链表（开源的代码）的基础上实现的。

一、二叉树的创建

1.1.完全二叉树的创建

TreeNode *CreateCompleteTree(int StartNo, int EndNo)
{TreeNode *pTmpNode = NULL;pTmpNode = malloc(sizeof(TreeNode));if (NULL == pTmpNode){return NULL;}memset(pTmpNode, 0, sizeof(TreeNode));pTmpNode->No = StartNo;pTmpNode->pLeftChild = pTmpNode->pRightChild = NULL;if (2 * StartNo <= EndNo){pTmpNode->pLeftChild = CreateCompleteTree(2 * StartNo, EndNo);}if (2 * StartNo + 1 <= EndNo){pTmpNode->pRightChild = CreateCompleteTree(2 * StartNo + 1, EndNo);}return pTmpNode;
}

1.2.非完全二叉树的创建

TreeNode *CreateBTree(void)
{char TmpData = 0;TreeNode *pTmpNode = NULL;scanf(" %c", &TmpData);if ('#' == TmpData){return NULL;}pTmpNode = malloc(sizeof(TreeNode));if (NULL == pTmpNode){return NULL;}memset(pTmpNode, 0, sizeof(TreeNode));pTmpNode->Data = TmpData;pTmpNode->pLeftChild = CreateBTree();pTmpNode->pRightChild = CreateBTree();return pTmpNode;
}

二、二叉树的递归遍历

2.1.前序遍历

int PreOrderBinTree(TreeNode *pRoot)
{   if (NULL == pRoot){return 0;}printf("%d ", pRoot->No);PreOrderBinTree(pRoot->pLeftChild);PreOrderBinTree(pRoot->pRightChild);return 0;
}

2.2.中序遍历

int InOrderBinTree(TreeNode *pRoot)
{   if (NULL == pRoot){return 0;}InOrderBinTree(pRoot->pLeftChild);printf("%d ", pRoot->No);InOrderBinTree(pRoot->pRightChild);return 0;
}

2.3.后序遍历

int PostOrderBinTree(TreeNode *pRoot)
{   if (NULL == pRoot){return 0;}PostOrderBinTree(pRoot->pLeftChild);printf("%d ", pRoot->No);PostOrderBinTree(pRoot->pRightChild);return 0;
}

三、二叉树的非递归遍历

3.1.前序遍历

先让根节点进栈，打印根节点，再让其左子树的所有左孩子依次进栈并打印，此时让栈顶元素出栈，判断下一个为栈顶元素的是否存在，如存在依次让他的所有左孩子再进栈并打印，依次类推，知道栈内无元素位置，就实现了二叉树的非递归前序遍历。

int PreOrderBinTreeByStack(TreeNode *pRoot)
{//判断树是否为空if (pRoot == NULL){return -1;}//初始化栈struct list_head head;INIT_LIST_HEAD(&head);//创建栈节点,方便后续树节点进栈Stack_t *pnewnode = NULL;Stack_t *pfreenode = NULL;//创建树节点指针,指向根节点TreeNode *ptmptreenode = NULL;ptmptreenode = pRoot;while (1){while (ptmptreenode != NULL){pnewnode = malloc(sizeof(Stack_t));if (pnewnode == NULL){return -1;}//根节点入栈pnewnode->data = ptmptreenode;//打印printf("%c ", pnewnode->data->data);//进栈list_add(&pnewnode->node, &head);//该左孩子,保存左孩子节点地址,让左孩子都进栈ptmptreenode = ptmptreenode->pLeftChild;}//如果栈空,则结束if (list_empty(&head)){break;}//获取栈顶节点的首地址pfreenode = list_entry(head.next, Stack_t, node);//让栈顶元素出栈list_del(&pfreenode->node);//获取出栈的树节点的右节点ptmptreenode = pfreenode->data->pRightChild;free(pfreenode);}return 0;
}

3.2.中序遍历

在前序遍历的过程中出栈一个元素打印一个元素就实现啦！

int InOrderBinTreeByStack(TreeNode *pRoot)
{//判断树是否为空if (pRoot == NULL){return -1;}//初始化栈struct list_head head;INIT_LIST_HEAD(&head);//创建栈节点,方便后续树节点进栈Stack_t *pnewnode = NULL;Stack_t *pfreenode = NULL;//创建树节点指针,指向根节点TreeNode *ptmptreenode = NULL;ptmptreenode = pRoot;while (1){while (ptmptreenode != NULL){pnewnode = malloc(sizeof(Stack_t));if (pnewnode == NULL){return -1;}//根节点入栈pnewnode->data = ptmptreenode;//进栈list_add(&pnewnode->node, &head);//该左孩子,保存左孩子节点地址,让左孩子都进栈ptmptreenode = ptmptreenode->pLeftChild;}//如果栈空,则结束if (list_empty(&head)){break;}//获取栈顶节点的首地址pfreenode = list_entry(head.next, Stack_t, node);//打印printf("%c ", pfreenode->data->data);//让栈顶元素出栈list_del(&pfreenode->node);//获取出栈的树节点的右节点ptmptreenode = pfreenode->data->pRightChild;free(pfreenode);}return 0;
}

3.3.后序遍历

先让根节点进栈，再让其左子树的所有左孩子依次进栈，此时让栈顶元素出栈，判断下一个为栈顶元素的是否存在，如存在依次让他的所有左孩子再进栈，然后出栈的元元素再次进栈，之后再次出栈，若出栈次数为2，则打印。依次类推，知道栈内无元素位置，就实现了二叉树的非递归后序遍历。

int PostOrderBinTreeByStack(TreeNode *pRoot)
{SeqStack *pTmpStack = NULL;TreeNode *pTmpNode = NULL;TreeNode *pTopNode = NULL;int k = 0;k = GetTreeHeight(pRoot);pTmpStack = CreateSeqStack(pow(2, k));pTmpNode = pRoot;while (1){while (pTmpNode != NULL){pTmpNode->flag = 1;PushSeqStack(pTmpStack, pTmpNode);pTmpNode = pTmpNode->pLeftChild;}if (IsEmptySeqStack(pTmpStack)){break;}pTopNode = PopSeqStack(pTmpStack);if (2 == pTopNode->flag){printf("%c ", pTopNode->Data);continue;}else if (1 == pTopNode->flag){pTopNode->flag = 2;PushSeqStack(pTmpStack, pTopNode);}pTmpNode = pTopNode->pRightChild;}printf("\n");DestroySeqStack(&pTmpStack);return 0;
}

3.4.层次遍历

借助队列实现，先让根节点进队列打印根节点；根节点出队列，让根节点的左右孩子依次进队列并打印，依次类推，知道队列为空，则顺序遍历完成。

int LayerOrderBTree(TreeNode *pRoot)
{SeqQueue *pTmpQueue = NULL;int k = 0;DataType Data;k = GetTreeHeight(pRoot);pTmpQueue = CreateSeqQueue(pow(2, k));EnterSeqQueue(pTmpQueue, pRoot);while (!IsEmptySeqQueue(pTmpQueue)){Data = QuitSeqQueue(pTmpQueue);printf("%c ", Data->Data);if (Data->pLeftChild != NULL){EnterSeqQueue(pTmpQueue, Data->pLeftChild);}if (Data->pRightChild != NULL){EnterSeqQueue(pTmpQueue, Data->pRightChild);}}printf("\n");DestroySeqQueue(&pTmpQueue);return 0;
}

四、树的高度

递归实现，分别递归求左子树和右子树的高度，比较最大的就为树的高度

int BinTreeHight(TreeNode *pRoot)
{int lefthight = 0;int righthight = 0;if (pRoot == NULL){return 0;}lefthight = BinTreeHight(pRoot->pLeftChild);righthight = BinTreeHight(pRoot->pRightChild);return lefthight >  righthight ? lefthight + 1 : righthight + 1;
}