1.关于指针和引用的说明 数据结构中 建立 二叉树子函数，根结点为什么用双重指针，即 指针的指针。 因为树的结点要用指针描述。 如果只用指针，作形参传给建立结点的函数，这个指针传给了函数栈中的内存，函数返回后，函数栈销毁，不能获得结点。 而用指针的
1.关于指针和引用的说明
数据结构中建立二叉树子函数，根结点为什么用双重指针，即指针的指针。因为树的结点要用指针描述。如果只用指针，作形参传给建立结点的函数，这个指针值传给了函数栈中的内存，函数返回后，函数栈销毁，不能获得结点。而用指针的指针，函数内修改了这个双重指针指向的值（即结点指针），在函数外也能获得结点。这swap()函数要用指针而不能用值做参数一样。只是这里的值本身就是个指针，所以要用指针的指针。如下：
typedef struct BinaryTreeNode
{
char data;
BinaryTreeNode * leftChild;
BinaryTreeNode * rightChild;
}Node;
void Create(Node**T){......}
int main(){
Node* T;
Create(&T);
}<span><span> <span>如果Create的参数不是指针的引用（等同双指针）,</span></span></span><span><span><span><span>main中 Create(T)是把指针T指向的地址传进去了。注意,只是地址.</span></span></span><span><span><span>然后你在Create函数内部申请内存时, 把这个地址给改变了, 但是因为你传的是一个地址, 这个地址本身跟T无关,T仅仅是指向了这个地址而以. 所以Create(T)之后, T还是指向原来的地址,并未改变, 后面的操作当然就是崩溃了(因为T未初始化,是一个野指针)。</span></span></span><span><span><br></span></span><span><span><span> 传值: 函数内部修改不会对原值内容进行改变. </span></span></span><span><span><span> 传址: 函数内部修改会影响原值.</span></span></span><span><span><span> 可能我们认为值的指针就是传址了.</span></span></span><span><span><span>如果是传值, 函数入栈的时候就是把这个变量的值压栈,如果是传址, 就是把指针压栈,但压栈的时候,本身实际也是写一个数值而以.</span></span></span><span><span><span>你传的是指针的情况下, 如果修改指针指向的内容, 那么函数外部会同步修改.</span></span></span><span><span><span>但是你传入的是指针, 但是又修改的是指针本身, 而不是其内容, 那么你这就相当于传值.</span></span></span><span><span><span>当你要修改指针本身的时候, 你可以这样理解.</span></span></span></span>
//比如有： 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;
<span> 第一种情况：a=1,b=5,*p=5，tmp=1 </span><pre class="brush:php;toolbar:false;"><span> 第二种情况：a=1,b=,*p=5，<span>tmp=5.</span> </span><span><span>这是因为指向指针的引用，不仅改变了指针所指的对象，也改变了指针本身。</span></span>
2.前序，中序，后序遍历的简单说明
<span><span><strong> </strong></span></span><span><span><span><strong>先序遍历</strong></span><span>也叫做先根遍历，前序遍历</span></span><span>，<span>可记做</span><strong><span><span>根</span></span><span>左右</span></strong><span>（二叉树父结点向下先左后右）。</span></span><span>首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树，如果二叉树为空则返回。</span><span>上图所示二叉树的先序遍历结果是：ABDECF。 </span></span><span><span> <span>已知中序遍历和后序遍历，可以确定唯一的前序遍历。</span></span></span>
<span><span> </span><span><span><span>中序遍历</span><span><span>也叫</span><span>做</span><span>中根遍历</span><span>、</span><span>中序周游，可记做</span><span><strong><span>左</span><span>根</span><span>右</span></strong></span><span>。</span></span><span>首先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时，仍然先遍历左子树，再访问根结点，最后遍历右子树。</span></span></span></span><span><span>注意的是：遍历左右子树时</span><span>仍然采用中序遍历方法。</span><span>中<span>序遍历的</span></span><span>时间复杂度</span><span><span>为</span>：O(n)。</span><span>如果一棵</span><span>二叉排序树</span><span>的节点值是数值，中序遍历的结果为升序排列的</span><span>数组</span><span>。可以利用该性质检测一棵树是否为二叉排序数。<span>上图所示</span><span>二叉树</span><span>中</span><span>序遍历结果：DBEAFC</span></span></span> <span><span> </span><span><span>已知前序遍历和后序遍历，</span><span><span><strong>不能</strong></span></span><span>确定唯一的中序遍历。</span></span></span>
<p><span></span></p><div class="aritcle_card flexRow">
<div class="artcardd flexRow">
<a class="aritcle_card_img" href="/ai/2523" title="梯子AI"><img
src="https://img.php.cn/upload/ai_manual/001/246/273/176907419527000.png" alt="梯子AI" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
<div class="aritcle_card_info flexColumn">
<a href="/ai/2523" title="梯子AI">梯子AI</a>
<p>百度推出的AI智能搜索</p>
</div>
<a href="/ai/2523" title="梯子AI" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span> </a>
</div>
</div><span><span><span> </span><span><span><strong>后序遍历</strong></span><span>（LRD）</span></span><span>也叫做</span><span>后根遍历</span><span>、后序周游，可记做</span><span><span>左右</span></span><span><span><strong>根</strong></span></span><span>。后序遍历有</span><span><span>递归算法</span></span><span>和非递归算法两种。</span></span></span><span><span>后序遍历首先遍历左子树，然后遍历右子树，最后遍历访问根结点，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根结点。即：</span><span>若</span><span>二叉树</span><span>为空则结束返回，</span><span>否则：</span><span>（1）后序遍历左子树</span><span>（2）后序遍历右子树（3）访问根结点。</span><span>如右图所示</span><span>二叉树</span><span>后序遍历结果：DEBFCA。
</span></span><span><span> </span><span><span>已知前序遍历和中序遍历，可以确定唯一的后序遍历。</span></span></span>
解释：前序或后序能够确定根节点，结合中序能够唯一确定左子树和右子树元素。而仅仅知道前序和后序时，当左右子树存在空时，无法唯一确定究竟是哪一棵树为空。即仅仅知道前序和后序，无法唯一的还原2叉树，即中序无法唯一确定。
3.程序代码以及说明
1.已知前序和中序排列，创建二叉树，并输出后序排列
2.已知中序和后序排列，创建二叉树，并输出前序排列
3.使用递归法遍历二叉树
#include "iostream"
using 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 <<"Wrong Input !!!"<<endl;return false;}
else
{int LeftTreeSize=strlen(midOrder)-strlen(rootposition);
MakeBinaryTree_PM(&(*root)->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 <<"Wrong Input !!!"<<endl;return false;}
else
{ /**将原来的中序排序分解为左子树和右子树并递归调用**/
int LeftSubTreeSize=strlen(midOrder)-strlen(rootposition);
int RightSubTreeSize=length-LeftSubTreeSize-1;
char* leftSubTree_mid=new char[length-1];strncpy(leftSubTree_mid,midOrder,LeftSubTreeSize);
char* leftSubTree_last=new char[length-1];strncpy(leftSubTree_last,lastOrder,LeftSubTreeSize);
char* rightSubTree_last=new char[length-1];strncpy(rightSubTree_last,lastOrder+LeftSubTreeSize,RightSubTreeSize);
MakeBinaryTree_ML(&(*root)->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
{cout<<Root->data;
PreTraverse(Root->leftchild);
PreTraverse(Root->rightchild);}
}
void MidTraverse(NodePoint Root)//嵌套中序遍历
{
if(Root==NULL);
else
{MidTraverse(Root->leftchild);
cout<<Root->data;
MidTraverse(Root->rightchild);}
}
void PostTraverse(Node* Root)//嵌套后序遍历
{
if (Root == NULL)
return;
PostTraverse(Root->leftchild);
PostTraverse(Root->rightchild);
cout << Root->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<<"由前序和中序得后序排列为: ";PostTraverse(Root);cout<<endl;
MakeBinaryTree_ML(&Root,mid,last,strlen(mid));<span style="font-family: Arial, Helvetica, sans-serif;">//使用指针的引用</span>
cout<<"由中序和后序得前序排列为: ";PreTraverse(Root);cout<<endl;
return 0;
}<span><span><strong>注意 </strong></span>1.必须知道中序，知道任何其他两种中的一种倘若知道，可建唯一的二叉树进而得到另外一种排序。 </span><span> 2.创建二叉树的时候，使用指针的引用作为形参，即双重指针。</span>
