树、二叉树
树
一、基本概念
1、只有一个前驱,但是可以有多个后继
2、节点
1.根节点:最顶层节点(没有前驱)
2.分支节点:有前驱也有后继
3.叶子节点:没有后继的节点
3、层、深度、高度
层:根节点所在为第一层,每过一个分支节点,层数+1
深度: 从根节点出发到达节点的分支节点个数称为该节点的深度
高度:从叶子节点出发到该节点最大的节点个数称为该节点的高度
树的高度:整个树形结构中高度最高的节点的高度称为树的高度
树的深度:整个树形结构中深度最深的节点的深度称为树的深度
树的层数 == 树的高度 == 树的深度
节点的度: 叶子节点度数为0
节点的后继的个数
二叉树
所有节点中最大度数为2的树形结构
一、基本概念
1、满二叉树:满二叉树是一种特殊的二叉树,其中每个层级的节点数都是最大值,即每个层级都是完全填充的
2、完全二叉树:所有节点展开后,节点编号排列连续
3、二叉树特点:叶子节点、只有左孩子、只有右孩子、左右孩子都有
4、满二叉树:二叉树第k层最多有2^(k-1)个节点
5、满二叉树有k层,则所有节点数为 2^k -1
二、基本操作
1、创建满二叉树
TreeNode *CreateCompleteTree(int StartNo, int EndNo)
{TreeNode *pTmpNode = NULL;pTmpNode = malloc(sizeof(TreeNode));if (NULL == pTmpNode){return NULL;}pTmpNode->pLeftChild = pTmpNode->pRightChild = NULL;pTmpNode->No = StartNo;if (2 * StartNo <= EndNo){pTmpNode->pLeftChild = CreateCompleteTree(2*StartNo, EndNo);}if (2 * StartNo + 1 <= EndNo){pTmpNode->pRightChild = CreateCompleteTree(2*StartNo+1, EndNo);}return pTmpNode;
}
2、前序遍历:根左右
int PreOrderBinTree(TreeNode *pRoot)
{printf("%c ", pRoot->Data);if (pRoot->pLeftChild != NULL){PreOrderBinTree(pRoot->pLeftChild);}if (pRoot->pRightChild != NULL){PreOrderBinTree(pRoot->pRightChild);}return 0;
}
3、中序遍历:左根右
int InOrderBinTree(TreeNode *pRoot)
{if (pRoot->pLeftChild != NULL){InOrderBinTree(pRoot->pLeftChild);}printf("%c ", pRoot->Data);if (pRoot->pRightChild != NULL){InOrderBinTree(pRoot->pRightChild);}return 0;
}
4、后续遍历:左右根
int PostOrderBinTree(TreeNode *pRoot)
{if (pRoot->pLeftChild != NULL){PostOrderBinTree(pRoot->pLeftChild);}if (pRoot->pRightChild != NULL){PostOrderBinTree(pRoot->pRightChild);}printf("%c ", pRoot->Data);return 0;
}
5、层序遍历
int LayerOrderBinTree(TreeNode *pRoot)
{struct list_head head;Data_t *pTmpNode = NULL;Data_t *pFreeNode = NULL;//树形结构为NULL直接返回if (NULL == pRoot){return -1;} //初始化队列INIT_LIST_HEAD(&head);//申请一个节点(将树形结构地址放入链表中)pTmpNode = malloc(sizeof(Data_t));if (NULL == pTmpNode){return -1;}pTmpNode->pData = pRoot;//入队list_add_tail(&pTmpNode->node, &head);//只要队列不为NULL,出队一个元素,打印该元素,左右孩子不为NULL,入队while (!list_empty(&head)){//获得队头元素pFreeNode = list_entry(head.next, Data_t, node);printf("%c ", pFreeNode->pData->Data);//队头元素的左孩子入队if (NULL != pFreeNode->pData->pLeftChild){ pTmpNode = malloc(sizeof(Data_t));if (NULL == pTmpNode){return -1;}pTmpNode->pData = pFreeNode->pData->pLeftChild;list_add_tail(&pTmpNode->node, &head);}//队头元素的右孩子入队if (NULL != pFreeNode->pData->pRightChild){ pTmpNode = malloc(sizeof(Data_t));if (NULL == pTmpNode){return -1;}pTmpNode->pData = pFreeNode->pData->pRightChild;list_add_tail(&pTmpNode->node, &head);}//队头元素出队list_del(&pFreeNode->node);//释放该节点free(pFreeNode);}return 0;
}
6、创建完全二叉树
TreeNode *CreateBinTree(void)
{char TmpData = 0;TreeNode *pTmpNode = NULL;scanf(" %c", &TmpData);if ('#' == TmpData){return NULL;}else{pTmpNode = malloc(sizeof(TreeNode));if (NULL == pTmpNode){return NULL;}pTmpNode->Data = TmpData;pTmpNode->pLeftChild = CreateBinTree();pTmpNode->pRightChild = CreateBinTree();}return pTmpNode;
}