基于C++类和指针实现二叉树1、二叉树的定义　　二叉树（Binary Tree）是一种特殊的树型结构，每个节点至多有两棵子树，且二叉树的子树有左右之分，次序不能颠倒。　　由定义可知，二叉树中不存在度（结点拥有的子树数目）大于2的节点。二叉树形状如下下图所示：2、二叉树的性质（1）在二叉树中的第i层上至多有2^(i-1)个结点（i>=1)。备注:^表示此方（2）深度为k的二叉树至多有2^k-1个节点（k>=1)。（3）对任何一棵二叉树T，如果其终端结点数目为n0，度为2的节点数目为n2，则n0=n2+1。满二叉树：深度为k且具有2^k-1个结点的二叉树。即满二叉树中的每一层上的结点数都是最大的结点数。完全二叉树：深度为k具有n个结点的二叉树，当且仅当每一个结点与深度为k的满二叉树中的编号从1至n的结点一一对应。可以得到一般结论：满二叉树和完全二叉树是两种特殊形态的二叉树，满二叉树肯定是完全二叉树，但完全二叉树不不一定是满二叉树。举例如下图是所示：（4）具有n个节点的完全二叉树的深度为log2n+ 1

1.二叉树和二叉搜索树（二叉查找树）的区别：

二叉树：每个节点的子节点不允许超过两个--可以0个、1个、至多2个；

二叉搜索树：1.每个节点的子节点不能超过两个，2.同时相对较小的值保存在左节点（left-child）,较大的值保存在右节点（right-child）

2.前序、中序和后序遍历的方法和顺序：

2.1前序遍历：

先访问根节点(root) -> 左子节点(left-child) -> 右子节点(right-child)

2.2中序遍历：

先访问左子节点(left-child) -> 根节点(root) -> 右子节点(right-child)

2.3后序遍历

先访问左子节点(left-child) -> 右子节点(right-child) -> 根节点(root)

3.实例分析

3.1 普通二叉树

$基于C++类和指针实现二叉树1、二叉树的定义　　二叉树（Binary Tree）是一种特殊的树型结构，每个节点至多有两棵子树，且二叉树的子树有左右之分，次序不能颠倒。　　由定义可知，二叉树中不存在度（结点拥有的子树数目）大于2的节点。二叉树形状如下下图所示：2、二叉树的性质（1）在二叉树中的第i层上至多有2^(i-1)个结点（i>=1)。备注:^表示此方（2）深度为k的二叉树至多有2^k-1个节点（k>=1)。（3）对任何一棵二叉树T，如果其终端结点数目为n0，度为2的节点数目为n2，则n0=n2+1。满二叉树：深度为k且具有2^k-1个结点的二叉树。即满二叉树中的每一层上的结点数都是最大的结点数。完全二叉树：深度为k具有n个结点的二叉树，当且仅当每一个结点与深度为k的满二叉树中的编号从1至n的结点一一对应。可以得到一般结论：满二叉树和完全二叉树是两种特殊形态的二叉树，满二叉树肯定是完全二叉树，但完全二叉树不不一定是满二叉树。举例如下图是所示：（4）具有n个节点的完全二叉树的深度为log2n+ 1。3、二叉树的存储结构　　可以采用顺序存储数组和链式存储二叉链表两种方法来存储二叉树。经常使用的二叉链表方法，因为其非常灵活，方便二叉树的操作。二叉树的二叉链表存储结构如下所示：1 typedef struct binary_tree_node2 {3 int elem;4 struct binary_tree_node *left;5 struct binary_tree_node *right;6 }binary_tree_node,*binary_tree;举例说明二叉链表存储过程，如下图所示：从图中可以看出：在还有n个结点的二叉链表中有n+1个空链域。4、遍历二叉树　　遍历二叉树是按照指定的路径方式访问书中每个结点一次，且仅访问一次。由二叉树的定义，我们知道二叉数是由根结点、左子树和右子树三部分构成的。通常遍历二叉树是从左向右进行，因此可以得到如下最基本的三种遍历方法：（1）先根遍历（先序遍历）：如果二叉树为空，进行空操作；否则，先访问根节点，然后先根遍历左子树，最后先根遍历右子树。采用递归形式实现代码如下：$

前序遍历(PreOrder traversal): G->D->A->F->E->M->H->Z

中序遍历(InOrder traversal): A->D->G->E->F->H->M->Z(X-error!) A->D->E->F->G->H->M->Z(√ - right)

后序遍历(PostOrder traversal): A->E->F->H->Z->D->M->G(X-error!) A->E->F->D->H->Z->M->G(√ - right)

3.1.1 已知前序、中序遍历，求后序遍历(转点击打开链接)

例：

前序遍历: GDAFEMHZ

中序遍历: ADEFGHMZ

画树求法：
第一步，根据前序遍历的特点，我们知道根结点为G

第二步，观察中序遍历ADEFGHMZ。其中root节点G左侧的ADEF必然是root的左子树，G右侧的HMZ必然是root的右子树。

第三步，观察左子树ADEF，左子树的中的根节点必然是大树的root的leftchild。在前序遍历中，大树的root的leftchild位于root之后，所以左子树的根节点为D。

第四步，同样的道理，root的右子树节点HMZ中的根节点也可以通过前序遍历求得。在前序遍历中，一定是先把root和root的所有左子树节点遍历完之后才会遍历右子树，并且遍历的左子树的第一个节点就是左子树的根节点。同理，遍历的右子树的第一个节点就是右子树的根节点。

第五步，观察发现，上面的过程是递归的。先找到当前树的根节点，然后划分为左子树，右子树，然后进入左子树重复上面的过程，然后进入右子树重复上面的过程。最后就可以还原一棵树了。该步递归的过程可以简洁表达如下：

1 确定根,确定左子树，确定右子树。

2 在左子树中递归。

3 在右子树中递归。

4 打印当前根。

那么，根据后序的遍历规则，我们可以知道，后序遍历顺序为：AEFDHZMG

编程求法：（依据上面的思路，写递归程序）

#include<iostream>
#include<fstream>
#include<string>
using  std::cout;
using  std::endl;

struct TreeNode{
struct TreeNode* left;
struct TreeNode* right;
char elem;
};

void BinaryTreeFromOrderings(char* inorder, char * preorder, int length){
if (length == 0){
//cout << "Invalid length!" << endl;
return;
}
TreeNode* node = new TreeNode;
node->elem = *preorder;
int rootIndex = 0;
for (; rootIndex < length; rootIndex++){
if (inorder[rootIndex] == *preorder)
break;
}
//Left
BinaryTreeFromOrderings(inorder, preorder + 1, rootIndex);
//Right
BinaryTreeFromOrderings(inorder+rootIndex+1,preorder+rootIndex+1,length-(rootIndex+1));
cout << node->elem << "->";  //输出postOrder: A->E->F->D->H->Z->M->G->  ??WHY
return;
}

int main()
{
char * pre = "GDAFEMHZ";
char * in =  "ADEFGHMZ" ;
BinaryTreeFromOrderings(in, pre, 8);
cout << endl;
return 0;
}

3.1.2 已知中序和后序遍历，求前序遍历

依然是上面的题，这次我们只给出中序和后序遍历：

中序遍历: ADEFGHMZ

后序遍历: AEFDHZMG

画树求法：
第一步，根据后序遍历的特点，我们知道后序遍历最后一个结点即为根结点，即根结点为G。

第二步，观察中序遍历ADEFGHMZ。其中root节点G左侧的ADEF必然是root的左子树，G右侧的HMZ必然是root的右子树。

第三步，观察左子树ADEF，左子树的中的根节点必然是大树的root的leftchild。在前序遍历中，大树的root的leftchild位于root之后，所以左子树的根节点为D。

第四步，同样的道理，root的右子树节点HMZ中的根节点也可以通过前序遍历求得。在前后序遍历中，一定是先把root和root的所有左子树节点遍历完之后才会遍历右子树，并且遍历的左子树的第一个节点就是左子树的根节点。同理，遍历的右子树的第一个节点就是右子树的根节点。

