先来些基本概念：

完全二叉树(Complete Binary Tree)

 

满二叉树（Full Binary Tree）

 

二叉排序树 (二叉查找树)（Binary Sort Tree）

 

平衡二叉树（Balanced Binary Tree）

平衡二叉树是一种自平衡二叉查找树算法。在AVL中任何节点的两个儿子子树的高度最大差别为一，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O（log n）。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。 平衡二叉树的常用算法有

红黑树、AVL、Treap、伸展树、SBT等。

可见，树的部分内容很多，变化也很丰富，这里先练习点基础的。

//二叉树#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;//二叉树节点定义template 
         
           struct BTNode{    T data;    BTNode
          
            *left; BTNode
           
             *right; BTNode() { left = NULL; right = NULL; }};typedef BTNode
            
              BinNode;//在完全二叉树中的索引值 + 结点valueBinNode* createIntBinTree(){ BinNode* root = NULL; BinNode* pNodes[255]; int i; int val; ifstream in("data.txt") ;#define cin in while ( cin >> i >> val ) { BinNode* node = new BinNode; node->data = val; pNodes[i] = node; if ( i == 1 ) root = node; else { int j = i/2; if ( i%2 == 0 ) pNodes[j]->left = node; else pNodes[j]->right = node; } } return root;}//创建完全二叉树,返回根节点BinNode* creatIntBTree(){ BinNode* root = NULL; vector
             
               vecPNode; vecPNode.push_back(NULL); ifstream in("data.txt") ;#define cin in //cout << "输入节点："; int i=0; int val; while(cin>>val) { ++i; BinNode* node = new BinNode; node->data = val; vecPNode.push_back(node); if (i==1) root = node; else { int parent = i/2; if (i%2==0) //left node vecPNode[parent]->left = node; else vecPNode[parent]->right = node; } }; vecPNode.clear(); return root;}//前序递归遍历void recurPreOrder(BinNode* root){ if(root) { cout << root->data << " "; recurPreOrder(root->left); recurPreOrder(root->right); }}//中序递归遍历void recurInOrder(BinNode* root){ if(root) { recurInOrder(root->left); cout << root->data << " "; recurInOrder(root->right); }}//后序递归遍历void recurPostOrder(BinNode* root){ if(root) { if(root->left) recurPostOrder(root->left); if(root->right) recurPostOrder(root->right); cout << root->data << " "; }}//非递归前序遍历void preOrder(BinNode* root){ BinNode* pn; pn = root; stack
              
                nodes; while(pn || !nodes.empty()) { if (pn) { cout << pn->data << " "; //入缓冲区时访问结点数据 nodes.push(pn); pn = pn->left; } else { BinNode* p = nodes.top(); nodes.pop(); pn = p->right; } }}//非递归中序遍历void inOrder(BinNode* root){ BinNode* pn = root; stack
               
                 sn; while (pn != NULL || !sn.empty()) { if (pn != NULL) { sn.push(pn); pn = pn->left; } else { BinNode* p = sn.top(); cout << p->data << " "; //出缓冲区时访问结点数据 sn.pop(); pn = p->right; } }}//后序遍历void postOrder(BinNode* root){ BinNode* pn = root; BinNode* pre = NULL; stack
                
                  sn; while(pn!=NULL || !sn.empty()) { if (pn!=NULL) { sn.push(pn); pn = pn->left; } else { BinNode* p = sn.top(); if (p->right == NULL || p->right == pre) //右子树为空或者右儿子已经被访问过，则访问该结点 { cout << p->data << " "; sn.pop(); pre = p; //记录最近一次被访问的结点 pn = NULL; } else { pn = p->right; } } }}int main (){ BinNode *tree = NULL; tree = creatIntBTree(); preOrder(tree); cout << endl; recurPreOrder(tree); cout << endl << endl; inOrder(tree); cout << endl; recurInOrder(tree); cout << endl << endl; postOrder(tree); cout << endl; recurPostOrder(tree); cout << endl << endl; return 0;}