二叉树链式结构：数据结构中的灵动之舞

前言

一、前置说明

二、二叉树的遍历

2.1前序遍历

2.2中序遍历

2.3 后序遍历

2.4层序遍历

三、二叉树的遍历的应用

3.1二叉树节点个数：

3.2二叉树的高度

3.3 二叉树第k层的节点的个数

3.4二叉树的查找

总结

前言

在数据结构的世界里，二叉树是一种极其重要的结构，它以其独特的性质和广泛的应用场景而备受关注。二叉树的存储结构主要有两种：顺序存储和链式存储。今天，我们将深入探讨二叉树的链式存储结构，从其基本概念、实现方式到实际，应用帮助大家全面理解这一强大的数据结构。

一、前置说明

在学习二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作。由于现在对二叉树结构还不够深入，为了降低学习成本，此处手动快速创建一棵简单的二叉树，快速进入二叉树操作学习，等二叉树结构了解的差不多时，我们反过头再来研究二叉树真正的创建方式。

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");exit(1);}node->data = x;node->left = NULL;node->right = NULL;return node;
}
BTNode* CreatTree()
{BTNode* node1 = Buynode(1);BTNode* node2 = Buynode(2);BTNode* node3 = Buynode(3);BTNode* node4 = Buynode(4);BTNode* node5 = Buynode(5);BTNode* node6 = Buynode(6);node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;return node1;
}

在看二叉树基本操作前，首先要对二叉树的基本结构要清楚

空树
非空：根节点，根节点的左子树、根节点的右子树组成的。

可以看出，二叉树的定义是递归式的，所以后续基本操作中基本都是按递归实现的，当然也是以二叉树的基本结构：根，左子树，右子树为基本展开的

二、二叉树的遍历

学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。

二叉树的遍历有：前序/中序/后序的递归结构遍历：

2.1前序遍历

前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。先访问根节点，再访问左子树，最后访问右子树

前序遍历（根-左-右）

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

递归演示图:

void PreOrder(BTNode* root)//前序遍历
{if (root){printf("%d ", root->data);PreOrder(root->left);PreOrder(root->right);}
}

递归演示图:

2.2中序遍历

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

中序遍历（左-根-右）

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

2.3 后序遍历

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

后序遍历（左-右-根）

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

测试一下：

2.4层序遍历

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

要用到队列的结构，A节点进对列出队列的时候，把a节点的左右子数节点进队列，a节点的左子数节点就是b，然后b再出队列的时候，又把b的左右子数节点路队列，然后c节点出队列，再又把c节点的左右子数节点路队列，以此类推

void LevelOrder(BTNode* root)//层序遍历
{Queue q;Init(&q);if(root)Push(&q, root);while (!Empty(&q)){BTNode*front = QueueFront(&q);Pop(&q);printf("%d ",front->data);if (front->left){Push(&q, front->left);}if (front->right){Push(&q, front->right);}}Destroy(&q);
}

需注意的是，存入队列的是指向节点的指针，因此，需改变一下队列存储的数据类型：

typedef struct BinaryTreeNode* c;
typedef struct QueueNode
{struct QueueNode* next;c data;
}QNode;

测试一下：

三、二叉树的遍历的应用

3.1二叉树节点个数：

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

当然还有其他的方法如：

定义一个全局变量size，然后用递归遍历树，每次能成功递归一次，就加一

int size = 0;
void TreeSize(BTNode* root)
{if (root == NULL)return;size++;TreeSize(root->left);TreeSize(root->right);}
int main()
{BTNode* root = CreatTree();PreOrder(root);printf("\n");InOrder(root);printf("\n");PostOrder(root);printf("\n");TreeSize(root);printf("TreeSize=%d ",size);TreeSize(root);printf("\n");printf("TreeSize=%d ", size);return 0;
}

但是最好不要用全局变量，而且每次统计数量时，还要初始化一次，要不然就会

int size = 0;
void TreeSize(BTNode* root)
{if (root == NULL)return;size++;TreeSize(root->left);TreeSize(root->right);}
int main()
{BTNode* root = CreatTree();PreOrder(root);printf("\n");InOrder(root);printf("\n");PostOrder(root);printf("\n");TreeSize(root);printf("TreeSize=%d ",size);TreeSize(root);printf("\n");printf("TreeSize=%d ", size);return 0;
}

如果是改为局部的静态，甚至都没法初始化它，局部的静态只会在第一次调用它的时候初始化，

void TreeSize(BTNode* root)
{static int size = 0;if (root == NULL)return;size++;TreeSize(root->left);TreeSize(root->right);}

最好的方式就是在TreeSize函数中增添一个变量psize，统计它的个数，想要形参影响实参，就要传指针，就要传地址：

void TreeSize(BTNode* root,int *psize)
{static int size = 0;if (root == NULL)return;(*psize)++;TreeSize(root->left,psize);TreeSize(root->right,psize);
}
int main()
{BTNode* root = CreatTree();PreOrder(root);printf("\n");InOrder(root);printf("\n");PostOrder(root);printf("\n");int size1 = 0;TreeSize(root,&size1);printf("TreeSize=%d ",size1);int size2 = 0;TreeSize(root,&size2);printf("\n");printf("TreeSize=%d ", size2);return 0;
}

测试一下：

3.2二叉树的高度

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

用参数保留它递归的结果，这样就不用return的时候再递归

3.3 二叉树第k层的节点的个数

int TreeKevel(BTNode* root, int x)
{assert(x > 0);if (root == NULL)return 0;if (x == 1)return x;/* int leftK = TreeKevel(root->left, x - 1);int rightK = TreeKevel(root->right, x - 1); return leftK+rightK+1   or*/return TreeKevel(root->left, x - 1) + TreeKevel(root->right, x - 1);
}

3.4二叉树的查找

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL || root->data == x)return root;BTNode* Findleft = BinaryTreeFind(root->left, x);if (Findleft)return Findleft;BTNode* Findright = BinaryTreeFind(root->right, x);if (Findright)return Findright;return NULL;
}

我一开始在写的时候只写出了这样的代码，后来我画图演示递归的过程,才发现的错误,所以说要多画图

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL || root->data == x)return root;BTNode* Findleft = BinaryTreeFind(root->left, x);if (Findleft)return Findleft;BTNode* Findright = BinaryTreeFind(root->right, x);if (Findright)return Findright;
}

查找递归演示图: