二叉树的链式结构
链式二叉树的增删查改是没有意义的，建立在二叉树基础上的搜索二叉树才具备增删查改的意义。但是链式二叉树是基础，就像修房子得先打地基一样。
二叉树的遍历
首先确定一个概念，二叉树分为空树和非空树，只要是非空树就有根节点、根节点的左子树和根节点的右子树。二叉树的定义是递归式的。
二叉树遍历是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作依次。访问节点所做的操作依赖于具体的应用问题，遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。
二叉树一共有四种遍历方式，前序遍历（先根遍历）、中序遍历（中根遍历）、后序遍历（后根遍历）和层序遍历。
前序遍历（先根遍历）
访问根节点的操作发生在遍历其左右子树之前。在遍历时，会不断向下遍历知道遇到空树才停止。
void PrevOrder(BTNode* root) { if (NULL == root) { printf("NULL "); return; } printf("%d ", root->data); PrevOrder(root->left); PrevOrder(root->right); }
栈帧空间的创建销毁顺序按照下图进行的，向右的箭头表示创建，向左的箭头表示销毁。创建销毁的顺序是橙色->绿色->深蓝色->粉色->金色->紫色->青色。
中序遍历（中根遍历）
访问根节点的操作放生在遍历其左右子树之间。
void InOrder(BTNode* root) { if (NULL == root) { printf("NULL "); return; } InOrder(root->left); printf("%d ", root->data); InOrder(root->right); }
栈帧空间的创建销毁顺序按照下图进行的，向右的箭头表示创建，向左的箭头表示销毁。创建销毁的顺序是橙色->绿色->蓝色->粉色->深蓝色->金色->青色->紫色。
后序遍历（后根遍历）
访问根节点的操作发生在遍历其左右子树之后。
void PostOrder(BTNode* root) { if (NULL == root) { printf("NULL "); return; } PostOrder(root->left); PostOrder(root->right); printf("%d ", root->data); }
栈帧空间的创建销毁顺序按照下图进行的，向右的箭头表示创建，向左的箭头表示销毁。创建销毁的顺序是橙色->绿色->蓝色->粉色->深蓝色->金色->青色->紫色。
层序遍历
从第一层开始，每层从左到右，一层一层的走。四种遍历中，只有层序遍历是非递归的，它采用的是队列来实现的。
void LevelOrder(BTNode* root) { Queue q; QueueInit(&q); // 先将根节点存入队列 if (root) QueuePush(&q, root); // 判空，如果为空就不执行以下语句 while (!QueueEmpty(&q)) { // 获取队头，打印之后，移出队列 BTNode* front = QueueFront(&q); printf("%d ", front->data); QueuePop(&q); if (front->left) QueuePush(&q, front->left); if (front->right) QueuePush(&q, front->right); } printf("\n"); QueueDestroy(&q); }
二叉树的构建
二叉树的构建根据三种递归的遍历方式进行构建，可以进行前序、中序、后序构建，我这里使用的是前序构建。
BTNode* CreatBinaryTree(BTDataType* a, int* pi) { if (-1 == a[*pi]) { (*pi)++; return NULL; } BTNode* root = (BTNode*)malloc(sizeof(BTNode)); if (NULL == root) { perror("malloc fail"); exit(-1); } root->data = a[(*pi)++]; root->left = CreatBinaryTree(a, pi); root->right = CreatBinaryTree(a, pi); return root; }
二叉树的节点数
int TreeSize(BTNode* root) { if (NULL == root) { return 0; } return TreeSize(root->left) + TreeSize(root->right) + 1; }
栈帧空间的创建销毁顺序按照下图进行的，向右的箭头表示创建，向左的箭头表示销毁。创建销毁的顺序是橙色->绿色->蓝色->粉色->深蓝色->金色->青色->紫色，最后返回的值是6。
二叉树的叶子数
int TreeLeafSize(BTNode* root) { if (NULL == root) { return 0; } if (NULL == root->left && NULL == root->right) { return 1; } return TreeLeafSize(root->left) + TreeLeafSize(root->right); }
栈帧空间的创建销毁顺序按照下图进行的，向右的箭头表示创建，向左的箭头表示销毁。创建销毁的顺序是橙色->绿色->蓝色->粉色->深蓝色->金色，最后结果为3。
二叉树的高度
int TreeHeight(BTNode* root) { if (NULL == root) { return 0; } int left = TreeHeight(root->left); int right = TreeHeight(root->right); return (left > right ? left : right) + 1; }
栈帧空间的创建销毁顺序按照下图进行的，向右的箭头表示创建，向左的箭头表示销毁。创建销毁的顺序是橙色->绿色->蓝色->粉色->深蓝色->金色，最后结果为3。
二叉树K层节点数
int TreeKLevelSize(BTNode* root, int k) { if (NULL == root) { return 0; } if (1 == k) { return 1; } return TreeKLevelSize(root->left, k - 1) + TreeKLevelSize(root->right, k - 1); }
栈帧空间的创建销毁顺序按照下图进行的，向右的箭头表示创建，向左的箭头表示销毁。创建销毁的顺序是橙色->绿色->蓝色->粉色->深蓝色->金色，最后结果为3。
查找值为X的节点
BTNode* TreeFind(BTNode* root, BTDataType x) { if (NULL == root) return NULL; if (x == root->data) return root; BTNode* ret1 = TreeFind(root->left, x); if (ret1) return ret1; BTNode* ret2 = TreeFind(root->right, x); if (ret2) return ret2; return NULL; }
栈帧空间的创建销毁顺序按照下图进行的，向右的箭头表示创建，向左的箭头表示销毁。创建销毁的顺序是橙色->绿色->蓝色->粉色->深蓝色->金色，最后结果为数字5节点的地址
判断二叉树是否为完全二叉树
bool TreeComplete(BTNode* root) { Queue q; QueueInit(&q); if (root) QueuePush(&q, root); // 若队列为空，则不执行 while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); QueuePop(&q); // 判断front是否为空，为空则跳出循环 if (!front) { break; } else { QueuePush(&q, front->left); QueuePush(&q, front->right); } } // 若队列为空，则不执行 while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); QueuePop(&q); if (front) { QueueDestroy(&q); return false; } } QueueDestroy(&q); return true; }
二叉树的销毁
// 二叉树销毁 void TreeDestory(BTNode* root) { if (NULL == root) { return; } TreeDestory(root->left); TreeDestory(root->right); free(root); }
