1.关于指针和引用的说明 数据结构中 建立 二叉树子函数，根结点为什么用双重指针，即 指针的指针。 因为树的结点要用指针描述。 如果只用指针，作形参传给建立结点的函数，这个指针传给了函数栈中的内存，函数返回后，函数栈销毁，不能获得结点。 而用指针的
1.关于指针和引用的说明
   数据结构中建立二叉树子函数，根结点为什么用双重指针，即指针的指针。因为树的结点要用指针描述。如果只用指针，作形参传给建立结点的函数，这个指针值传给了函数栈中的内存，函数返回后，函数栈销毁，不能获得结点。而用指针的指针，函数内修改了这个双重指针指向的值（即结点指针），在函数外也能获得结点。这swap()函数要用指针而不能用值做参数一样。只是这里的值本身就是个指针，所以要用指针的指针。如下：
typedef struct binarytreenode{ char data; binarytreenode * leftchild; binarytreenode * rightchild;}node;void create(node**t){......}int main(){ node* t; create(&t);}
如果create的参数不是指针的引用（等同双指针）,main中 create(t)是把指针t指向的地址传进去了。注意,只是地址.然后你在create函数内部申请内存时, 把这个地址给改变了, 但是因为你传的是一个地址, 这个地址本身跟t无关,t仅仅是指向了这个地址而以. 所以create(t)之后, t还是指向原来的地址,并未改变, 后面的操作当然就是崩溃了(因为t未初始化,是一个野指针)。
传值: 函数内部修改不会对原值内容进行改变. 传址: 函数内部修改会影响原值. 可能我们认为值的指针就是传址了.如果是传值, 函数入栈的时候就是把这个变量的值压栈,如果是传址, 就是把指针压栈,但压栈的时候,本身实际也是写一个数值而以.你传的是指针的情况下, 如果修改指针指向的内容, 那么函数外部会同步修改.但是你传入的是指针, 但是又修改的是指针本身, 而不是其内容, 那么你这就相当于传值.当你要修改指针本身的时候, 你可以这样理解.
//比如有：void creat(btnode *proot);//可以修改成以下形式typedef btnode* pnode;void creat(pnode proot);//这时你可能就看出来了, 原来这是一个传值调用.想要修改proot的值, 那么就要void creat(pnode &proot); ====还原就是 void creat(btnode* &proot);//或者void creat(pnode *proot); ====还原就是 void creat(btnode* *proot);
反正注意区分传址还是传值的区分不是看参数是否是指针, 而是要看你在函数内部是如何操作参数的. 如果你操作的是参数本身, 那么就是传值.如果你是把参数当成一个地址, 操作的是那个地址上的内容,那就是传址。一个简单的例子：
int a = 1;int b = 2;int *tmp = &a;int *p = tmp;// 第二种情况：int *&p = tmp；(此即是指向指针的引用)p = &b;*p = 5;
第一种情况：a=1,b=5,*p=5，tmp=1  第二种情况：a=1,b=,*p=5，tmp=5. 这是因为指向指针的引用，不仅改变了指针所指的对象，也改变了指针本身。
2.前序，中序，后序遍历的简单说明
先序遍历也叫做先根遍历，前序遍历，可记做根左右（二叉树父结点向下先左后右）。首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树，如果二叉树为空则返回。上图所示二叉树的先序遍历结果是：abdecf。    已知中序遍历和后序遍历，可以确定唯一的前序遍历。
中序遍历也叫做中根遍历、中序周游，可记做左根右。首先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时，仍然先遍历左子树，再访问根结点，最后遍历右子树。注意的是：遍历左右子树时仍然采用中序遍历方法。中序遍历的时间复杂度为：o(n)。如果一棵二叉排序树的节点值是数值，中序遍历的结果为升序排列的数组。可以利用该性质检测一棵树是否为二叉排序数。上图所示二叉树中序遍历结果：dbeafc    已知前序遍历和后序遍历，不能确定唯一的中序遍历。
后序遍历（lrd）也叫做后根遍历、后序周游，可记做左右根。后序遍历有递归算法和非递归算法两种。后序遍历首先遍历左子树，然后遍历右子树，最后遍历访问根结点，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根结点。即：若二叉树为空则结束返回，否则：（1）后序遍历左子树（2）后序遍历右子树（3）访问根结点。如右图所示二叉树后序遍历结果：debfca。    已知前序遍历和中序遍历，可以确定唯一的后序遍历。
解释：前序或后序能够确定根节点，结合中序能够唯一确定左子树和右子树元素。而仅仅知道前序和后序时，当左右子树存在空时，无法唯一确定究竟是哪一棵树为空。即仅仅知道前序和后序，无法唯一的还原2叉树，即中序无法唯一确定。
3.程序代码以及说明
1.已知前序和中序排列，创建二叉树，并输出后序排列
   2.已知中序和后序排列，创建二叉树，并输出前序排列
   3.使用递归法遍历二叉树
#include iostreamusing namespace std;typedef struct binarytreenode//二叉树节点 { char data; binarytreenode* leftchild; binarytreenode* rightchild; }node,*nodepoint; bool makebinarytree_pm(nodepoint* root,char* preorder, char* midorder,int length)//基于前序和中序遍历计算后序遍历 { if(length==0) {*root=null;return true;} else { *root=new node; (*root)->data=*preorder;//前序第一个元素为根节点 char * rootposition = strchr(midorder,(*root)->data);//查找根节点在排序中的位置 if (rootposition == null) {cout leftchild,preorder+1,midorder,lefttreesize); makebinarytree_pm(&(*root)->rightchild,preorder+lefttreesize+1,rootposition+1,length-lefttreesize-1); return true; } } }bool makebinarytree_ml(nodepoint* root,char* midorder,char* lastorder,int length)//基于中序和后序遍历计算前序遍历 { if(length==0) {*root=null;return true;} else { *root=new node; (*root)->data=lastorder[length-1];//后序最后一个元素为根节点 char * rootposition = strchr(midorder,(*root)->data);//查找根节点在排序中的位置 if (rootposition == null) {cout leftchild,leftsubtree_mid,leftsubtree_last,leftsubtreesize); delete[]leftsubtree_mid;delete[]leftsubtree_last; makebinarytree_ml(&(*root)->rightchild,rootposition+1,rightsubtree_last,rightsubtreesize); delete []rightsubtree_last; return true; } } } void pretraverse(nodepoint root)//嵌套前序遍历 { if(root==null); else {coutdata; pretraverse(root->leftchild); pretraverse(root->rightchild);} }void midtraverse(nodepoint root)//嵌套中序遍历 { if(root==null); else {midtraverse(root->leftchild); coutdata; midtraverse(root->rightchild);} }void posttraverse(node* root)//嵌套后序遍历{ if (root == null) return; posttraverse(root->leftchild); posttraverse(root->rightchild); cout data;}int main(int argc, const char** argv){ char pre[] = abdeijcfg;//前序 char mid[] = dbiejafcg;//中序 char last[]=dijebfgca;//后序 node* root; makebinarytree_pm(&root, pre, mid, strlen(pre));//使用指针的引用 cout//使用指针的引用 cout
 注意 1.必须知道中序，知道任何其他两种中的一种倘若知道，可建唯一的二叉树进而得到另外一种排序。      2.创建二叉树的时候，使用指针的引用作为形参，即双重指针。