第五步，观察发现，上面的过程是递归的。先找到当前树的根节点，然后划分为左子树，右子树，然后进入左子树重复上面的过程，然后进入右子树重复上面的过程。最后就可以还原一棵树了。该步递归的过程可以简洁表达如下：

1 确定根,确定左子树，确定右子树。

2 在左子树中递归。

3 在右子树中递归。

4 打印当前根。

这样，我们就可以画出二叉树的形状，如上图所示，这里就不再赘述。

那么，前序遍历: GDAFEMHZ

编程求法：（并且验证我们的结果是否正确）

#include<iostream>
#include<fstream>
#include<string>
using  std::cout;
using  std::endl;

struct TreeNode{
struct TreeNode* left;
struct TreeNode* right;
char elem;
};

TreeNode* BinaryTreeFromOrderings(char* inorder, char * postorder, int length){
if (length == 0){
//cout << "Invalid length!" << endl;
return NULL;
}
TreeNode* node = new TreeNode;
node->elem = *(postorder + length - 1);
cout << node->elem << "->";  //注意cout的位置！ Preorder : G->D->A->F->E->M->H->Z->
int rootIndex = 0;
for (; rootIndex < length; rootIndex++){
if (inorder[rootIndex] == *(postorder + length - 1))
break;
}
node->left = BinaryTreeFromOrderings(inorder, postorder,rootIndex);
node->right = BinaryTreeFromOrderings(inorder+rootIndex+1,postorder+rootIndex,length-(rootIndex+1));

return node;
}

int main()
{
char * post = "AEFDHZMG";
char * in = "ADEFGHMZ";
BinaryTreeFromOrderings(in, post, 8);
cout << endl;
return 0;
}

3.2 二叉搜索树的后序遍历

题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是返回true,否则返回false.

解析：例如输入数组 {5,7,6,9,11,10,8}，则返回true。解释在【分析】中；如果输入的数组是{7,4,6,5}，则返回false;

因为二叉搜索树中会有大小关系-----left_child->value < root->value < right_child->value 而这里（右子节点->4 > root->5 不符）

分析：

1. 后序遍历最后一个节点对应的值为根节点对应的值，即root->value = 8;

2. 比8小的是左子节点对应的值--{5,7,6}；比8大的是右子节点对应的值--{9,11,10}；

3. 递归思想：在左子节点{5,7,6}中 root->value = 6; 因为5<6,所以5是左节点对应的值，7>6，所以7是右节点对应的值

在右子节点{9,11,10}中root->value = 10; 因为9<10,所以9是左节点对应的值，11>10，所以10是右节点对应的值

4.判断是否是最后一个节点，可得下图：

代码如下：

class Solution {
public:
    bool IsSubtree(vector<int> sequence){
       int n = 0, root = 0;
        n = sequence.size();
        if(n == 1 || n == 0) return true;
        //else if (n == 0) return false; 子节点可以不存在！
        root = sequence[n-1];
        vector<int> leftTree; //依次保存递归使用的子树
        vector<int> rightTree;
        int i = 0 ;// 在如下两个for循环*同使用，目的是为了顺序遍历每个节点
        for(;i < n-1; i++){
            if(sequence[i] < root)
            leftTree.push_back(sequence[i]);
            else
                break;
        }
        for(;i < n-1; i++){
            if(sequence[i] > root)
                rightTree.push_back(sequence[i]);
            else
                return false;
        }
        return IsSubtree(leftTree) && IsSubtree(rightTree);
        }       
    bool VerifySquenceOfBST(vector<int> sequence) {
        int n = 0;
        n = sequence.size();
        if( n == 0)
            return false;
        return IsSubtree(sequence);
    }
       
};

使用先序、中序、后序遍历的方法对二叉树的依次访问：

转自  基于C++类和指针实现二叉树

