2.二叉树链式结构的实现
①二叉树链式结构的遍历 ：
所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访 问结点所做的操作依赖于具体的应用问 题。 遍历是二叉树上最重要的运算之一，是二叉树上进行 其它运算之基础。
前序/中序/后序的递归结构遍历：是根据访问结点操作发生位置命名
前序（先根）：先访问根节点，然后访问左子树，最后访问右子树
中序（中根）：先访问左节点，然后访问根节点，最后访问右子树
后序（后根）：先访问左节点，然后访问右子树，最后访问根节点
先定一个结构体类型：
typedef char BTDataType; typedef struct BinarytreeNode { BTDataType data; struct BinarytreeNode* left; struct BinarytreeNode* right; }BTNode;
前序：
void Preamble(BTNode* p)//前序 { if (p == NULL) { printf("NULL "); return; } printf("%c ", p->data); Preamble(p->left); Preamble(p->right); }
中序：
void Morder(BTNode* p)//中序 { if (p == NULL) { printf("NULL "); return; } Morder(p->left); printf("%c ", p->data); Morder(p->right); }
后序：
void Porder(BTNode* p)//后序 { if (p == NULL) { printf("NULL "); return; } Porder(p->left); Porder(p->right); printf("%c ", p->data); }
求二叉树结点的个数：
int treeSize(BTNode* p)//结点个数 { return p == NULL ? 0 : treeSize(p->left) + treeSize(p->right)+1; }
求叶子结点的个数：
int treeLeafSize(BTNode* p)//叶子结点个数 { if (p == NULL) { return 0; } if (p->left == NULL&&p->right == NULL) { return 1; } return treeLeafSize(p->left) + treeLeafSize(p->right); }
本期的内容就到这了。。。
