程序１：二叉树的先中后序遍历
#include<iostream> //二叉树的先中后序遍历
using namespace std;
#include<stack>
struct Node
{
int value;
Node* left;
Node* right;
Node(int val)
{
value=val;
left=NULL;
right=NULL;
}
};
void preOrderRecur(Node* head) //递归,先
{
if(head==NULL)
{
return;
}
cout<<head->value<<endl;
preOrderRecur(head->left);
preOrderRecur(head->right);
}
void inOrderRecur(Node* head) //递归,中
{
if(head==NULL)
{
return;
}
inOrderRecur(head->left);
cout<<head->value<<endl;
inOrderRecur(head->right);
}
void posOrderRecur(Node* head) //递归,后
{
if(head==NULL)
{
return;
}
posOrderRecur(head->left);
posOrderRecur(head->right);
cout<<head->value<<endl;
}
void preOrderUnRecur(Node* head)//非递归,先序，准备一个栈，弹一个，先压右，后压左, 中，左，右
{
if(head!=NULL)
{
Node* tmp;
stack<Node*> s;
s.push(head);
while(!s.empty())
{
tmp=s.top();
cout<<tmp->value<<endl;
s.pop();
if(tmp->right!=NULL)
{
s.push(tmp->right);
}
if(tmp->left!=NULL)
{
s.push(tmp->left);
}
}
}
}
void inOrderUnRecur(Node* head)//非递归,中序
{
if(head!=NULL)
{
Node* tmp;
stack<Node*> s;
while(!s.empty()||head!=NULL)
{
if(head!=NULL)
{
s.push(head);
head=head->left;
}
else
{
tmp=s.top();
cout<<tmp->value<<endl;
s.pop();
head=tmp->right;
}
}
}
}
void posOrderUnRecur(Node* head)//非递归,后序，左，右，中,采用先序遍历的方式，不同之处先压左，再压右，不打印，按照中右左的次序放在栈中，之后再弹出
{
if(head!=NULL)
{
Node* tmp;
stack<Node*> s;
stack<Node*> s1;
s.push(head);
while(!s.empty())
{
tmp=s.top();
s1.push(tmp);
s.pop();
if(tmp->left!=NULL)
{
s.push(tmp->left);
}
if(tmp->right!=NULL)
{
s.push(tmp->right);
}
}
while (!s1.empty())
{
cout<<s1.top()->value<<endl;
s1.pop();
}
}
}
int main()
{
Node* head;
head=new Node(1);
head->left=new Node(2);
head->right=new Node(3);
preOrderUnRecur(head);
inOrderUnRecur(head);
posOrderUnRecur(head);
return 0;
}程序２：二叉树中的前驱和后继
#include<iostream> //二叉树中前驱和后继
using namespace std;
#include<stack>
struct Node
{
int value;
Node* left;
Node* right;
Node* parent;
Node(int val)
{
value=val;
}
};
Node* getMostLeft(Node* node)
{
if(node==NULL)
{
return node;
}
while(node->left!=NULL)
{
node=node->left;
}
return node;
}
Node* getsuccessorNode(Node* node) //找后继
{
if(node==NULL)
{
return NULL;
}
if(node->right!=NULL)
{
return getMostLeft(node->right);
}
else
{
Node* parent=node->parent;
while(parent!=NULL&&parent->left!=node)
{
node=parent;
parent=node->parent;
}
return parent;
}
}
Node* getMostRight(Node* node)
{
if(node==NULL)
{
return node;
}
while(node->right!=NULL)
{
node=node->right;
}
return node;
}
Node* getPresuccessorNode(Node* node) //找前驱
{
if(node==NULL)
{
return NULL;
}
if(node->left!=NULL)
{
return getMostRight(node->left);
}
else
{
Node* parent=node->parent;
while(parent!=NULL&&parent->right!=node)
{
node=parent;
parent=node->parent;
}
return parent;
}
}
int main()
{
return 0;
}程序３：二叉树的序列化和反序列化--未完成！！！！！
#include<iostream> //二叉树的序列化和反序列化
using namespace std;
#include<queue>
#include<string>
#include<sstream>
struct Node
{
int value;
Node* left;
Node* right;
Node(int val)
{
value=val;
}
};
string serialByPre(Node* head) //先序的方式序列化
{
if(head==NULL)
{
return "#!";
}
string res=to_string(head->value)+"!";
res+=serialByPre(head->left);
res+=serialByPre(head->right);
return res;
}
Node* reconPreOrder(queue<string> q)
{
string value=q.front();
q.pop();
if(value=="#")
{
return NULL;
}
Node* head=new Node(atoi(value.c_str()));
head->left=reconPreOrder(q);
head->right=reconPreOrder(q);
return head;
}
Node* reconByPreString(string prestr) //先序的方式反序列化
{
queue<string> q;
for(int i=0;i<prestr.length();i++)
{
if(prestr[i]=='#')
{
continue;
}
q.push(to_string(prestr[i]));
}
return reconPreOrder(q);
}
int main()
{
string res = "5!3!#!#!2!";
Node* b=reconByPreString(res);
cout<<b->value<<endl;
return 0;
}程序４：判断是否是平衡二叉树
#include<iostream> //判断是否是平衡二叉树
using namespace std;
#include<queue>
#include<string>
struct Node
{
int value;
Node* left;
Node* right;
Node(int val)
{
value=val;
}
};
class ReturnData
{
public:
ReturnData(bool isB,int h) //是否为平衡，高度是多少
{
this->isB=isB;
this->h=h;
}
bool isB;
int h;
};
ReturnData process(Node* head)
{
if(head==nullptr)
{
return ReturnData(true,0);
}
ReturnData leftData=process(head->left);
if(!leftData.isB)
{
return ReturnData(false,0);
}
ReturnData rightData=process(head->right);
if(!rightData.isB)
{
return ReturnData(false,0);
}
if(abs(leftData.h-rightData.h)>1)
{
return ReturnData(false,0);
}
return ReturnData(true,max(leftData.h,rightData.h)+1);
}
int main()
{
Node*head=nullptr;
head = new Node(2);
head->left = new Node(5);
head->right = new Node(6);
head->left->left = new Node(8);
cout<<process(head).h<<endl;;
cout<<process(head).isB<<endl;
return 0;
}程序５：是否搜索二叉树和完全二叉树
#include<iostream> //是否搜索二叉树和完全二叉树
using namespace std;
#include<queue>
#include<string>
#include<stack>
#include<limits.h>
struct Node
{
int value;
Node* left;
Node* right;
Node(int val)
{
value=val;
}
};
bool inOrderUnRecur(Node* head)//非递归,中序遍历判断是否为搜索二叉树
{
int pre = INT_MIN;
if(head!=NULL)
{
Node* tmp;
stack<Node*> s;
while(!s.empty()||head!=NULL)
{
if(head!=NULL)
{
s.push(head);
head=head->left;
}
else
{
tmp=s.top();
if(tmp->value<pre)
return false;
else
pre=tmp->value;
s.pop();
head=tmp->right;
}
}
return true;
}
}
bool isCBT(Node* head) //完全二叉树
{
if(head==nullptr)
{
return true;
}
bool leaf=false;
queue<Node*> q;
Node* l=nullptr;
Node* r=nullptr;
q.push(head);
while(!q.empty())
{
Node* tmp=q.front();
q.pop();
l=tmp->left;
r=tmp->right;
if((leaf&&(l!=nullptr||r!=nullptr))||(l==nullptr&&r!=nullptr))
{
return false;
}
if(l!=nullptr)
{
q.push(l);
}
if(r!=nullptr)
{
q.push(r);
}
else
{
leaf=true;
}
}
return true;
}
int main()
{
Node*head=nullptr;
head = new Node(2);
head->left = new Node(5);
head->right = new Node(6);
head->left->right = new Node(8);
cout<<inOrderUnRecur(head)<<endl;
cout<<isCBT(head);
return 0;
}程序６：求完全二叉树的节点个数
#include<iostream> //完全二叉树求节点个数
using namespace std;
#include<queue>
#include<string>
#include<stack>
#include<limits.h>
struct Node
{
int value;
Node* left;
Node* right;
Node(int val)
{
value=val;
}
};
int mostLeftLevel(Node* node,int level)
{
while(node!=nullptr)
{
level++;
node=node->left;
}
return level-1;
}
int bs(Node* node,int level,int h) // h:整棵树的高度,返回值为以node为头的树节点个数
{
if(level==h)
{
return 1;
}
if(mostLeftLevel(node->right,level+1)==h)
{
return (1<<(h-level)) + bs(node->right,level+1,h);
}
else
{
return (1<<(h-level-1)) + bs(node->left,level+1,h);
}
}
int nodeNum(Node* head)
{
if(head==nullptr)
{
return 0;
}
return bs(head,1,mostLeftLevel(head,1));
}
int main()
{
Node*head=nullptr;
head = new Node(5);
head->left = new Node(2);
head->right = new Node(6);
head->left->left=new Node(2);
head->left->right=new Node(3);
head->right->left=new Node(8);
cout<<nodeNum(head);
return 0;
}
京公网安备 11010502036488号