当前位置: 首页> 文旅> 艺术 > 数据结构——二叉树

数据结构——二叉树

时间:2025/7/12 2:09:18来源:https://blog.csdn.net/m0_61965705/article/details/141725755 浏览次数:0次

目录

二叉树

  满二叉树

​编辑 完全二叉树

​编辑完全二叉树链式结构及实现

1.结构体定义

2.递归实现完全二叉树创建

3.递归实现前序遍历

4.递归实现中序遍历

5.递归实现后序遍历

6.销毁

要从叶子节点往上free,类似后序遍历

7.创建非完全二叉树

8.获得树的高度,深度,层数

9.层序遍历


    :只有一个前驱,但是可以有多个后继
    根节点:最顶层节点(没有前驱)
    分支节点:有前驱也有后继
    叶子节点:没有后继的节点
    :根节点所在为第一层,每过一个分支节点,层数+1 
    深度: 从根节点出发到达节点的分支节点个数称为该节点的深度
    高度:从叶子节点出发到该节点最大的节点个数称为该节点的高度

    树的高度:整个树形结构中高度最高的节点的高度称为树的高度
    树的深度:整个树形结构中深度最深的节点的深度称为树的深度
    树的层数 == 树的高度 == 树的深度

    节点的度: 叶子节点度数为0 
                      节点的后继的个数

二叉树

            所有节点中最大度数为2的树形结构

  满二叉树

满二叉树是一种特殊的二叉树,其中每个层级的节点数都是最大值,即每个层级都是完全填充的(每一层都排满了)


 完全二叉树

所有节点展开后,节点编号排列连续(除了最后一层,其他每一层都排满了)

 二叉树特点:叶子节点、只有左孩子、只有右孩子、左右孩子都有
 满二叉树:二叉树第k层最多有2^(k-1)个节点 
 满二叉树有k层,则所有节点数为 2^k -1

二叉树的三种遍历方法:
    1.前序遍历:根左右
    2.中序遍历:左根右
    3.后续遍历:左右根

完全二叉树链式结构及实现
1.结构体定义
//二叉树节点类型 
typedef struct node 
{int No;struct node *pLeftChild;struct node *pRightChild;
}TreeNode;
2.递归实现完全二叉树创建
//创建完全二叉树
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;
}


 举例:

CreateCompleteTree(1,5)
        申请节点1
        节点1的pLeftChild=CreateCompleteTree(2,5);
                申请节点2
          节点2的pLeftChild=CreateCompleteTree(4,5)
                        申请节点4

            StartNo = 4,2*4 > 5不符合if判断条件了,然后就回到节点调用处,节点2的pLeftChild=CreateCompleteTree(4,5),这样就节点2的pLeftChild赋值成了节点4

                

                然后程序执行到节点2的pTmpNode->pRightChild = CreateCompleteTree(5, 5);

                        申请节点5

                 StartNo = 5,2*5 > 5不符合if判断条件了,然后就回到节点调用处,

节点2的pTmpNode->pRightChild = CreateCompleteTree(5, 5)这里,这样节点2的pLeftChild就赋值成了节点5,

                

                CreteComplete(2,5)执行结束,回到调用处,节点1的pLeftChild=CreateCompleteTree(2,5);这样节点1的pLeftChild就赋值成了节点2

                   然后程序执行到节点1的pTmpNode->pRightChild = CreateCompleteTree(3, 5);

                      申请节点3

                 StartNo = 3,2*3 > 5不符合if判断条件了,然后就回到节点调用处,

节点1的pTmpNode->pRightChild = CreateCompleteTree(3, 5)这里,这样节点1的pLeftChild就赋值成了节点3

                程序执行结束

3.递归实现前序遍历
int PreOrderBinTree(TreeNode *pRoot)
{printf("%c ", pRoot->Data);if (pRoot->pLeftChild != NULL){PreOrderBinTree(pRoot->pLeftChild);}if (pRoot->pRightChild != NULL){PreOrderBinTree(pRoot->pRightChild);}return 0;
}
4.递归实现中序遍历
int InOrderBinTree(TreeNode *pRoot)
{if (pRoot->pLeftChild != NULL){InOrderBinTree(pRoot->pLeftChild);}printf("%c ", pRoot->Data);if (pRoot->pRightChild != NULL){InOrderBinTree(pRoot->pRightChild);}return 0;
}
5.递归实现后序遍历
int PostOrderBinTree(TreeNode *pRoot)
{if (pRoot->pLeftChild != NULL){PostOrderBinTree(pRoot->pLeftChild);}if (pRoot->pRightChild != NULL){PostOrderBinTree(pRoot->pRightChild);}printf("%c ", pRoot->Data);return 0;
}
6.销毁
要从叶子节点往上free,类似后序遍历
int DestroyBinTree(TreeNode **ppRoot)
{if ((*ppRoot)->pLeftChild != NULL){DestroyBinTree(&(*ppRoot)->pLeftChild);}if ((*ppRoot)->pRightChild != NULL){DestroyBinTree(&(*ppRoot)->pRightChild);}free(*ppRoot);*ppRoot = NULL;return 0;
}
7.创建非完全二叉树

