当前位置：首页 > news >正文

数据结构：树

news 来源：原创 2024/9/19 23:59:31

树：

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

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

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

二叉树：

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

    满二叉树：满二叉树是一种特殊的二叉树，其中每个层级的节点数都是最大值，即每个层级都是完全填充的
    完全二叉树：所有节点展开后，节点编号排列连续

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

    二叉树的三种遍历方法：

    1.前序遍历：根左右

A B D E H C F I G
    2.中序遍历：左根右

D B E H A F I C G
    3.后续遍历：左右根

D H E B I F G C A

二叉树结构体

typedef struct node
{int No; //节点序号char data;//也可以是char类型的struct node *pLeftChild;//左孩子struct node *pRightChild;//右孩子}BinTree;

创建完全二叉树

BinTree *CreateBinTree(int Start,int End)
{BinTree *pRoot=NULL;pRoot=malloc(sizeof(BinTree));if(pRoot==NULL){return NULL;}pRoot->No=Start;pRoot->pLeftChild=NULL;pRoot->pRightChild=NULL;if(2*Start<=End){pRoot->pLeftChild = CreateBinTree(2*Start,End);}if(2*Start+1<=End){pRoot->pRightChild = CreateBinTree(2*Start+1,End);}return pRoot;
}

前序遍历（递归）

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

中序遍历（递归）

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

后序遍历（递归）

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

销毁二叉树（后序遍历思想）

int DestroyBinTree(BinTree **pRoot)
{if((*pRoot)->pLeftChild!=NULL){DestroyBinTree(&(*pRoot)->pLeftChild);}if((*pRoot)->pRightChild!=NULL){DestroyBinTree(&(*pRoot)->pRightChild);}free((*pRoot));*pRoot=NULL;return 0;
}

创建不完全二叉树

//输入#代表此节点不存在
//节点存在则再次递归调用本函数，创建其左右子树

BinTree *CreateUncompleteTree(void)
{BinTree *pRoot=NULL;char Tmpdata=0;scanf(" %c",&Tmpdata);if(Tmpdata=='#'){return NULL;}else{pRoot=malloc(sizeof(BinTree));if(pRoot==NULL){return NULL;}pRoot->data=Tmpdata;pRoot->pLeftChild=CreateUncompleteTree();pRoot->pRightChild=CreateUncompleteTree();}return pRoot;
}

获得树的高度

//每个节点的高度等于左子树或右子树中较高的子树高度 +1

int GetBinTreeHeight(BinTree *pRoot)
{int LeftHeight=0;int RightHeight=0;if(pRoot==NULL){return 0;}LeftHeight = GetBinTreeHeight(pRoot->pLeftChild);RightHeight=GetBinTreeHeight(pRoot->pRightChild);return (LeftHeight>RightHeight?LeftHeight:RightHeight)+1;
}

定义链表结构体（使用内核链表）

typedef struct Data
{struct list_head node;BinTree *pData;
}Data_t;

层次遍历

使用队列实现层次遍历

算法思想：

初始化：创建一个队列，并将根节点加入队列中。
循环处理：当队列不为空时，进行循环。
队列中第一个节点出队。
访问该节点（进行你需要的操作，如打印节点的值）。
如果该节点有左子节点，则将左子节点加入队列。
如果该节点有右子节点，则将右子节点加入队列。
结束：当队列为空时，表示所有节点都已经遍历完，算法结束。

int LayerOrderBinTree(BinTree *pRoot)
{struct list_head head;Data_t *pTmpNode=NULL;Data_t *pFreeNode=NULL;if(pRoot==NULL){return -1;}//创建链式队列INIT_LIST_HEAD(&head);//为根节点申请一块链式节点的空间pTmpNode=malloc(sizeof(Data_t));if(pTmpNode==NULL){return -1;}//链式节点的pData挂载根节点pTmpNode->pData=pRoot;//根节点入队list_add_tail(&pTmpNode->node,&head);while(!list_empty(&head)){//找到队头（要出栈的节点）pFreeNode=list_entry(head.next,Data_t,node);//打印队头printf(" %c",pFreeNode->pData->data);//判断要出栈的节点是否有左孩子，左孩子存在则入队if(pFreeNode->pData->pLeftChild!=NULL){pTmpNode=malloc(sizeof(Data_t));if(pTmpNode==NULL){return -1;}pTmpNode->pData=pFreeNode->pData->pLeftChild;list_add_tail(&pTmpNode->node,&head);}//判断要出栈的节点是否有右孩子，右孩子存在则入队if(pFreeNode->pData->pRightChild!=NULL){pTmpNode=malloc(sizeof(Data_t));if(pTmpNode==NULL){return -1;}pTmpNode->pData=pFreeNode->pData->pRightChild;list_add_tail(&pTmpNode->node,&head);}//队头出栈list_del(&pFreeNode->node);//释放为此节点申请的空间free(pFreeNode);}return 0;
}

前序遍历（非递归）

算法思想

初始化：创建一个空栈用于存储节点，同时设定一个指针（或称为当前访问节点）指向根节点。

访问当前节点：当栈不为空或当前节点不为空时，进行循环。

如果当前节点不为空，则首先访问（处理）当前节点（例如，打印其值），然后将当前节点推入栈中，并转向其左子节点（即，将当前节点设为左子节点）。
如果当前节点为空，则从栈中弹出一个节点作为新的当前节点，并转向其右子节点（即，将当前节点设为右子节点）。

结束条件：当栈为空且当前节点也为空时，表示所有节点都已遍历完毕，算法结束。

int PreOrderBinTreeByStack(BinTree *pRoot)
{struct list_head stackhead;Data_t *pTmpNode=NULL;Data_t *pFreeNode=NULL;BinTree *pTreeNode=NULL;if(pRoot==NULL){return -1;}//初始化链式栈INIT_LIST_HEAD(&stackhead);pTreeNode=pRoot;while(1){//每个左孩子节点入栈while(NULL!=pTreeNode){pTmpNode=malloc(sizeof(Data_t));if(pTmpNode==NULL){return -1;}pTmpNode->pData=pTreeNode;//入栈前打印此节点printf(" %c",pTreeNode->data);list_add(&pTmpNode->node,&stackhead);pTreeNode=pTreeNode->pLeftChild;}if(list_empty(&stackhead)){break;}//此时的栈顶节点出栈pFreeNode=list_entry(stackhead.next,Data_t,node);list_del(&pFreeNode->node);//将此节点的右子树的所有左孩子循环入栈pTreeNode=pFreeNode->pData->pRightChild;free(pFreeNode);}return 0;
}