😽PREFACE
🎁欢迎各位→点赞👍 + 收藏⭐ + 评论📝
📢系列专栏：数据结构
🔊本专栏主要更新的是数据结构部分知识点
💪种一棵树最好是十年前其次是现在

目录

1.二叉树的顺序结构

2.二叉树的链式结构

3.创建结构和树

4.二叉树的遍历

4.1 前序遍历

4.2 中序遍历

4.3 后序遍历

4.4 层序遍历

5.二叉树常见玩法

5.1 节点个数

5.2 第k层叶节点个数

5.3 树的高度

5.4 查找值为x的节点

1.二叉树的顺序结构

2.二叉树的链式结构

大体来说，二叉树的链式结构可分为而二叉链与三叉链。

//二叉链
typedef struct BinaryTreeNode
{BTDataType data;//当前节点的值域struct BinaryTreeNode* left;//指向当前节点左孩子struct BinaryTreeNode* right;//指向当前节点右孩子
}BTNode;//三叉链
typedef struct BinaryTreeNode
{BTDataType data;//当前节点的值域struct BinaryTreeNode* left;//指向当前节点左孩子struct BinaryTreeNode* right;//指向当前节点右孩子struct BinaryTreeNode* parent;//指向当前节点的双亲
}BTNode;

但通常情况下，我们使用的都是二叉链的结构。我们不妨回顾一下之前学过的数据结构，什么顺序表啊，链表啊，栈和队列等等，在初学这些结构的同时，我们都会关注其增删查改，但这些对于二叉树而言是没有什么意义的，我们在这里也不展开讨论。

3.创建结构和树

有了上面的铺垫，创建一个二叉链结构就会容易很多，代码如下：
 

//创建二叉链结构
typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;//当前节点的值域struct BinaryTreeNode* left;//指向当前节点左孩子struct BinaryTreeNode* right;//指向当前节点右孩子
}BTNode;

有了结构，接下来就可以构造树了。光有结构还不行，我们还需要创建出节点，代码如下：
 

//创建二叉链结构
typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;//当前节点的值域struct BinaryTreeNode* left;//指向当前节点左孩子struct BinaryTreeNode* right;//指向当前节点右孩子
}BTNode;//创建节点
BTNode* BuyNode(BTDataType x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc fail");return NULL;}node->data = x;node->left = NULL;node->right = NULL;return node;
}//构造树
BTNode* CreatTree()
{//创建7个节点BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);BTNode* node5 = BuyNode(5);BTNode* node6 = BuyNode(6);BTNode* node7 = BuyNode(7);//手动连接各节点之间的关系(根据具体树来定)node1->left = node2;node1->right = node4;node2->left = node3;node4->right = node6;node3->right = node7;//返回根节点return node1;
}int main()
{BTNode* root = CreatTree();return 0;
}

4.二叉树的遍历

以这颗二叉树为例：

 首先遍历分为四种：分别是前序遍历，中序遍历，后序遍历，层次遍历

4.1 前序遍历

1.前序遍历(Preorder Traversal），亦称先序遍历

2.遍历顺序：根->左->右

3.图示结构：

 4.代码演示：

void PreOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}printf("%d ", root->data);PreOrder(root->left);PreOrder(root->right);
}

4.2 中序遍历

1.中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。

2.遍历顺序：左->根->右

3.图示结构：

 

4.代码演示：

void InOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
}

4.3 后序遍历

1.后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

2.遍历顺序：左->右->根

3.图示结构：

4.代码演示：

void PostOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);
}

4.4 层序遍历

1.层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

2.遍历顺序：一层一层的遍历打印

3.图示结构：

4.代码展示：

void LevelOrder(BTNode* root)
{Queue q;QueueInit(&q);if (root){QueuePush(&q, root);//根节点先入队列}while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);//取队头QueuePop(&q);//出队头printf("%d ", front->data);//打印队头数据if (front->left){QueuePush(&q, front->left);}if (front->right){QueuePush(&q, front->right);}}printf("\\n");QueueDestory(&q);
}

5.二叉树常见玩法

5.1 节点个数

• 代码演示：

int TreeSize(BTNode* root)
{return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}

5.2 第k层叶节点个数

• 思路：如果一开始根节点为空，那么直接返回0，如果左右子树均为0，则该节点为叶节点，此时返回1 即可，如果不是这两种情况，那么就一直递归下去。
• 代码演示：

int TreeKLevel(BTNode* root, int k)
{if (root == NULL)return 0;if (k == 1)return 1;int leftk = TreeKLevel(root->left, k - 1);int rightk = TreeKLevel(root->right, k - 1);return leftk + rightk;
}

5.3 树的高度

• 思路：如果root节点为空，直接返回0，如果root==1，则返回1，如果不是这两种情况，就依次递归，分别定义左右高度变量来保存，最后还要比较一下，大的高度还要加一得到最终答案。
• 代码演示：

  int TreeHeight(BTNode* root)
  {if (root == NULL){return 0;}int leftHeight = TreeHeight(root->left);int rightHeight = TreeHeight(root->right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}

5.4 查找值为x的节点

• 思路：先去找根，看看根节点是否等于x，等于直接返回根，不等于先去左子树里面找，再去右子树里面找，如果左右子树都找不到则返回NULL
• 代码演示：

  BTNode* TreeFind(BTNode* root, BTDataType x)
  {if (root == NULL){return NULL;}if (root->data == x){return root;}//去左子树找BTNode* ret1 = TreeFind(root->left, x);if (ret1){return ret1;}//去右子树找BTNode* ret2 = TreeFind(root->right, x);if (ret2){return ret2;}//都没找到返回NULLreturn NULL;
  }