数据结构（14）链式结构二叉树

一、链式结构二叉树的实现

用链表来表示一棵二叉树，链表中每个结点由三个域组成——数据域和左右指针域。左右指针分别用来给出该结点左孩子和右孩子所在链结点的存储地址，其结构如下：

//定义链式结构的二叉树
typedef char BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;

为了更快步入到二叉树的遍历，我们先创建一棵如图所示的链式二叉树 。

注：本章节若没有特殊说明，均采用这棵二叉树来实现相关代码~ 

BTNode* buyNode(char x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc fail");return NULL;}node->data = x;node->left = node->right = NULL;return node;
}BTNode* createBinaryTree()
{BTNode* nodeA = buyNode('A');BTNode* nodeB = buyNode('B');BTNode* nodeC = buyNode('C');BTNode* nodeD = buyNode('D');BTNode* nodeE = buyNode('E');BTNode* nodeF = buyNode('F');nodeA->left = nodeB;nodeA->right = nodeC;nodeB->left = nodeD;nodeC->left = nodeE;nodeC->right = nodeF;return nodeA;
}

二、前中后序遍历

（1）前序遍历（也叫先序遍历）：访问顺序——根结点、左子树、右子树

（2）中序遍历：访问顺序——左子树、根结点、右子树

（3）后序遍历：访问顺序——左子树、右子树、根结点

 代码实现：

//前序遍历——根左右
void preOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}printf("%c ", root->data);preOrder(root->left);preOrder(root->right);
}

//中序遍历——左根右
void inOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}inOrder(root->left);printf("%c ", root->data);inOrder(root->right);
}
//后序遍历——左右根
void postOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}postOrder(root->left);postOrder(root->right);printf("%c ", root->data);
}

三、二叉树中常用的函数接口

1、求二叉树结点的个数

我们刚才说了二叉树遍历的三种方式，那可能有人会想，定义一个变量size，每遍历一个结点，就让size++不就行了吗？这里要注意，如果我们在函数内创建一个局部变量size，初始化为0，那么每次递归都会让size的值变为0，达不到我们想要的累加的效果。那我把size定义成全局变量不就可以了吗？当我们调用一次该函数时，可以看到答案确实是我们想要的值（如下图所示）

但如果我们多调用几次这个函数，就会发现问题：

出现该问题的原因也很简单——size是全局变量。所以在每次调用函数前，我们都要把size重新置为0，但是这样做太麻烦了。既然局部变量和全局变量都不行，那么把size定义成参数行不行呢？

很明显，还是不行。那为什么每次调用之后size的值都为1呢？因为在其他结点中size的值的改变不会影响A这个结点的size的值（形参的改变不会影响实参），因此最后输出的结果永远是size++之后的值，也就是1。想要解决该问题，就需要传size的地址。但这样做就会多创建一个形参，如果不想额外创建一个形参，该怎么做呢？

我们回到最初的问题上来，结点数 = 根结点 + 左子树结点个数 + 右子树结点个数。而我们知道，根结点只有一个，因此上式又可写成结点数 = 1 + 左子树结点个数 + 右子树结点个数。而想要求左右子树的结点个数，我们又可以用上述式子，如此便构成了递归。正确参考代码如下：

//二叉树结点个数
int BinaryTreeSize(BTNode* root)
{if (root == NULL){return 0;}return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

并且无论我们调用多少次该函数，输出结果都是正确的：

递归示意图如下：

2、求二叉树叶子结点的个数 

有了上面的思路，那我们就可以参考来解决这个问题。叶子结点个数 = 根结点叶子结点个数 + 左子树叶子结点个数 + 右子树叶子结点个数。而我们知道，根结点是没有叶子结点的，因此上面式子又可以写成叶子结点个数 = 左子树叶子结点个数 + 右子树叶子结点个数，仍然构成递归。

参考代码如下：

//二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL){return 0;}if (root->left == NULL && root->right == NULL){return 1;}return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

 3、求二叉树第K层结点个数

第K层结点个数 = 左子树第K - 1层结点个数 + 右子树第K - 1层结点个数。根据这个思路，可以很轻松地写出代码：

//二叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root == NULL){return 0;}if (k == 1){return 1;}return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

4、求二叉树的深度/高度

根据思路：二叉树的高度 = 根结点 + max{左子树，右子树}，再次使用递归

//二叉树的深度/高度
int BinaryTreeDepth(BTNode* root)
{if (root == NULL){return 0;}return 1 + max(BinaryTreeDepth(root->left), BinaryTreeDepth(root->right));
}

5、查找二叉树中值为x的结点

//查找二叉树中值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode* leftFind = BinaryTreeFind(root->left, x);if (leftFind){return leftFind;}BTNode* rightFind = BinaryTreeFind(root->right, x);if (rightFind){return rightFind;}return NULL;
}

6、二叉树的销毁

在这里，我们希望形参的改变能够影响实参，因此形参部分传的要是root指针的地址，也就是要传二级指针。前面我们讲了链表的销毁是遍历一个一个的结点，那么二叉树的销毁是否和链表的销毁类似呢？答案是肯定的。那具体该如何操作呢？我们能否通过前序遍历的方式，遍历到根结点就直接将其销毁呢？要注意，这个操作是不行的。如果我们直接把根结点（也就是图中的结点A）直接释放掉了，那么我们就无法访问到左右子树了。所以，根结点一定要最后销毁！那么，唯一的遍历方式就是后序遍历了（左右根）。

//二叉树的销毁
void BinaryTreeDestroy(BTNode** proot)
{if (*proot == NULL){return;}BinaryTreeDestroy(&((*proot)->left));BinaryTreeDestroy(&((*proot)->right));free(*proot);*proot = NULL;
}

四、层序遍历 

假设二叉树的根结点所在层数为1，层序遍历就是从二叉树所在的根结点出发，首先访问第一层的根结点，然后从左到右访问第2层上的结点，以此类推。从上而下，从左至右逐层访问树的结点的过程就是层序遍历。在本章节的二叉树中，层序遍历的结果就是A B C D E F。

实现层序遍历。我们需要借助数据结构——队列。我们先将根结点入队列，如果队列不为空，取出队头元素，判断其左右孩子是否为空，不为空，就入队列，如此循环往复，直至链表为空。

//层序遍历
void LevelOrder(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){//取队头，出队头BTNode* top = QueueFront(&q);QueuePop(&q);printf("%c ", top->data);//将队头非空的左右孩子入队列if (top->left)QueuePush(&q, top->left);if (top->right)QueuePush(&q, top->right);}QueueDestroy(&q);
}

五、判断二叉树是否为完全二叉树

前一章讲了，完全二叉树具有如下两个特点：（1）最后一层的结点个数不一定达到最大（2）结点从左到右依次排列。和层序遍历的思想类似，我们仍然需要借助数据结构队列来解决问题。

根据上面两张图，我们可以得出结论：如果在第二个循环中，从非空的队列中取到了非空的队头结点，那么这棵二叉树一定不是完全二叉树，否则一定是完全二叉树。

参考代码如下： 

//判断二叉树是否为完全二叉树
//借助数据结构——队列
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){//取队头结点，出队头BTNode* top = QueueFront(&q);QueuePop(&q);if (top == NULL){break;}QueuePush(&q, top->left);QueuePush(&q, top->right);}//队列不一定为空while (!QueueEmpty(&q)){//取队头结点，出队头BTNode* top = QueueFront(&q);QueuePop(&q);if (top){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}