二叉树的建立用了递归的思想，本质上是: 先建立根节点--->再建立左子树----->再建立右子树
二叉树的遍历分为先序遍历，中序遍历后序遍历，还有层序遍历 注意无论先序中序还是后序都是先遍历左子树再遍历右子树
由前序和中序遍历或由中序和后序遍历序列可以唯一确定一棵二叉树，而由前序和后序遍历序列不能唯一确定一棵二叉树前序和后序在本质上都是将父节点与子结点进行分离，但并没有指明左子树和右子树的能力，因此得到这两个序列只能明确父子关系，而不能确定一个二叉树
在知道根结点的情况下根据中序可得到左子树和右子树
不过利用这种方法建立的二叉树有个条件是树中不含有重复的结点
当然有简单的办法就是用带有NULL指针的先序遍历序列建立二叉树其中NULL指针用特殊的符号‘#’ 代替，这种方法建立树很快
代码如下：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<fstream>
using namespace std;
typedef struct BinaryTreeNode
{
char data;
BinaryTreeNode *left,*right;
}BinaryTreeNode;
//根据带有NULL 的先序序列建立二叉树 其中NULL的字符用特殊符号‘#’表示
void CreateBinaryTree(BinaryTreeNode**pRoot)//从控制台中读入字符串 字符之间用逗号隔开
{
char ch;
scanf("%c,",&ch);
if(ch=='#')//最后遇到‘#’ 递归自然会结束好好想想就清楚了。
{
*pRoot=NULL;
}
else
{
*pRoot=new BinaryTreeNode;//先建立根节点
(*pRoot)->data=ch;
CreateBinaryTree(&((*pRoot)->left));//建立左子树
CreateBinaryTree(&((*pRoot)->right));//建立右子树
}
}
//输出带有NULL指针的 先序序列其中NULL用特殊字符'#'表示
void PreOrder(BinaryTreeNode*pRoot)
{
if(pRoot==NULL)
{
printf("%c,",'#');
return;
}
printf("%c,",pRoot->data);
PreOrder(pRoot->left);
PreOrder(pRoot->right);
}
int main()
{
cout<<"please input PreOrder serialize"<<endl;
BinaryTreeNode *pRoot;
CreateBinaryTree(&pRoot);
cout<<"\nthe PreOrder is:"<<endl;
PreOrder(pRoot);
return 0;
}
以下代码 根据先序和中序或后序和中序建立二叉树及树的遍历
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<stack>
#include<queue>
using namespace std;
typedef int ElemType;
typedef struct BinaryTreeNode
{
ElemType data;
BinaryTreeNode *left,*right;
}BinaryTreeNode;
//二叉树的建立3 根据先序序列和中序序列建立一个二叉树 先序：DBACEGF 中序：ABCDEFG 令pre[]="DBACEGF" in[]="ABCDEFG"
BinaryTreeNode * CreateBinaryTree(ElemType * pre,ElemType *in,int length)//此种建立二叉树的方法本质上是先建立根结点 再建立左子树，再建立右子树
{
if(length<=0||pre==NULL||in==NULL)////递归出口长度为0时表示建树完毕
{
return NULL;
}
ElemType rootValue=pre[0];
BinaryTreeNode * root=new BinaryTreeNode ();//建立根节点
root->data=rootValue;
root->left=root->right=NULL;
int leftLength,rightLength,i=0;//左子树的长度，右子树的长度
while(i<length&&in[i]!=rootValue)
{
i++;
}
leftLength=i;
rightLength=length-leftLength-1;//注意对个一个遍历的序列一定满足rightLength+leftLength+1=length;左子树长度加上右子树长度加一个根结点的长度等于树所有结点的长度。
if(leftLength>0)//建立左子树
{
root->left=CreateBinaryTree(pre+1,in,leftLength);////此处的关键在于寻找右子树后序序列的起始地址，和右子树的中序序列的起始地址
}
if(rightLength>0)//建立右子树
{
root->right =CreateBinaryTree(pre+length-rightLength,in+length-rightLength,rightLength);////此处的关键在于寻找右子树后序序列的起始地址，和右子树的中序序列的起始地址
// 上一句等价于root->right =CreateBinaryTree(pre+1+leftLength,in+1+leftLength,rightLength);
}
return root;
}
//二叉树的建立2 根据后序序列和中序序列建立一个二叉树 后序：ACBFGED 中序：ABCDEFG 令post[]="ACBFGED" in[]="ABCDEFG"
BinaryTreeNode *CreateBinaryTree2(ElemType *post,ElemType * in,int length)//此种建立二叉树的方法本质上是先建立根节点再建立左子树，再建立右子树。
{
if(post==NULL||in==NULL||length<=0)//递归出口长度为0时表示建树完毕
{
return NULL;
}
ElemType rootValue=post[length-1];
BinaryTreeNode *root=new BinaryTreeNode();//建立根节点
root->data=rootValue;
root->left=root->right=NULL;
int leftLength,rightLength;//左子树的长度，右子树的长度
int i=0;
while(i<length&&in[i]!=rootValue)//遍历中序序列寻找根结点从而得到左子树的长度，和右子树的长度
{
i++;
}
leftLength=i;
rightLength=length-leftLength-1;//右子树的长度为总长度减去左子树长度和一个根结点长度
if(leftLength>0)//建立左子树
{
root->left=CreateBinaryTree2(post,in,leftLength);//此处的关键在于寻找左子树后序序列的起始地址，和中序序列的起始地址
}
if(rightLength>0)//建立右子树
{
root->right=CreateBinaryTree2(post+leftLength,in+length-rightLength,rightLength);//此处的关键在于寻找右子树后序序列的起始地址，和右子树的中序序列的起始地址
//等价于root->right=CreateBinaryTree2(post+leftLength,in+leftLength+1,rightLength);
}
return root;//最后返回根节点
}
void PreOrder(BinaryTreeNode * T)//递归先序遍历
{
if(T==NULL)//递归出口
{
return;
}
printf("%d",T->data);
PreOrder(T->left);
PreOrder(T->right);
}
void PostOrder(BinaryTreeNode * T)//递归后序遍历
{
if(T==NULL)//递归出口
{
return;
}
PostOrder(T->left);
PostOrder(T->right);
printf("%d",T->data);
}
void InOrder(BinaryTreeNode * T)//递归中序遍历
{
if(T==NULL)
{
return;
}
InOrder(T->left);
printf("%d",T->data);
InOrder(T->right);
}
// 以下为二叉树的先序的非递归遍历算法
// 对于任一结点pcur：
// 1)访问结点Pcur，并将结点pcur入栈,结点pcur一直左走
// 2)判断结点pcur的左孩子是否为空，若为空，则取栈顶结点并进行出栈操作，并将栈顶结点的右孩子置为当前的结点pcur，循环至 1);若不为空，则将P的左孩子置为当前的结点pcur;
// 3)直到P为NULL并且栈为空，则遍历结束。
void PreOrderBinaryTree(BinaryTreeNode* proot)
{
if(proot==NULL)//此句其实是多余的。
{
return;
}
stack<BinaryTreeNode*> stackTreeNode;
BinaryTreeNode *pcur=proot;//指向当前要访问的结点
while(pcur!=NULL||!stackTreeNode.empty())
{
while(pcur!=NULL)//一直往左走
{
printf("%d ",pcur->data);
stackTreeNode.push(pcur);
pcur=pcur->left;
}
if(!stackTreeNode.empty())//在出栈和访问栈顶元素之前要先检查是否为空
{
pcur=stackTreeNode.top();//pcur刚跳出上面的while循环时值为NULL 故要将其pucr当前的栈顶结点
stackTreeNode.pop();
pcur=pcur->right;
}
}
}
// 以下为二叉树的中序的非递归遍历算法
void InOrderBinaryTree(BinaryTreeNode* proot)
{
if(proot==NULL)//此句其实是多余的。
{
return;
}
stack<BinaryTreeNode*> stackTreeNode;
BinaryTreeNode *pcur=proot;//指向当前要访问的结点
while(pcur!=NULL||!stackTreeNode.empty())
{
while(pcur!=NULL)//一直向左走
{
stackTreeNode.push(pcur);
pcur=pcur->left;
}
if(!stackTreeNode.empty())//在出栈和访问栈顶元素之前要先检查是否为空
{
pcur=stackTreeNode.top();//pcur刚跳出上面的while循环时值为NULL 故要将其pucr当前的栈顶结点
printf("%d ",pcur->data);
stackTreeNode.pop();
pcur=pcur->right;
}
}
}
// 以下为二叉树的后序的非递归遍历算法
//思路：设立两个指针pcur ,和preVisted,,对于任一结点pcur，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左孩子的结点，此时该结点出现在栈顶，
//此时要判断此节点是否满是输出条件即：当前节点的右孩子如果为空或者已经被访问，则访问当前节点 否则则将pcur置为其右结点
void PostOrderBinaryTree(BinaryTreeNode* proot)
{
if(proot==NULL)//此句其实是多余的。
{
return;
}
stack<BinaryTreeNode*> stackTreeNode;
BinaryTreeNode *pcur=proot;//指向当前要访问的结点
BinaryTreeNode *preVisted=NULL;//指向前一结点被访问的结点
while(pcur!=NULL||!stackTreeNode.empty())
{
while(pcur!=NULL)//一直向左走
{
stackTreeNode.push(pcur);
pcur=pcur->left;
}
if(!stackTreeNode.empty())//在出栈和访问栈顶元素之前要先检查是否为空
{
pcur=stackTreeNode.top();//pcur刚跳出上面的while循环时值为NULL 故要将其pucr当前的栈顶结点
if(pcur->right==NULL||pcur->right==preVisted)//当前节点的右孩子如果为空或者已经被访问，则访问当前节点
{
printf("%d\t",pcur->data);
stackTreeNode.pop();
preVisted=pcur;//
pcur=NULL;//此句不要忘记
}
else//如果当前结点的右子结点存在且没被访问过
{
pcur=pcur->right;
}
}
}
}
//二叉树的层序遍历
void LevelOrderBinaryTree(BinaryTreeNode*proot)
{
if(proot==NULL)
{
return;
}
queue<BinaryTreeNode*>queueTreeNode;
queueTreeNode.push(proot);
while(!queueTreeNode.empty())
{
BinaryTreeNode *pNode=queueTreeNode.front();
queueTreeNode.pop();
printf("%d ",pNode->data);
if(pNode->left!=NULL)
{
queueTreeNode.push(pNode->left);
}
if(pNode->right!=NULL)
{
queueTreeNode.push(pNode->right);
}
}
}
//剑指offer 25题二叉树中和为某一值的路径
void FindPath(BinaryTreeNode *proot,int expectedSum,vector<int>&path,int currentSum)//currentSum 可以用在函数内定义一个static sum来代替
{
if(proot==NULL)
{
return;
}
currentSum+=proot->data;
path.push_back(proot->data);
bool isLeaf=proot->left==NULL&&proot->right==NULL;
if(isLeaf&¤tSum==expectedSum)// 找到路径则打印出来
{
vector<int>::iterator iter=path.begin();
for(;iter!=path.end();iter++)
{
printf("%d ",*iter);
}
printf("\n");
}
if(proot->left!=NULL)
{
FindPath(proot->left,expectedSum,path,currentSum);
}
if(proot->right!=NULL)
{
FindPath(proot->right,expectedSum,path,currentSum);
}
currentSum-=proot->data;//执行到这一步时说明已经访问到叶子结点了。其余结点不能执行到这步 后面开始回溯了。。
path.pop_back();
}
//剑指offer 25题二叉树中和为某一值的路径
void FindPath(BinaryTreeNode *proot,int expectedSum)
{
if(proot==NULL)
{
return ;
}
int currentSum=0;
vector<int> path;
FindPath(proot,expectedSum,path,currentSum);
}
//剑指offer 39题二叉树 的深度
int DeepthOfTree(BinaryTreeNode* proot)
{
if(proot==NULL)
{
return 0;
}
int leftLength=DeepthOfTree(proot->left);
int rightLength=DeepthOfTree(proot->right);
return (leftLength>rightLength)? leftLength+1:rightLength+1;
}
//求二叉树的深度类似求和为某一路径的解法。结点的最大的层次一定在叶子结点
void DeepthOfTree2(BinaryTreeNode *proot,int &curDeepth,int &maxDeepth)
{
if(proot==NULL)
{
return;
}
curDeepth=curDeepth+1;
if(proot->left==NULL&&proot->right==NULL)
{
if(maxDeepth<curDeepth)
{
maxDeepth=curDeepth;
}
}
if(proot->left!=NULL)
{
DeepthOfTree2(proot->left,curDeepth,maxDeepth);
}
if(proot->right!=NULL)
{
DeepthOfTree2(proot->right,curDeepth,maxDeepth);
}
curDeepth=curDeepth-1;//这句话不要忘记了
}
int DeepthOfTree2(BinaryTreeNode*proot)
{
if(proot==NULL)
{
return 0;
}
int curDeepth=0;
int maxDeepth=0;
DeepthOfTree2(proot,curDeepth,maxDeepth);
return maxDeepth;
}
//剑指offer 输入一棵二叉树的的根节点判断一棵二叉树是否为平衡二叉树
bool isBalancedTree2(BinaryTreeNode *proot)//
{
if(proot==NULL)
{
return true;
}
int leftDeepth=DeepthOfTree(proot->left);
int rightDeepth=DeepthOfTree(proot->right);
int diff=leftDeepth-rightDeepth;
if(diff>1||diff<-1)
{
return false;
}
return isBalancedTree2(proot->left)&&isBalancedTree2(proot->right);
}
int main()
{
//char pre[100]="DBACEGF",in[100]="ABCDEFG",post[100]="ACBFGED";//随意的一颗二叉树
// int Tree_length=strlen(pre);
// D
// B E
// A C G
// F
//char pre[100]="ABC",in[100]="CBA",post[100]="CBA";//二叉树只有左子树
//char pre[100]="",in[100]="",post[100]="";//二叉树为空
int pre[]={1,2,4,7,3,5,6,8},in[]={4,7,2,1,5,3,8,6},post[]={7,4,2,5,8,6,3,1};
// 1
// 2 3
// 4 5 6
// 7 8
int Tree_length=sizeof(pre)/sizeof(pre[0]);
BinaryTreeNode *T;
cout<<"****************根据先序和中序建立二叉树****************"<<endl;
T=CreateBinaryTree(pre,in,Tree_length);
cout<<"递归先序结果"<<endl;
PreOrder(T);//先序的递归算法
cout<<"\n非递归先序结果"<<endl;
PreOrderBinaryTree(T);//先序非递归算法
cout<<"\n递归中序结果"<<endl;
InOrder(T);
cout<<"\n非递归中序结果"<<endl;
InOrderBinaryTree(T);// 中序非递归算法
cout<<"\n后序结果"<<endl;
PostOrder(T);
cout<<"\n非递归后序结果"<<endl;
PostOrderBinaryTree(T);
cout<<"\n层序序结果"<<endl;
LevelOrderBinaryTree(T);
cout<<"\n****************根据后序和中序建立二叉树****************\n"<<endl;
T=CreateBinaryTree2(post,in,Tree_length);
cout<<"先序结果"<<endl;
PreOrder(T);
cout<<"\n中序结果"<<endl;
InOrder(T);
cout<<"\n递归后序结果"<<endl;
PostOrder(T);
cout<<"\n层序结果"<<endl;
LevelOrderBinaryTree(T);
//以下为剑指offer程序
cout<<"\n面试题25题找到的路径为："<<endl;
FindPath(T,8);
cout<<"\n面试题39二叉树的深度为"<<DeepthOfTree(T)<<endl;
cout<<"\n面试题39二叉树的深度为 方法二 "<<DeepthOfTree2(T)<<endl;
if(isBalancedTree2(T))
{
cout<<"\n此二叉树为平衡二叉树"<<endl;
}
else
{
cout<<"\n此二叉树不是平衡二叉树"<<endl;
}
return 0;
}