实现链式结构二叉树

需要实现的操作

链式结构二叉树实现

结点的创建

前序遍历

中序遍历

后序遍历

计算结点个数

计算二叉树的叶子结点个数

计算二叉树第k层结点个数

计算二叉树的深度

查找值为x的结点

销毁

层序遍历

判断是否为完全二叉树

总结

需要实现的操作

//前序遍历
void PreOrder(BTNode* root);//中序遍历
void InOrder(BTNode* root);//后序遍历
void PostOrder(BTNode* root);//计算结点个数
int BinaryTreeSize(BTNode* root);//二叉树的叶子结点个数
int BinaryTreeLeafSize(BTNode* root);//二叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k);//二叉树的深度
int BinaryTreeDepth(BTNode* root);//二叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDatatype x);//销毁
void BinaryTreeDestroy(BTNode** root);//层序遍历
void LevelOrder(BTNode* root);//判断是否为完全二叉树
bool BinaryTreeComplete(BTNode* root);

链式结构二叉树实现

结点的创建

⽤链表来表⽰⼀棵⼆叉树，即⽤链来指⽰元素的逻辑关系。通常的⽅法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别⽤来给出该结点左孩⼦和右孩⼦所在的链结点的存储地址，其结构如下：

typedef int BTDataType;
// ⼆叉链
typedef struct BinaryTreeNode
{
struct BinTreeNode* left; // 指向当前结点左孩⼦
struct BinTreeNode* right; // 指向当前结点右孩⼦
BTDataType val; // 当前结点值域
}BTNode;

⼆叉树的创建⽅式⽐较复杂，为了更好的步⼊到⼆叉树内容中，我们先⼿动创建⼀棵链式⼆叉树

BTNode* BuyNode(int val)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = val;newnode->left = newnode->right = NULL;return newnode;
}
void CreatTree()
{BTNode* n1 = BuyNode(1);BTNode* n2 = BuyNode(2);BTNode* n3 = BuyNode(3);BTNode* n4 = BuyNode(4);n1->left = n2;n1->right = n3;n2->left = n4;
}
int main()
{CreatTree();return 0;
}

前序遍历

前序遍历：访问根结点的操作发⽣在遍历其左右⼦树之前

访问顺序为：根结点、左⼦树、右⼦树

以该图为例，前序遍历从我们创建链式二叉树的根节点1开始，按照“根左右”的顺序，先遍历自己，在遍历左子树2，同时以2为中心，遍历2的左子树，当遍历完4时，同样以4为中心遍历4的左子树，但是4的左子树为NULL，只能返回，再以4为中心遍历4的右子树，同样为NULL返回。2的左子树遍历完后遍历2的右子树，为NULL返回。这样1的左子树遍历完了，再用同样方法遍历1的右子树。

从以上实现步骤来看，前序遍历在遍历时一环套一环，当遇到NULL时，需要返回。可以利用递归的方式实现前序遍历。

//前序遍历
void PreOrder(BTNode* root)
{if (root == NULL)//遇到NULL时返回{return;}//按照根左右顺序遍历printf("%d ", root->data);PreOrder(root->left);//一环套一环先遍历左子树PreOrder(root->right);
}

中序遍历

中序遍历：访问根结点的操作发⽣在遍历其左右⼦树之中

访问顺序为：左⼦树、根结点、右⼦树

以该图为例，中序遍历从我们创建链式二叉树的根节点1开始，按照“左根右”的顺序，先以1为中心往左子树找，直到找到NULL返回，遍历4，再遍历右子树，为NULL返回。2的左子树遍历完，遍历2，之后遍历右子树，为NULL返回。这样1的左子树遍历完，再遍历1，最后以同样方式遍历右子树。

从以上实现步骤来看，中序遍历在遍历时一环套一环，当遇到NULL时，需要返回。可以利用递归的方式实现中序遍历。

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

后序遍历

后序遍历：访问根结点的操作发⽣在遍历其左右⼦树之后

访问顺序为：左⼦树、右⼦树、根结点

