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

Linux 数据结构树知识

news 来源：原创 2024/9/21 1:30:53

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

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

节点的度：叶子节点度数为0
节点的后继的个数
多个树构成森林

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

左孩子
右孩子

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

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

//二叉树节点类型 
typedef struct node 
{int No;char Data;struct node *pLeftChild;struct node *pRightChild;
}TreeNode;//队列数据
typedef struct data
{struct list_head node;TreeNode *pData;
}Data_t;
//创建完全二叉树
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;
}

二叉树的三种遍历方法：
1.前序遍历：根左右

利用队列和递归，实现遍历

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

2.中序遍历：左根右

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

3.后续遍历：左右根

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