1、>> 二叉树的后续遍历非递归
void PostOrder_Nor()//后序遍历 非递归
{
if(_pRoot == NULL)
return;
stack<Node*> s;
Node* pCur = _pRoot;
Node* prev = NULL;//临时变量 保存刚刚访问过的节点
while(pCur || !s.empty())
{
while(pCur)//保存左边路径上的节点
{
s.push(pCur);
pCur = pCur->_pLeft;
}
if(!s.empty())//???
{
pCur = s.top();
if(pCur->_pRight == NULL || pCur->_pRight == prev)
{
cout<<pCur->_value<<" ";
prev = pCur;
s.pop();
pCur = NULL;//
}
else
pCur = pCur->_pRight;
}
}
}
2、>> 判断一棵树是否为完全二叉树
bool IsCompleteBinaryTree()
{
if(_pRoot == NULL)
return true;
queue<Node*> q;
Node* pCur = _pRoot;
q.push(pCur);
bool flag = false;
while(!q.empty())
{
pCur = q.front();
if(flag)
{
if(pCur->_pLeft || pCur->_pRight)
return false;
}
else
{
if(pCur->_pLeft && pCur->_pRight)
{
q.push(pCur->_pLeft);
q.push(pCur->_pRight);
}
else if(pCur->_pLeft)
{
q.push(pCur->_pLeft);
flag = true;
}
else if(pCur->_pRight)
return false;
else
flag = true;
}
q.pop();
}return true;
}
3、>> 根据前序和中序遍历结果重建二叉树
4、>> 寻找二叉树中两个结点的公共祖先结点
#include<iostream>
using namespace std;
#include<stack>
#include<vector>
typedef struct Node
{
char _data;
Node* _pLeft;
Node* _pRight;
Node(char data)
:_data(data)
,_pLeft(NULL)
,_pRight(NULL)
{}
~Node()
{
delete _pLeft;
delete _pRight;
}
};
Node* RebuildBinaryTree(char* PreOrder,char* InOrder,int n)
{
if(n == 0)
return NULL;
char data = PreOrder[0];//根据前序创建根
Node* node = new Node(data);
int i = 0;
for(i = 0; i<n && InOrder[i]!=data; i++)
;
int Leftlen = i;//左子树长度
int Rightlen = n-i-1;//不算中间的根节点 右子树长度
if(Leftlen)//递归左子树
node->_pLeft = RebuildBinaryTree(&PreOrder[1],&InOrder[0],Leftlen);
if(Rightlen)//递归右子树
node->_pRight = RebuildBinaryTree(&PreOrder[Leftlen+1],&InOrder[Leftlen+1],Rightlen);
return node;
}
bool FindPath(Node* pRoot, vector<char> &path, char key)//找路径
{
if(pRoot == NULL)
return false;
path.push_back(pRoot->_data);
if(pRoot->_data == key)
return true;
if(FindPath(pRoot->_pLeft,path,key)||FindPath(pRoot->_pRight,path,key))//在左右子树中找路径
return true;
path.pop_back();
return false;
}
char FindLCA(Node* pRoot,char key1, char key2)//找最近公共祖先节点
{
vector<char> path1;
vector<char> path2;
bool find1 = FindPath(pRoot, path1, key1);
bool find2 = FindPath(pRoot, path2, key2);
if(find1&&find2)
{
char ans;
int i;
for(i = 0; i<path1.size(); i++)
{
if(path1[i]!=path2[i])
break;
else
ans = path1[i];
}
return ans;
}
return -1;
}
int main()
{
char s1[6] = {'a','b','d','c','e','f'};
char s2[6] = {'d','b','a','e','c','f'};
Node* node = RebuildBinaryTree(s1,s2,6);
cout<<FindLCA(node,'e','d')<<endl;
system("pause");
return 0;
}
转载请注明原文地址: https://www.6miu.com/read-80605.html
