1.二叉树的非线性数据结构，通过遍历可以将二叉树中的结点访问一次仅一次，从而得到访问结点的顺序序列。

按先左后右的顺序有三种排序

DLR:先序遍历

遍历根结点

按先序遍历左子树

按先序遍历右子树

LDR：中序遍历

先中序排列左子树

访问根结点

按中序排列右子树。

LRD  :后序遍历。

树的相关术语：

结点的度：一个结点的子树个数称为结点的度。

树的度：树中所有结点的层次的最大值。

树的高度：树中所有结点的层次最大值。

二叉树的性质

1.二叉树的第i层至多有2的i次幂-1.

2.深度为k的二叉树至多有2的k次幂-1个结点。

3。度数为0的结点=度数为2的结点+1

4.满二叉树的定义和完全二叉树的定义。

 

 遍历算法的应用：主要是递归算法

1.输出二叉树的结点：

void PreOrder(Bitree root){ if(root!=null){ printf(root->data)； PreOrder(root->LChild); PreOrder(root->RChild); } }

2.输出二叉树的叶子结点

void PreOrder(Bitree root){ if(root!=null){ if(root->LChild==null && root->RChild==null) printf(root->data)； PreOrder(root->LChild); PreOrder(root->RChild); } }

3.统计叶子结点

void PreOrder(Bitree root){ if(root!=null){ PreOrder(root->LChild); PreOrder(root->RChild); if(root->LChild==null && root->RChild==null) count++; } }