以该图为例，后序遍历从我们创建链式二叉树的根节点1开始，按照“左右根”的顺序，先以1为中心往左子树找，直到找到NULL返回，再以4为中心遍历右子树，为NULL返回，最后遍历4。2的左子树遍历完，遍历右子树，为NULL返回，最后遍历2。这样1的左子树遍历完，再遍历1的右子树，最后遍历1。

从以上实现步骤来看，后序遍历在遍历时一环套一环，当遇到NULL时，需要返回。可以利用递归的方式实现后序遍历。

计算结点个数

计算链式二叉树的结点个数，我们可以利用递归的方式找到每一个结点，遇到NULL返回0，先找左子树上的结点，再找右子树上的结点。可以得出以下代码：

int size = 0;
int BinaryTreeSize(BTNode* root, int size)
{if(root == NULL){return 0;//遇到非结点返回0}++size;//遍历完一个结点记一次BinaryTreeSize(root->left, size);//遍历左子树结点BinaryTreeSize(root->right, size);//遍历右子树结点return size;
}

但是这样写得出的结果却是错误的，因为在传递参数时，传的是值，当函数栈帧遍历到4时，++size总共进行了3次，size为3，但是返回后栈帧自动回收，当进行遍历右结点的操作时，全局变量size的值为1，没有得到保存。

那么是否可以通过传递地址的方式来永久改变size的值呢？

void BinaryTreeSize(BTNode* root, int* size)//传地址
{if(root == NULL){return 0;}++(*size);BinaryTreeSize(root->left, size);BinaryTreeSize(root->right, size);
}

这样写成功将size的值进行了正确的计算，结果在栈帧销毁时得到了保存。但是如果在实际运用中需要两次及以上计算结点的个数，size的值一直得到保存后，必然发生错误。

如何做到size的值既能在一次计算中得到保存，还能不会影响之后计算结点的个数？

我们可以将递归的发生保存在返回值中，遇到NULL时返回0，如果左右子树都为0，则只返回1来表示自身的结点个数。

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

计算二叉树的叶子结点个数

叶子结点：度为 0 的结点称为叶结点

计算二叉树叶子结点的个数，可以根据结点是否有左右子树来判断，当结点同时不存在左右子树时，该结点就是叶子结点。

联系上文，利用递归方法对二叉树进行遍历。

//二叉树的叶子结点个数
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);
}

计算二叉树第k层结点个数

若规定根结点的层数为 i ，则⼀棵⾮空⼆叉树的第i层上最多有 2^（i-1）个结点

第k层结点个数 = 第k层左子树结点 + 第k层右子树结点

以该图为例，若想要计算第三层的结点个数，则需要将k调整为1，当k值为1时，返回1个结点。

同理，利用递归的方法遍历左右子树，同时利用 k-1 的方式不断向下调整，当遇到 k == 1 时，返回1，遇到NULL时返回0。

//二叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root == NULL)//为空返回0{return 0;}if (k == 1)//第k层的结点{return 1;}return BinaryTreeLevelKSize(root->left, k - 1) +BinaryTreeLevelKSize(root->right, k - 1);//k-1向下寻找第k层结点
}

计算二叉树的深度

计算二叉树的深度时，需要比较左右子树两边的深度值，找到较大一方的深度进行返回来代表二叉树的整体深度。

利用递归向下调整计算深度

根据分析绘制图例：

当递归过程中遭遇NULL时，返回0。遇到结点时向上返回1。最后比较左右子树计算而来的深度，取大值2，+1得出最后的深度为3。

由此我们可以设置两个变量 leftdep 和 rightdep ，leftdep计算左子树深度，rightdep计算右子树深度。递归的结束条件为 root == NULL 时返回0。

像这样不断向下递归，以1为中心左右子树向下递归，而后再以左右子树为中心递归自身的左右子树，返回值取每一个左右子树的较大值+1进行返回。

//二叉树的深度
int BinaryTreeDepth(BTNode* root)
{if (root == NULL)//递归结束条件{return 0;}int leftdep = BinaryTreeDepth(root->left);//左子树深度int rightdep = BinaryTreeDepth(root->right);//右子树深度return leftdep > rightdep ? leftdep + 1 : rightdep + 1;
}

查找值为x的结点

依据前文，查找结点需要不断向下查找，所以依然可以利用递归的方式查找结点。

