初识二叉树（ 二）

实现链式结构二叉树

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

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

前中后序遍历

前中后序遍历，均用到函数的递归，因此代码量虽小，却能够帮助我们充分理解递归的思想。

遍历规则

按照规则，⼆叉树的遍历有：前序/中序/后序的递归结构遍历：
1）前序遍历(Preorder Traversal 亦称先序遍历)：访问根结点的操作发⽣在遍历其左右子树之前
访问顺序为：根结点、左子树、右子树
2）中序遍历(Inorder Traversal)：访问根结点的操作发⽣在遍历其左右子树之中（间）
访问顺序为：左子树、根结点、右子树
3）后序遍历(Postorder Traversal)：访问根结点的操作发⽣在遍历其左右子树之后
访问顺序为：左⼦树、右⼦树、根结点

代码实现

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

结点个数以及高度等

// ⼆叉树结点个数 
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 BinaryTreeDestory(BTNode** root);

层序遍历

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

// 层序遍历
void LevelOrder(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* top = QueueFront(&q);printf("%c ", top->data);QueuePop(&q);if (top->_left) {QueuePush(&q, top->_left);}if (top->_right) {QueuePush(&q, top->_right);}}QueueDesTroy(&q);
}

判断是否为完全二叉树

// 判断⼆叉树是否是完全⼆叉树
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 != NULL) {QueueDesTroy(&q);return false;}}QueueDesTroy(&q);return true;
}
```利用了队列的方法，将二叉树进行遍历，一旦在NULL后找到非空元素，说明该二叉树非完全二叉树，若全不为空，或剩下的全为空时，说明为完全二叉树，但有一点需要判断该队列是否为空。