【 声明：版权全部，欢迎转载，请勿用于商业用途。 联系信箱：feixiaoxing @163.com】
前面我们讲过的数据结构。每个循环节点有两个指针，一个指向前面一个节点，一个指向后继节点，这样全部的节点像一颗颗珍珠一样被一根线穿在了一起。然而今天我们讨论的数据结构却有一点不同，它有三个节点。它是这样定义的：
typedef struct _TREE_NODE{ int data; struct _TREE_NODE* parent; struct _TREE_NODE* left_child; struct _TREE_NODE* right_child;}TREE_NODE; 依据上面的数据结构，我们看到每个数据节点都有三个指针，各自是：指向父母的指针，指向左孩子的指针，指向右孩子的指针。每个节点都是通过指针相互连接的。相连指针的关系都是父子关系。那么排序二叉树又是什么意思呢？事实上非常easy，仅仅要在二叉树的基本定义上添加两个基本条件就能够了：（1）全部左子树的节点数值都小于此节点的数值；（2）全部右节点的数值都大于此节点的数值。 既然看到了节点的定义，那么我们并能够得到，仅仅要依照一定的顺序遍历，能够把二叉树中的节点依照某一个顺序打印出来。那么，节点的创建、查找、遍历是怎么进行的呢，二叉树的高度应该怎么计算呢？我们一一道来。
1）创建二叉树节点
TREE_NODE* create_tree_node(int data){ TREE_NODE* pTreeNode = NULL; pTreeNode = (TREE_NODE*)malloc(sizeof(TREE_NODE)); assert(NULL != pTreeNode); memset(pTreeNode, 0, sizeof(TREE_NODE)); pTreeNode->data = data; return pTreeNode;} 分析：我们看到，二叉树节点的创建和我们看到的链表节点、堆栈节点创建没有什么本质的差别。首先须要为节点创建内存，然后对内存进行初始化处理。最后将输入參数data输入到tree_node其中就可以。 2）数据的查找
TREE_NODE* find_data_in_tree_node(const TREE_NODE* pTreeNode, int data){ if(NULL == pTreeNode) return NULL; if(data == pTreeNode->data) return (TREE_NODE*)pTreeNode; else if(data < pTreeNode->data) return find_data_in_tree_node(pTreeNode->left_child, data); else return find_data_in_tree_node(pTreeNode->right_child, data);} 分析：我们的查找是依照递归迭代进行的。由于整个二叉树是一个排序二叉树，所以我们的数据仅仅须要和每个节点依次比較就能够了，假设数值比节点数据小，那么向左继续遍历；反之向右继续遍历。假设遍历下去遇到了NULL指针，仅仅能说明当前的数据在二叉树中还不存在。 3）数据统计
int count_node_number_in_tree(const TREE_NODE* pTreeNode){ if(NULL == pTreeNode) return 0; return 1 + count_node_number_in_tree(pTreeNode->left_child) + count_node_number_in_tree(pTreeNode->right_child);} 分析：和上面查找数据一样，统计的工作也比較简单。假设是节点指针，那么直接返回0就可以，否则就须要分别统计左节点树的节点个数、右节点树的节点个数，这样全部的节点总数加起来就能够了。 4）依照从小到大的顺序打印节点的数据
void print_all_node_data(const TREE_NODE* pTreeNode){ if(pTreeNode){ print_all_node_data(pTreeNode->left_child); printf("%d\n", pTreeNode->data); print_all_node_data(pTreeNode->right_child); }} 分析：由于二叉树本身的特殊性，按顺序打印二叉树的函数本身也比較简单。首先打印左子树的节点，然后打印本节点的数值，最后打印右子树节点的数值，这样全部节点的数值就都能够打印出来了。 5）统计树的高度
int calculate_height_of_tree(const TREE_NODE* pTreeNode){ int left, right; if(NULL == pTreeNode) return 0; left = calculate_height_of_tree(pTreeNode->left_child); right = calculate_height_of_tree(pTreeNode->right_child); return (left > right) ? (left + 1) : (right + 1);} 分析：树的高度事实上是指全部叶子节点中，从根节点到叶子节点的最大高度能够达到多少。当然，程序中表示得已经非常明确了，假设节点为空，那么非常遗憾，节点的高度为0；反之假设左子树的高度大于右子树的高度，那么整个二叉树的节点高度就是左子树的高度加上1；假设右子树的高度大于左子树的高度，那么整个二叉树的高度就是右子树的高度加上1。计算树的高度在我们设计平衡二叉树的时候非常实用，特别是測试的时候，希望大家多多理解，熟练掌握。 总结：
1）二叉树是全部树的基础，兴许的平衡二叉树、线性二叉树、红黑树、复合二叉树、b树、b+树都以此为基础，希望大家好好学习；
2）二叉树非常多的操作是和堆栈紧密联系在一起的，假设大家临时理解不了递归，能够用循环或者堆栈取代；
3）实践出真知，大家能够自己对排序二叉树的代码多多练习。不瞒大家说，我个人写平衡二叉树不下20多遍，即使这样也不能保证每次都正确；即使这样，我每次写代码的都有不同的感觉。
【预告： 以下一篇博客介绍平衡二叉树的插入和删除】