1、二叉树的定义
　　二叉树（Binary Tree）是一种特殊的树型结构，每个节点至多有两棵子树，且二叉树的子树有左右之分，次序不能颠倒。
　　由定义可知，二叉树中不存在度（结点拥有的子树数目）大于2的节点。二叉树形状如下下图所示：
2、二叉树的性质
（1）在二叉树中的第i层上至多有2^(i-1)个结点（i>=1)。备注:^表示此方
（2）深度为k的二叉树至多有2^k-1个节点（k>=1)。
（3）对任何一棵二叉树T，如果其终端结点数目为n0，度为2的节点数目为n2，则n0=n2+1。
满二叉树：深度为k且具有2^k-1个结点的二叉树。即满二叉树中的每一层上的结点数都是最大的结点数。
完全二叉树：深度为k具有n个结点的二叉树，当且仅当每一个结点与深度为k的满二叉树中的编号从1至n的结点一一对应。
可以得到一般结论：满二叉树和完全二叉树是两种特殊形态的二叉树，满二叉树肯定是完全二叉树，但完全二叉树不不一定是满二叉树。
举例如下图是所示：
（4）具有n个节点的完全二叉树的深度为log_2ⁿ + 1。
3、二叉树的存储结构
　　可以采用顺序存储数组和链式存储二叉链表两种方法来存储二叉树。经常使用的二叉链表方法，因为其非常灵活，方便二叉树的操作。二叉树的二叉链表存储结构如下所示：
1 typedef struct binary_tree_node2 {3     int elem;4     struct binary_tree_node *left;5     struct binary_tree_node *right;6 }binary_tree_node,*binary_tree;
举例说明二叉链表存储过程，如下图所示：

从图中可以看出：在还有n个结点的二叉链表中有n+1个空链域。
4、遍历二叉树
　　遍历二叉树是按照指定的路径方式访问书中每个结点一次，且仅访问一次。由二叉树的定义，我们知道二叉数是由根结点、左子树和右子树三部分构成的。通常遍历二叉树是从左向右进行，因此可以得到如下最基本的三种遍历方法：
（1）先根遍历（先序遍历）：如果二叉树为空，进行空操作；否则，先访问根节点，然后先根遍历左子树，最后先根遍历右子树。采用递归形式实现代码如下：
1 void preorder_traverse_recursive(binary_tree root)
2 {
3     if(NULL != root)
4     {
5         printf("%d\t",root->elem);
6         preorder_traverse_recursive(root->left);
7         preorder_traverse_recursive(root->right);
8     }
9 }
具体过程如下图所示：

（2）中根遍历（中序遍历）：如果二叉树为空，进行空操作；否则，先中根遍历左子树，然后访问根结点，最后中根遍历右子树。递归过程实现代码如下：
1 void inorder_traverse_recursive(binary_tree root)
2 {
3     if(NULL != root)
4     {
5         inorder_traverse_recursive(root->left);
6         printf("%d\t",root->elem);
7         inorder_traverse_recursive(root->right);
8     }
9 }
具体过程如下图所示：

（3）后根遍历（后序遍历）：如果二叉树为空，进行空操作；否则，先后根遍历左子树，然后后根遍历右子树，最后访问根结点。递归实现代码如下：
1 void postorder_traverse_recursive(binary_tree root)
2 {
3     if(NULL != root)
4     {
5         postorder_traverse_recursive(root->left);
6         postorder_traverse_recursive(root->right);
7         printf("%d\t",root->elem);
8     }
9 }
具体过程如下图所示：

用类和指针实现的二叉树：

[cpp] view plain copy print? 
   