//创建非完全二叉树
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;
}
8.获得树的高度,深度,层数
//获得树的高度、深度、层数
int GetBinTreeHeight(TreeNode *pRoot)
{int LeftHeight = 0;int RightHeight = 0;if (NULL == pRoot){return 0;}LeftHeight = GetBinTreeHeight(pRoot->pLeftChild);RightHeight = GetBinTreeHeight(pRoot->pRightChild);return (LeftHeight > RightHeight ? LeftHeight : RightHeight) + 1;
}
9.层序遍历

一层一层遍历

层序遍历:A B C D E F G H I

使用队列实现,先将根节点A放到队列中,A出队,打印A,并且将A的(B)和C)放到队列中,然后B出队,打印B,将B的左孩子(D)和有孩子(E)放到队列中,然后C出队,依次类推

//层序遍历
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;
}

10.非递归表实现前序遍历

 使用栈结构,因为栈有类似回溯的作用,让根节点的左孩子(A,B,D)都入栈,入栈的时候打印,入栈的元素,然后让栈顶元素出栈,元素出栈时,判断一下,它的右孩子,是否为空,不为空,就将它右孩子以及右孩子的左孩子都入栈,然后再判断出栈顶元素,依次类推,直到栈为空。

    

//前序遍历(非递归)
int PreOrderBinTreeByStack(TreeNode *pRoot)
{struct list_head stack;Data_t *pNewNode = NULL;Data_t *pFreeNode = NULL;TreeNode *pTmpTreeNode = NULL;if (NULL == pRoot){return -1;}INIT_LIST_HEAD(&stack);pTmpTreeNode = pRoot;while (1){while (pTmpTreeNode != NULL){pNewNode = malloc(sizeof(Data_t));if (NULL == pNewNode){return -1;}pNewNode->pData = pTmpTreeNode;printf("%c ", pNewNode->pData->Data);list_add(&pNewNode->node, &stack);pTmpTreeNode = pTmpTreeNode->pLeftChild;}if (list_empty(&stack)){break;}pFreeNode = list_entry(stack.next, Data_t, node);list_del(&pFreeNode->node);pTmpTreeNode = pFreeNode->pData->pRightChild;free(pFreeNode);}return 0;
}

 11.非递归表实现中序遍历

和前序一样,唯一区别,就是要在出栈时打印数据

//非递归中序遍历
int InOrderBinTreeByStack(TreeNode *pRoot)
{struct list_head stack;Data_t *pNewNode = NULL;Data_t *pFreeNode = NULL;TreeNode *pTmpTreeNode = NULL;if(NULL == pRoot){return -1;}INIT_LIST_HEAD(&stack);pTmpTreeNode = pRoot;while(1){while(pTmpTreeNode != NULL){pNewNode = malloc(sizeof(Data_t));if(NULL == pNewNode){return -1;}pNewNode->pData = pTmpTreeNode;list_add(&pNewNode->node,&stack);pTmpTreeNode = pTmpTreeNode->pLeftChild;}if(list_empty(&stack)){break;}pFreeNode = list_entry(stack.next,Data_t,node);printf("%c ",pFreeNode->pData->Data);list_del(&pFreeNode->node);pTmpTreeNode = pFreeNode->pData->pRightChild;free(pFreeNode);}return 0;}

12.非递归表实现后序遍历

设置一个标志位,第一次入栈的时候,置1,然后二次入栈的时候置为2

//非递归后序遍历
int PostOrderBinTreeByStack(TreeNode *pRoot)
{struct list_head stack;Data_t *pNewNode = NULL;Data_t *pFreeNode = NULL;TreeNode *pTmpTreeNode = NULL;if(NULL == pRoot){return -1;}INIT_LIST_HEAD(&stack);pTmpTreeNode = pRoot;while(1){while(pTmpTreeNode != NULL){pNewNode = malloc(sizeof(Data_t));if(NULL == pNewNode){return -1;}pNewNode->pData = pTmpTreeNode;pNewNode->pData->No = 1;list_add(&pNewNode->node,&stack);pTmpTreeNode = pTmpTreeNode->pLeftChild;}if(list_empty(&stack)){break;}pFreeNode = list_entry(stack.next,Data_t,node);if(pFreeNode->pData->No == 2){printf("%c ",pFreeNode->pData->Data);list_del(&pFreeNode->node);free(pFreeNode);continue;}else if(pFreeNode->pData->No == 1){list_del(&pFreeNode->node);pFreeNode->pData->No = 2;list_add(&pFreeNode->node,&stack);}pTmpTreeNode = pFreeNode->pData->pRightChild;}return 0;
}

关键字:数据结构——二叉树

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: