树是一种非常重要的数据结构，而二叉树是树的最基本的形式。像其他高级的数据结构，如 二叉查找树、平衡二叉树、AVL树、红黑树、splay 树（伸展树）、笛卡尔树、Treap、SBT树等都是以二叉树作为基础。

性质

1. 树中每个节点都有0-2个子节点，每个子节点又成为一棵子树的根
2. 树中边的数目是节点的数目 - 1， 即 e = n - 1
3. 树中度数为0，1，2的节点个数分别为n0, n1, n2， 则有 n0 + n1 + n2 = n, n1 + 2*n2 = e. 则可以推出 n0 - n2 = 1，即度数为0的点的个数比度数为2的点的个数多1.
4. 第n层（设根为第0层，依次向下为第1、2、3 ...层）中点的数目最多为 2n
5. n 个节点的二叉树的层数最少为 ⌊log2n⌋ + 1

特殊的二叉树

• 1 完全二叉树 
      若二叉树的层数为h，且从第0层到第h-2层的节点均满（依次为 20 、21... 2^(h−2)），第h-1层的节点数目>0, 而且第h-1层的节点均排在靠左的位置（如果将二叉树最后一层可以放置节点的位置从左到右编号为1， 2... 2^(h−1)，最后一层有k个节点，则这k个节点的位置为 1, 2,3...k)。这样的二叉树称为完全二叉树. 
   
• 2满二叉树 
      若二叉树为h层，且从第0层到第h-1层的节点均满（依次为 20 、21... 2^(h−1)），即总节点数目为 2^h−1.这种二叉树称为满二叉树，可见满二叉树为完全二叉树的特例。

二叉树的实现（c++）

#include
     
      #include
      
       using namespace std;struct TreeNode{    int data;    TreeNode* left;    TreeNode* right;    TreeNode* parent;    TreeNode(int d) :        data(d), left(NULL), right(NULL), parent(NULL){};};void Visit(TreeNode* node){    cout << "visit node, data = " << node->data << endl;}//树的前序遍历，非递归void PreOrderTravel_Stack(TreeNode* root){    TreeNode* node = root;    stack
       
         node_stack;    while (!node_stack.empty() || node){        if (node){            Visit(node);            node_stack.push(node);            node = node->left;        }        else{            node = node_stack.top();            node_stack.pop();            node = node->right;        }    }}//树的中序遍历，非递归void InOrderTravel_Stack(TreeNode* root){    TreeNode* node = root;    stack
        
          node_stack;    while (!node_stack.empty() || node){        if (node){            node_stack.push(node);            node = node->left;        }        else{            node = node_stack.top();            node_stack.pop();            Visit(node);            node = node->right;        }    }}//树的后序遍历，非递归void PostOrderTravel_Stack(TreeNode* root){    stack
         
          
            > node_stack; //bool 代表当从栈中弹出该节点时候，该节点是从左子树返回（true），还是从右子树返回（false） pair
           
             node_tag(root, true); TreeNode* node = root; while (true){ while (node){ //node节点及其左子节点肯定没有被访问 node_tag.first = node; node_tag.second = true; //去左子树，则出栈时候，表示该节点从左子树返回 node_stack.push(node_tag); } node_tag = node_stack.top(); node_stack.pop(); node = node_tag.first; while (node_tag.second == false){ //当前node是从右子树返回，则可以访问node节点 Visit(node); if (node_stack.empty()){ //表示所有的节点都已经访问完毕 return; } else{ node_tag = node_stack.top(); node_stack.pop(); node = node_tag.first; } } //node节点的左子数已经访问完毕，而右子树还没有开始被访问 node_tag.second = false; //进入右子树，则被出栈时，表明从右子树返回 node_tag.first = node; node_stack.push(node_tag); //进入右子树进行遍历 node = node->right; }}//树的前序遍历（递归）void PreOrderTravel_Recursive(TreeNode* root){ if (root){ Visit(root); PreOrderTravel_Recursive(root->left); PreOrderTravel_Recursive(root->right); }}//树的中序遍历（递归）void InOrderTravel_Recursive(TreeNode* root){ if (root){ InOrderTravel_Recursive(root->left); Visit(root); InOrderTravel_Recursive(root->right); }}//树的后序遍历（递归）void PostOrderTravel_Recursive(TreeNode* root){ if (root){ PostOrderTravel_Recursive(root->left); PostOrderTravel_Recursive(root->right); Visit(root); }}