二叉树的递归遍历与复制
生活随笔
收集整理的這篇文章主要介紹了
二叉树的递归遍历与复制
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
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:\n");
114 preOrder(&t1);
115 printf("\n");
116 printf("Old Tree's inOrder:\n");
117 inOrder(&t1);
118 printf("\n");
119 printf("Old Tree's posOrder:\n");
120 posOrder(&t1);
121 printf("\n");
122 printf("Old Tree:\n");
123 preOrder(&t1);
124 printf("\n");
125 BiTNode* newTree = CopyTree(&t1);
126 printf("New Tree:\n");
127 preOrder(newTree);
128
129
130 system("pause");
131 }
?
轉載于:https://www.cnblogs.com/Lxk0825/p/9519983.html
總結
以上是生活随笔為你收集整理的二叉树的递归遍历与复制的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Linux虚机安装配置Tomcat
- 下一篇： BZOJ2809 dispatching