当向下递归查找找到x时，返回当前结点。当没有查找到x时，返回NULL。

可以先查找左子树，再查找右子树。当左子树先一步查找到值为x的结点时，可以提前返回结点。

进一步查找右子树，查找到时返回值为x的结点。

//二叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDatatype x)
{if (root == NULL)//左子树没有找到，右子树没有找到，二叉树没找到{return NULL;}if (root->data == x)//查找到值为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;//没有查找到值为x的结点
}

销毁

销毁二叉树需要先销毁左子树，再销毁右子树，最后销毁根结点。

同样利用递归的方式找结点，先找左子树，后找右子树。递归结束条件为结点为NULL，这样就可以从每一个子树的尾部向上销毁每一个结点。

因为需要对二叉树进行改变，所以传参时需要传递地址。

//销毁
void BinaryTreeDestroy(BTNode** root)//传一级指针的地址，也就是二级指针
{if (*root == NULL)//找到每一个子树最后的结点{return;}BinaryTreeDestroy(&((*root)->left));BinaryTreeDestroy(&((*root)->right));free(*root);//销毁*root = NULL;
}

层序遍历

除了先序遍历、中序遍历、后序遍历外，还可以对⼆叉树进⾏层序遍历。设⼆叉树的根结点所在层数为1，层序遍历就是从所在⼆叉树的根结点出发，⾸先访问第⼀层的树根结点，然后从左到右访问第2 层上的结点，接着是第三层的结点，以此类推，⾃上⽽下，⾃左⾄右逐层访问树的结点的过程就是层序遍历。

实现层序遍历需要额外借助数据结构：队列

根据先前创建的结点进行层序遍历，得出以下图示：

考虑递归的方式分别从左右子树进行遍历，无法达到层序遍历的效果。所以需要利用队列“先进先出”的特点来实现。

为了实现层序遍历，我们可以利用队列，插入根节点，再取出队列，判断该结点是否有左孩子和右孩子，如果有则插入。直到队列为空结束循环。

队列的实现：

typedef struct BinaryTreeNode* QDatatype;typedef struct QueueNode
{QDatatype data;struct QueueNode* next;
}QueueNode;
typedef struct Queue
{QueueNode* phead;QueueNode* ptail;int size;
}Queue;//初始化
void QueueInit(Queue* pq);//销毁队列
void QueueDestroy(Queue* pq);//入队列
void QueuePush(Queue* pq, QDatatype x);//出队列
void QueueBack(Queue* pq);//判空
bool QueueEmpty(Queue* pq);

层序遍历：

//层序遍历
void LevelOrder(BTNode* root)
{Queue q;//创建队列QueueInit(&q);//初始化QueuePush(&q, root);//插入根节点while (!QueueEmpty(&q))//当队列不为空时循环{//打印队头数据，出队列BTNode* front = QueueTou(&q);QueueBack(&q);printf("%d ", front->data);//判断这个数据是否有左右子树，插入if (front->left)QueuePush(&q, front->left);if (front->right)QueuePush(&q, front->right);}//销毁队列QueueDestroy(&q);
}

判断是否为完全二叉树

完全二叉树：一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。

判断是否为完全二叉树时，我们可以利用层序遍历的原理，利用队列“先进先出”的特点来实现。

往队列中插入根节点，再取出队列，判断该结点是否有左孩子和右孩子，如果有则插入，如果没有则将NULL也插入到队列中，当出队列时，出队列的数据为NULL，提前跳出循环。

存在两种情况，当出队列的数据为NULL时，跳出循环后：

队列中仍存在有效数据，则这个二叉树不是完全二叉树。

队列中只剩NULL时，这个二叉树是完全二叉树。

//判断是否为完全二叉树
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){//插入数据，直到插入的数据为空BTNode* front = QueueTou(&q);QueueBack(&q);if (front == NULL)//出队列的数据为NULL时提前结束循环{break;}QueuePush(&q, front->left);QueuePush(&q, front->right);}//队列要么只剩下NULL，要么还有非空结点while (!QueueEmpty(&q)){BTNode* front = QueueTou(&q);QueueBack(&q);if (front != NULL)//队列中还有非空结点{QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}