一、先序遍历序列创建二叉树

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. typedef struct node//二叉树的结构
  5. {
  6.     char data;
  7.     struct node *lchild,*rchild;
  8. }Node, *Tree;
  10. void PreCreateTree(Tree &t)//先序遍历序列创建二叉树
  11. {
  12.     char ch;
  13.     cin>>ch;
  14.     if(ch == '@')//@为特殊字符，表示空
  15.         t=NULL;
  16.     else
  17.     {
  18.         t=new node;
  19.         t->data=ch;
  20.         PreCreateTree(t->lchild);
  21.         PreCreateTree(t->rchild);
  22.     }
  23. }
  25. int main()
  26. {
  27.     Tree t=new node;
  28.     PreCreateTree(t);
  30.     return 0;
  31. }

二、遍历二叉树

1.递归写法：

  1. void PreTraverse(Tree &t)
  2. {
  3.     if(t)
  4.     {
  5.         cout<<t->data;//在这输出就是先序遍历
  6.         PreTraverse(t->lchild);
  7.         //放到这里输出就是中序遍历
  8.         PreTraverse(t->rchild);
  9.         //放到这里输出就是后序遍历
  10.     }
  11. }

2.非递归写法：

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. typedef struct node
  5. {
  6.     char data;
  7.     struct node *lchild,*rchild;
  8. }Node, *Tree;
  10. Tree stk[100];//二叉树结构的结构体指针数组
  12. void PreCreateTree(Tree &t)//先序遍历序列创建二叉树
  13. {
  14.     char ch;
  15.     cin>>ch;
  16.     if(ch == '@')
  17.         t=NULL;
  18.     else
  19.     {
  20.         t=new node;
  21.         t->data=ch;
  22.         PreCreateTree(t->lchild);
  23.         PreCreateTree(t->rchild);
  24.     }
  25. }
  27. void InoderTraverse(Tree &t)//非递归中序遍历
  28. {
  29.     int hh=-1,tt=0;//模拟栈
  30.     while(t!=NULL || hh>=tt)//当t不为空 或者 栈不为空
  31.     {
  32.         if(t!=NULL)//t不为空就把该结点压入栈，再移到左孩子
  33.         {
  34.             stk[++hh]=t;
  35.             t=t->lchild;
  36.         }
  37.         else//t为空则退栈并输出，再移到右孩子
  38.         {
  39.             t=stk[hh--];
  40.             cout<<t->data;
  41.             t=t->rchild;
  42.         }
  43.     }
  44.     cout<<endl;
  45. }
  47. int main()
  48. {
  49.     Tree t=new node;
  50.     PreCreateTree(t);
  51.     InoderTraverse(t);
  53.     return 0;
  54. }

3.按层次遍历：

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. typedef struct node
  5. {
  6.     char data;
  7.     struct node *lchild,*rchild;
  8. }Node, *Tree;
  10. Tree q[100];
  12. void PreCreateTree(Tree &t)
  13. {
  14.     char ch;
  15.     cin>>ch;
  16.     if(ch == '@')
  17.         t=NULL;
  18.     else
  19.     {
  20.         t=new node;
  21.         t->data=ch;
  22.         PreCreateTree(t->lchild);
  23.         PreCreateTree(t->rchild);
  24.     }
  25. }
  27. void LayerTraverse(Tree t)//层次遍历
  28. {
  29.     int hh=0,tt=0;//模拟对列
  30.     if(t == NULL)
  31.         return ;
  32.     else
  33.     {
  34.         q[0]=t;//根结点入队
  35.         while(hh<=tt)//当队不为空
  36.         {
  37.             t=q[hh++];//取队首并输出
  38.             cout<<t->data;
  39.             if(t->lchild!=NULL)//有左孩子就把左孩子入队
  40.                 q[++tt]=t->lchild;
  41.             if(t->rchild!=NULL)//有右孩子就把右孩子入队
  42.                 q[++tt]=t->rchild;
  43.         }
  44.     }
  45. }
  47. int main()
  48. {
  49.     Tree t=new node;
  50.     PreCreateTree(t);
  51.     LayerTraverse(t);
  53.     return 0;
  54. }

三、一些操作

1.根据森林的孩子兄弟表示法的先序序列找叶子数量：

关于树及树的基础操作 - 图1

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. typedef struct node
  5. {
  6.     char data;
  7.     struct node *lchild,*rchild;
  8. }Node,*Tree;
  10. void CreateTree(Tree &t)
  11. {
  12.     char ch;
  13.     cin>>ch;
  14.     if(ch == '@')
  15.         t=NULL;
  16.     else
  17.     {
  18.         t = new node;
  19.         t->data = ch;
  20.         CreateTree(t->lchild);
  21.         CreateTree(t->rchild);
  22.     }
  23. }
  25. int TreeLeaf(Tree &t)
  26. {
  27.     if(t == NULL)//根结点为空返回0
  28.         return 0;
  29.     if(t->lchild == NULL)//如果没有左孩子，返回1+右孩子的情况
  30.         return 1+TreeLeaf(t->rchild);
  31.     else//有左孩子，返回左孩子的情况+右孩子的情况
  32.         return TreeLeaf(t->lchild)+TreeLeaf(t->rchild);
  33. }
  35. int main()
  36. {
  37.     Tree t=new node;
  38.     CreateTree(t);
  39.     cout<<TreeLeaf(t);
  41.     return 0;
  42. }

2.找叶子：

  1. int ans=0;
  2. int PreTraverse(Tree t)
  3. {
  4.     if(t == NULL)
  5.         return ans;
  6.     else
  7.     {
  8.         if(t->lchild==NULL&& t->rchild==NULL)
  9.             ans++;
  10.         PreTraverse(t->lchild);
  11.         PreTraverse(t->rchild);
  13.     }
  14.     return ans;
  15. }

3.求二叉树的深度：

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. typedef struct node
  5. {
  6.     char data;
  7.     struct node *lchild,*rchild;
  8. }Node, *Tree;
  10. void PreCreateTree(Tree &t)
  11. {
  12.     char ch;
  13.     cin>>ch;
  14.     if(ch == '@')
  15.         t=NULL;
  16.     else
  17.     {
  18.         t=new node;
  19.         t->data=ch;
  20.         PreCreateTree(t->lchild);
  21.         PreCreateTree(t->rchild);
  22.     }
  23. }
  25. int Depth(Tree t)
  26. {
  27.     int n,m;//注意，这里的n和m不能定义在depth函数外！会出错！！！
  28.     if(t==NULL)
  29.         return 0;
  30.     else
  31.     {
  32.         m=Depth(t->lchild);
  33.         n=Depth(t->rchild);
  34.         return max(n,m)+1; //返回较大的值+1
  35.     }
  36. }
  38. int main()
  39. {
  40.     Tree t=new node;
  41.     PreCreateTree(t);
  42.     cout<<Depth(t)<<endl;
  44.     return 0;
  45. }

4.复制二叉树：

  1. void copy(Tree &t,Tree newt)
  2. {
  3.     if(t == NULL)
  4.     {
  5.         newt = NULL;
  6.         return;
  7.     }
  8.     else
  9.     {
  10.         newt = new node;
  11.         newt->data = t->data;
  12.         copy(t->lchild, newt->lchild);
  13.         copy(t->rchild, newt->rchild);
  14.     }
  15. }