#include<iostream>   
    using namespace std;   
    struct tree   
    {   
        int data;   
        tree *left,*right;   
    };   
    class Btree   
    {   
        static int n;   
        static int m;   
    public:   
        tree *root;   
        Btree()   
        {   
            root=NULL;   
        }   
        void create_Btree(int);   
        void Preorder(tree *);                  //先序遍历   
        void inorder(tree *);                   //中序遍历   
        void Postorder(tree *);                 //后序遍历   
        void display1() {Preorder(root); cout<<endl;}   
        void display2() {inorder(root);cout<<endl;}   
        void display3() {Postorder(root); cout<<endl;}     
        int count(tree *);                      //计算二叉树的个数   
        int findleaf(tree *);                   //求二叉树叶子的个数   
        int findnode(tree *);                   //求二叉树中度数为1的结点数量,这是当初考数据结构时候的最后一道题目   
    };                                             
    int Btree::n=0;   
    int Btree::m=0;   
    void Btree::create_Btree(int x)   
    {   
        tree *newnode=new tree;   
        newnode->data=x;   
        newnode->right=newnode->left=NULL;   
        if(root==NULL)   
            root=newnode;   
        else   
        {   
            tree *back;   
            tree *current=root;   
            while(current!=NULL)   
            {   
                back=current;   
                if(current->data>x)   
                    current=current->left;   
                else   
                    current=current->right;   
            }   
            if(back->data>x)   
                back->left=newnode;   
            else   
                back->right=newnode;   
        }   
    }   
    int Btree::count(tree *p)   
    {   
        if(p==NULL)   
            return 0;   
        else   
            return count(p->left)+count(p->right)+1;      //这是运用了函数嵌套即递归的方法。   
    }   
    void Btree::Preorder(tree *temp)    //这是先序遍历二叉树，采用了递归的方法。   
    {   
        if(temp!=NULL)   
        {   
            cout<<temp->data<<" ";   
            Preorder(temp->left);   
            Preorder(temp->right);   
        }   
    }   
    void Btree::inorder(tree *temp)      //这是中序遍历二叉树，采用了递归的方法。   
    {   
        if(temp!=NULL)   
        {   
            inorder(temp->left);   
            cout<<temp->data<<" ";   
            inorder(temp->right);   
        }   
    }   
    void Btree::Postorder(tree *temp)     //这是后序遍历二叉树，采用了递归的方法。   
    {   
        if(temp!=NULL)   
        {   
            Postorder(temp->left);   
            Postorder(temp->right);   
            cout<<temp->data<<" ";   
        }   
    }   
    int Btree::findleaf(tree *temp)   
    {   
        if(temp==NULL)return 0;   
        else   
        {   
            if(temp->left==NULL&&temp->right==NULL)return n+=1;   
            else   
            {   
                findleaf(temp->left);   
                findleaf(temp->right);   
            }   
            return n;   
        }   
    }   
    int Btree::findnode(tree *temp)   
    {   
        if(temp==NULL)return 0;   
        else   
        {   
            if(temp->left!=NULL&&temp->right!=NULL)   
            {   
                findnode(temp->left);   
                findnode(temp->right);   
            }   
            if(temp->left!=NULL&&temp->right==NULL)   
            {   
                m+=1;   
                findnode(temp->left);   
            }   
            if(temp->left==NULL&&temp->right!=NULL)   
            {   
                m+=1;   
                findnode(temp->right);   
            }   
        }   
        return m;   
    }   
       
       
    void main()   
    {   
        Btree A;   
        int array[]={100,4,2,3,15,35,6,45,55,20,1,14,56,57,58};   
        int k;   
        k=sizeof(array)/sizeof(array[0]);   
        cout<<"建立排序二叉树顺序: "<<endl;   
        for(int i=0;i<k;i++)   
        {   
            cout<<array[i]<<" ";   
            A.create_Btree(array[i]);   
        }   
        cout<<endl;   
        cout<<"二叉树节点个数： "<<A.count(A.root)<<endl;   
        cout<<"二叉树叶子个数："<<A.findleaf(A.root)<<endl;   
        cout<<"二叉树中度数为1的结点的数量为："<<A.findnode(A.root)<<endl;   
        cout<<endl<<"先序遍历序列: "<<endl;   
        A.display1();   
        cout<<endl<<"中序遍历序列: "<<endl;   
        A.display2();   
        cout<<endl<<"后序遍历序列: "<<endl;   
        A.display3();   
    }