数据结构实验（四）二叉树的基本操作

#include<iostream>
 
using namespace std;
 
typedef struct TreeNode {
  char data;//数据域
  TreeNode* Lchild;//左孩子
  TreeNode* Rchild;//右孩子
}*Tree,TreeNode;
 
//前序创建二叉树
void CreateTree(Tree& T) {
  char x;
  cin >> x;
  if (x =='*')
  {
    T = NULL; 
  }
  else 
  {
    T = new TreeNode;//新建一个结点 
    T->data = x;
    CreateTree(T->Lchild);//生成左孩子结点 
    CreateTree(T->Rchild);//生成右孩子结点 
  }
}
//先序遍历
void Pre_Traversal(const Tree& T) {
  if (T) {
    cout << T->data<<" ";
    Pre_Traversal(T->Lchild);
    Pre_Traversal(T->Rchild);
  }
}
//中序遍历
void Ino_Traversal(const Tree& T) {
  if (T) {
    Ino_Traversal(T->Lchild);
    cout << T->data<<" ";
    Ino_Traversal(T->Rchild);
  }
}
//后序遍历
void Pos_Traversal(const Tree& T) {
  if (T) {
    Pos_Traversal(T->Lchild);
    Pos_Traversal(T->Rchild);
    cout << T->data << " ";
    
  }
}
//二叉树是否为空
bool TreeEmpty(const Tree& T) {
  if (T == NULL)
  {
    cout << "该二叉树为空！"<<endl; 
    return true;
  }
  else
  {
    cout << "该二叉树为不为空！"<<endl;
    return false;
  }
}
//求二叉树的叶子节点数
int Treeleaf_Count(const Tree& T) {
  if(T == NULL)
  {
    return 0;
  }
  if (T->Lchild == NULL && T->Rchild == NULL)
  {
    return 1;
  }
  return Treeleaf_Count(T->Lchild) + Treeleaf_Count(T->Rchild);
}
 
//交换左孩子和右孩子
void swap( Tree& T)
{
    //如果T不存在，就返回
    if(T == NULL) 
  {
    return; 
  }
    //如果T的左右子树都不存在就返回
    if(T->Lchild == NULL && T->Rchild == NULL) 
  {
    return;
  }
  //左右子树交换
  
  
  Tree tmp = T->Lchild;
    T->Lchild = T->Rchild;
    T->Rchild = tmp;
    swap(T->Lchild);
    swap(T->Rchild);
  
    
    
}
//求二叉树的深度
int TreeDepth(const Tree& T) {
  if (T == NULL) return 0;
  else {
    int i = TreeDepth(T->Lchild);
    int j = TreeDepth(T->Rchild);
    return i > j ? i + 1 : j + 1;
  }
 
}
// 递归比较两棵树是否相等
bool CompareTrees(Tree& t1, Tree& t2) {
    if (t1 && t2) {
        // 比较当前节点的值
        if (t1->data == t2->data) {
            // 递归比较左子树和右子树
            return CompareTrees(t1->Lchild, t2->Lchild) && CompareTrees(t1->Rchild, t2->Rchild);
        } else {
            return false;
        }
    } else if (!t1 && !t2) {
        // 如果都是空树，二者相同
        return true;
    } else {
        // 其他情况，二者不同
        return false;
    }
}
 
// 双序遍历：先序遍历 + 后序遍历
void DoubleOrderTraversal(Tree& root) {
    if (root) {
        // 先输出根节点
        cout << root->data << " ";
 
        // 递归遍历左子树
        DoubleOrderTraversal(root->Lchild);
 
        // 递归遍历右子树
        DoubleOrderTraversal(root->Rchild);
 
        // 再输出根节点
        cout << root->data << " ";
    }
}
int main(){
  Tree T;
  cout << "请按先序遍历的顺序创建二叉树，若其节点的左孩子或右孩子不存在则使用*代替！如：（ABC**DE*G**F***）" << endl;
  CreateTree(T);
  TreeEmpty(T);
  cout << "先序遍历的结果为：";
  Pre_Traversal(T) ;
  cout<< endl;
  cout << "中序遍历的结果为：";
  Ino_Traversal(T);
  cout << endl;
  cout << "后序遍历的结果为：";
  Pos_Traversal(T);
  cout << endl;
  cout << "该树的深度为："<< TreeDepth(T)<< endl;
  cout << "该树的叶子节点数为：" << Treeleaf_Count(T) << endl;
  swap(T);
  cout << "该先序排序的树交换左右孩子后的先序排序结果为：" <<endl;
  Pre_Traversal(T);
  cout<<"\n"<<endl; 
 
  Tree tree1;
  Tree tree2;
  cout<<"输入tree1树："<<endl; 
  CreateTree(tree1);
  cout<<"输入tree2树："<<endl; 
  CreateTree(tree2);
  
  if (CompareTrees(tree1, tree2)) 
  {
        cout << "两棵树相等" << endl;
    } else {
        cout << "两棵树不相等" << endl;
    }
    
    Tree tree3;
    cout<<"输入tree3树："<<endl; 
    CreateTree(tree3);
    // 进行双序遍历
    cout<<"tree3树双序(先+后)遍历的结果为："<<endl;
    DoubleOrderTraversal(tree3);
    cout<<"\n"<<endl;
    system("pause");
  
}