二叉树的递归遍历与复制

  1 #include <iostream>
  2  
  3 //定义树的数据结构
  4 struct BiTNode
  5 {
  6     int data;
  7     struct BiTNode *lchild, *rchild;
  8 };
  9  
 10 typedef struct BiTNode  BiTNode;
 11 typedef struct BiTNode* BiTree;
 12  
 13  
 14 //前序遍历
 15 void preOrder(BiTNode *root)
 16 {
 17     if (root == NULL)
 18     {
 19         return;
 20     }
 21     printf("%d ", root->data);
 22     preOrder(root->lchild);
 23     preOrder(root->rchild);
 24 }
 25  
 26 //中序遍历
 27 void inOrder(BiTNode *root)
 28 {
 29     if (root == NULL)
 30     {
 31         return;
 32     }
 33     inOrder(root->lchild);
 34     printf("%d ", root->data);
 35     inOrder(root->rchild);
 36 }
 37 //后序遍历
 38 void posOrder(BiTNode *root)
 39 {
 40     if (root == NULL)
 41     {
 42         return;
 43     }
 44     posOrder(root->lchild);
 45     posOrder(root->rchild);
 46     printf("%d ", root->data);
 47 }
 48 //创建拷贝函数
 49 BiTNode* CopyTree(BiTNode *root)
 50 {
 51     BiTNode *newNode = NULL;
 52     BiTNode *newLc = NULL;
 53     BiTNode *newRc = NULL;
 54  
 55     if (root == NULL)
 56     {
 57         return NULL;
 58     }
 59     //拷贝左子树
 60     if (root->lchild != NULL)
 61     {
 62         newLc = CopyTree(root->lchild);
 63     }
 64     else
 65     {
 66         newLc = NULL;
 67     }
 68  
 69     //拷贝右子树
 70     if (root->rchild != NULL)
 71     {
 72         newRc = CopyTree(root->rchild);
 73     }
 74     else
 75     {
 76         newRc = NULL;
 77     }
 78     
 79     //创建动态内存
 80     newNode = (BiTNode * )malloc(sizeof(BiTNode));
 81     if (newNode == NULL)
 82     {
 83         return NULL;
 84     }
 85  
 86     newNode->lchild = newLc;
 87     newNode->rchild = newRc;
 88     newNode->data = root->data;
 89  
 90     return newNode;
 91 }
 92  
 93  
 94  
 95 void main()
 96 {
 97     BiTNode t1, t2, t3, t4, t5;
 98     memset(&t1, 0, sizeof(BiTNode));
 99     memset(&t2, 0, sizeof(BiTNode));
100     memset(&t3, 0, sizeof(BiTNode));
101     memset(&t4, 0, sizeof(BiTNode));
102     memset(&t5, 0, sizeof(BiTNode));
103     t1.data = 1;
104     t2.data = 2;
105     t3.data = 3;
106     t4.data = 4;
107     t5.data = 5; 
108  
109     t1.lchild = &t2;
110     t1.rchild = &t3;
111     t2.lchild = &t4;
112     t2.rchild = &t5;
113     printf("Old Tree's preOrder:
");
114     preOrder(&t1);
115     printf("
");
116     printf("Old Tree's inOrder:
");
117     inOrder(&t1);
118     printf("
");
119     printf("Old Tree's posOrder:
");
120     posOrder(&t1);
121     printf("
");
122     printf("Old Tree:
");
123     preOrder(&t1);
124     printf("
");
125     BiTNode* newTree = CopyTree(&t1);
126     printf("New Tree:
");
127     preOrder(newTree);
128  
129  
130     system("pause");
131 }