交换二叉树中每个结点的左孩子和右孩子
以二叉链表作为二叉树的存储结构，交换二叉树中每个结点的左孩子和右孩子。
输入格式:
输入二叉树的先序序列。
提示：一棵二叉树的先序序列是一个字符串，若字符是‘#’,表示该二叉树是空树，否则该字符是相应结点的数据元素。
输出格式:
输出有两行：
第一行是原二叉树的中序遍历序列；
第二行是交换后的二叉树的中序遍历序列。
输入样例:
ABC##DE#G##F###
输出样例:
CBEGDFA
AFDGEBC
/*以二叉链表作为二叉树的存储结构:
完成 1:统计二叉树的叶结点个数.
完成 2:判别两棵树是否相等
完成 3:交换二叉树每个节点的左孩子和右孩子
4:设计二叉树的双序遍历(双序遍历就是指对于二叉树的每个节点，先访问这个节点
，再按双序遍历她的左子树，然后在访问这个节点，然后在按双序遍历它右子树 )
5:计算二叉树的最大宽度(就是所有层中结点个数最大值)
6:用按层次遍历二叉树的方法，统计树中度为1的节点数目
7:求二叉树第一条最长路径的长度，并输出次路径上个节点值
完成 8:输出二叉树中从每个叶子节点到根节点的路径
*/
#include <iostream>
using namespace std;
#define MAXSIZE 100 //栈和队列中需要的长度
//***********节点类**************
class Tree;
class Node
{
private:
int Data;
Node* Lchild;
Node* Rchild;
public:
Node()
{
Lchild = NULL;
Rchild = NULL;
}
int Return_Data(){return Data;} //返回数据域
Node* Return_Lchild(){return Lchild;} //返回做孩子
Node* Return_Rchild(){return Rchild;} //返回右孩子
friend class Tree; //声明Node类为Tree的友元类
};
//**********Tree类***************
class Tree
{
private:
int Leaf_Numbers;
Node* Root;
int Front; //栈顶指针
int Rear; //栈底指针
Node* NodeStack[MAXSIZE];
public:
Tree()
{
Leaf_Numbers = 0;
Root = NULL;
Front = -1;
Rear = 0;
for(int i = 0; i < MAXSIZE; i++)
{
NodeStack[i] = NULL;
}
}
//************函数**************
void CreatTree(Node* &); //先序递归创建节点
void TheCreatTree();
void TraveFront(Node* ); //先序遍历
void TheTraveFront();
void Numbers_Leafs(Node*); //计算叶子节点数
void TheNumbers_Leafs();
int Return_LeafNums();
Node* Return_Root(){return Root;} //返回树的头结点
void ExchangeLR(Node*); //交换二叉树的左右子树
void TheExchangeLR();
void Leaf_Root(Node*); //叶子到根节点的路径
/*算法：1.申请一个对象指针数组用于存储节点的地址 用于栈的先进后出
2.从根节点先把左子树进栈，在右子树进栈
3.在节点进站后，当它左子树为空判断右子树是否为空，为空把它只有兄弟进站
否则吧它右子树进站
4.当节点左右子树都为空，把它进站，从栈顶退栈，把吧剩余的战中元素遍历但不退栈
然后检查它右兄弟
5.重复3 4*/
void TheLeaf_Root();
};
void Tree::CreatTree(Node* &p)
{
int x;
cin>>x;
if(x != -1)
{
p = new Node();
p->Data = x;
CreatTree(p->Lchild);
CreatTree(p->Rchild);
}
}
void Tree::TheCreatTree()
{
CreatTree(Root);
}
void Tree::TraveFront(Node* p)
{
if(p != NULL)
{
cout<<p->Data<<" ";
TraveFront(p->Lchild);
TraveFront(p->Rchild);
}
}
void Tree::TheTraveFront()
{
TraveFront(Root);
}
void Tree::Numbers_Leafs(Node* p)
{
if(p != NULL)
{
if(p->Lchild == NULL && p->Rchild == NULL) //俺的垃圾算法
{
cout<<p->Data<<" ";
Leaf_Numbers = Leaf_Numbers + 1;
}
else
{
Numbers_Leafs(p->Lchild);
Numbers_Leafs(p->Rchild);
}
}
/*if(p != NULL) //优化算法
{
Numbers_Leafs(p->Lchild);
if(p->Lchild == NULL && p->Rchild == NULL)
{
Leaf_Numbers = Leaf_Numbers + 1;
cout<<p->Data<<" ";
}
Numbers_Leafs(p->Rchild);
}*/
/*if(p->Lchild == NULL && p->Rchild == NULL) //俺的垃圾算法
{
cout<<p->Data<<" ";
Leaf_Numbers = Leaf_Numbers + 1;
}
else
{
if(p->Lchild != NULL && p->Rchild != NULL)
{
Numbers_Leafs(p->Lchild);
Numbers_Leafs(p->Rchild);
}
if(p->Lchild != NULL && p->Rchild == NULL)
Numbers_Leafs(p->Lchild);
if(p->Lchild == NULL && p->Rchild != NULL)
Numbers_Leafs(p->Rchild);
}*/
}
void Tree::TheNumbers_Leafs()
{
Numbers_Leafs(Root);
}
int Tree::Return_LeafNums()
{
return Leaf_Numbers;
}
/*
比较两个二叉树是否相等，所以函数不能属于类当中
应声明为类外函数
*/
bool Compare(Node* p1,Node* p2)
{
if(p1 == NULL && p2 == NULL)
return true;
else
if((p1 == NULL && p2 != NULL) || (p1 != NULL && p2 == NULL))
return false;
else
if(p1->Return_Data() != p2->Return_Data())
return false;
else
/*{
bool Is_Left = Compare(p1->Return_Lchild(),p2->Return_Lchild());
bool Is_Right = Compare(p1->Return_Rchild(),p2->Return_Rchild());
if(Is_Left && Is_Right)
return true;
else
return false;
}*/
return (Compare(p1->Return_Lchild(),p2->Return_Lchild()) && Compare(p1->Return_Rchild(),p2->Return_Rchild()));
}
bool TheCompare(Tree &tree1,Tree &tree2)
{
Node* p1 = tree1.Return_Root();
Node* p2 = tree2.Return_Root();
return Compare(p1,p2);
}
void Tree::ExchangeLR(Node* p)
{
if(p->Lchild != NULL && p->Rchild != NULL)
{
Node* temp;
temp = p->Lchild;
p->Lchild = p->Rchild;
p->Rchild = temp;
ExchangeLR(p->Lchild);
ExchangeLR(p->Rchild);
}
else
{
return;
}
}
void Tree::TheExchangeLR()
{
ExchangeLR(Root);
}
void Tree::Leaf_Root(Node* p)
{
if(p != NULL)
{
Front = Front + 1; //栈顶指针加1
NodeStack[Front] = p; //进栈
Leaf_Root(p->Lchild);
Leaf_Root(p->Rchild);
}
if(NodeStack[Front]->Lchild == NULL && NodeStack[Front]->Rchild == NULL) //左右子树都为空，开始遍历
{
while(NodeStack[Front]->Rchild == NULL) //当栈顶元素的右孩子为空则它是叶子，输出
{
cout<<NodeStack[Front]->Data<<"->";
Front = Front - 1;
}
while(NodeStack[Front]->Rchild == NodeStack[Front+1] && Front != 0) //当Front = -1是程序错误
{ //从右叶子到根节点，如果利用上面的while循环，要是
cout<<NodeStack[Front]->Data<<"->"; //第一个叶子是右叶子则会重复输出，用这用判断
Front = Front - 1;
}
int temp = Front;
while(temp != Rear - 1) //把剩余的有右孩子的节点输出，栈顶指针不变
{
if(temp == 0)
cout<<NodeStack[temp]->Data;
else
cout<<NodeStack[temp]->Data<<"->";
temp = temp - 1;
}
cout<<" 路径输出完毕!"<<endl;
}
}
void Tree::TheLeaf_Root()
{
Leaf_Root(Root);
}
int main() //1 2 3 -1 -1 4 5 -1 -1 6 -1 -1 7 8 -1 -1 9 10 -1 -1 -1
{
Tree Root1;
cout<<"输入二叉树节点,(空点-1) :";
Root1.TheCreatTree();
cout<<"~~~~~~~~~~~~~~~~~~~~~~~~~"<<endl;
cout<<"先序遍历二叉树 :";
/*
1
/ \
2 7
/ \ / \
3 4 8 9
/ \ /
5 6 10
*/
Root1.TheTraveFront();cout<<endl;
cout<<"~~~~~~~~~~~~~~~~"<<endl;
cout<<"此树的叶子节为 :";
Root1.TheNumbers_Leafs();
cout<<" ,叶节点个数为:";
cout<<Root1.Return_LeafNums()<<endl;
cout<<"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"<<endl;
cout<<"请输入待比较的第二棵树的节点:";
Tree Root2;
Root2.TheCreatTree();
bool flag = TheCompare(Root1,Root2);
flag ? cout<<"∨∨这两棵树相等"<<endl : cout<<"××这两棵树不相等"<<endl;
cout<<"~~~~~~~~~~~~~~~~~~~~~~~~~"<<endl;
cout<<"Root1交换左右子树前:";
Root1.TheTraveFront();cout<<endl;
cout<<"Root1交换左右子树后:";
Root1.TheExchangeLR();
Root1.TheTraveFront();cout<<endl;
/*
1
/ \
7 2
/ \ / \
9 8 4 3
\ / \
10 6 5
1 7 9 10 8 2 4 6 5 3 这是交换后的先序遍历*/
cout<<"~~~~~~~~~~~~~~~~~~~~~~~~~"<<endl;
cout<<"Root2的叶子路径:"<<endl;
cout<<" "<<endl;
cout<<" 1 "<<endl;
cout<<" / \\ "<<endl;
cout<<" 2 7 "<<endl;
cout<<" / \\ / \\ "<<endl;
cout<<" 3 4 8 9 "<<endl;
cout<<" / \\ / "<<endl;
cout<<" 5 6 10 "<<endl;
Root2.TheLeaf_Root();
return 0;
}
参考：https://blog.csdn.net/cnm_1314/article/details/8109743
/*以二叉链表作为二叉树的存储结构:
完成 1:统计二叉树的叶结点个数.
完成 2:判别两棵树是否相等
完成 3:交换二叉树每个节点的左孩子和右孩子
4:设计二叉树的双序遍历(双序遍历就是指对于二叉树的每个节点，先访问这个节点
，再按双序遍历她的左子树，然后在访问这个节点，然后在按双序遍历它右子树 )
5:计算二叉树的最大宽度(就是所有层中结点个数最大值)
6:用按层次遍历二叉树的方法，统计树中度为1的节点数目
7:求二叉树第一条最长路径的长度，并输出次路径上个节点值
完成 8:输出二叉树中从每个叶子节点到根节点的路径
*/
void Exchange(BiTree &bt)
/* Exchange the left and right leaves of /
/ bitree whose root node is bt */
{
BiTree temp;
if(bt){
temp = bt -> lchild;
bt -> lchild = bt -> rchild;
bt -> rchild = temp;
Exchange(bt -> lchild);
Exchange(bt -> rchild);
}
}
#include
#include
#define TElemType char
typedef struct BiTNode{
TElemType data;//数据域
struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;
//创建一颗二叉树 ，以前序遍历
void CreateBiTree(BiTree T)
{
char n;
scanf("%c",&n);
if(n=='#')
*T=NULL;
else
{
*T=(BiTNode)malloc(sizeof(BiTNode));
(*T)->data=n;
CreateBiTree(&(*T)->lchild);
CreateBiTree(&(*T)->rchild);
}
}
//交换二叉树的左右结点
void ChangeLeftAndRight(BiTree T)
{
if(T != NULL)
{
//交换左右节点
BiTNode *p = T->lchild;
T->lchild = T->rchild;
T->rchild = p;
ChangeLeftAndRight(T->lchild);
ChangeLeftAndRight(T->rchild);
}
//else
// return;
}
void preOrderTtaverse(BiTree T)//遍历二叉树
{
if(T)
{
preOrderTtaverse(T->lchild);
printf("%c",T->data);
preOrderTtaverse(T->rchild);
}
}
int main() {
BiTree Tree=NULL;
CreateBiTree(&Tree);
preOrderTtaverse(Tree);//交换前中序遍历
ChangeLeftAndRight(Tree);//左右交换
printf("\n");
preOrderTtaverse(Tree);//交换后
return 0;
}