树的创建和遍历

佚名 6年前 (2019-04-27) 随笔 554人围观抢沙发百度已收录

二叉树的创建

库文件和结构体定义

 1 ···
 2 #include<iostream>
 3 #include<stdlib.h>
 4 using namespace std;
 5 
 6 typedef struct Tree
 7 {
 8     int data;
 9     struct Tree* lchild;
10     struct Tree* rchild;
11 }Tree;
12 ```

前序创建二叉树

 1 ···
 2 Tree* createtree()//前序创建二叉树； 
 3 {
 4     Tree* p;
 5     int c;
 6     cin>>c;
 7 
 8     if(c==0)
 9     {
10         p=NULL;
11     }
12     else
13     {
14     
15         p=new Tree;
16         p->data=c;
17         p->lchild=createtree();
18         p->rchild=createtree();
19     }
20     return p;
21 }
22 ···

先序遍历

 1 ···
 2 void preorder(Tree *p)//先序遍历； 
 3 {
 4     if(p!=NULL)
 5     {
 6         cout<<p->data<<" ";
 7         preorder(p->lchild);
 8         preorder(p->rchild);
 9     }
10 }
11 ···

中序遍历

 1 ···
 2 void inorder(Tree *p)//中序遍历； 
 3 {
 4     if(p!=NULL)
 5     {
 6         preorder(p->lchild);
 7         cout<<p->data<<" ";
 8         preorder(p->rchild);
 9     }
10 }
11 ···

后序遍历

 1 ···
 2 void postorder(Tree *p)//后序遍历；
 3 {
 4     if(p!=NULL)
 5     {
 6         preorder(p->lchild);
 7         preorder(p->rchild);
 8         cout<<p->data<<" ";
 9     }
10     
11 } 
12 ···

主函数

 1 ···
 2 int main()
 3 {
 4     Tree* tree=NULL;
 5     cout<<"创建一个二叉树（每两个数之间用空格间断，0代表空）"<<endl;
 6     tree=createtree();
 7     cout<<"二叉树创建完成"<<endl;
 8     cout<<"前序遍历二叉树"<<endl;
 9     preorder(tree);
10     cout<<endl;
11     cout<<"中序遍历二叉树"<<endl;
12     inorder(tree);
13     cout<<endl;
14     cout<<"后序遍历二叉树"<<endl;
15     postorder(tree);
16     return 0;
17 }
18 ···