algorithm/tree/ali.cpp at master · viclab/algorithm · GitHub

History

272 lines (228 loc) · 6.46 KB

Raw

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

//二叉树遍历

//Thu Jul 17 06:40:24 PDT 2014

#include <iostream>

#include <assert.h>

#include <stack>

#include <climits>

using namespace std;

typedef struct BTreeNode {

int value;

BTreeNode *lchild;

BTreeNode *rchild;

}*BTree;

//函数：根据所给数据创建二叉排序树

BTree CreateBinaryTree(int *arr, int n);

//向二叉排序树中插入元素-递归

BTree InsertBTreeRecursion(BTree &root, int val);

//向二叉排序树中插入元素-非递归

void InsertBinaryTree(BTree *root, int val);

//函数：二叉树遍历-前序遍历

void PreOrderTraversal(BTree root);

//函数：二叉树遍历-中序遍历

void InOrderTraversal(BTree root);

//函数：二叉树遍历-后序遍历

void PostOrderTraversal(BTree root);

//函数：二叉树遍历-前序遍历(非递归方式)

void PreOrderNonrecursive(BTree root);

//函数：二叉树遍历-中序遍历(非递归方式)

void InOrderNonrecursive(BTree root);

//函数：二叉树遍历-后序遍历(非递归方式)

void PostOrderNonrecursive(BTree root);

int main()

{

int a[] = {7, 2, 8, 3, 6, 4, 5, 1};

int n = sizeof(a) / sizeof(a[0]);

BTree bt = CreateBinaryTree(a, n);

//PreOrderNonrecursive(bt);

cout << "前序遍历：";

PreOrderTraversal(bt);

cout << endl;

//cout << "中序遍历：";

//InOrderTraversal(bt);

//cout << endl;

//cout << "后序遍历：";

//PostOrderTraversal(bt);

//cout << endl;

//cout << "非递归前序：";

//PreOrderNonrecursive(bt);

//cout << endl;

//cout << "非递归中序：";

//InOrderNonrecursive(bt);

//cout << endl;

//cout << "非递归后序：";

//PostOrderNonrecursive(bt);

//cout << endl;

return 0;

}

//函数：根据所给数据创建二叉排序树

BTree CreateBinaryTree(int *arr, int n)

{

assert(arr != NULL && n > 0);

BTree root = NULL;

for (int i=0; i<n; ++i)

//InsertBinaryTree(&root, *(arr+i));

InsertBTreeRecursion(root, *(arr+i));

return root;

}

//向二叉排序树中插入元素-递归

BTree InsertBTreeRecursion(BTree &root, int val)

{

if (root == NULL) {

root = new BTreeNode;

root->value = val;

root->lchild = root->rchild = NULL;

}

else if (val < root->value)

root->lchild = InsertBTreeRecursion(root->lchild, val);

else if (val > root->value)

root->rchild = InsertBTreeRecursion(root->rchild, val);

return root;

}

//向二叉排序树中插入元素-非递归

void InsertBinaryTree(BTree *root, int val)

{

BTreeNode *newNode = new BTreeNode();

newNode->value = val;

newNode->lchild = newNode->rchild = NULL;

BTreeNode *pre, *cur;

pre = NULL;

cur = *root;

while (cur != NULL)

{

pre = cur;

if (val < cur->value)

cur = cur->lchild;

else

cur = cur->rchild;

}

if (NULL == pre)

*root = newNode;

else if (val < pre->value)

pre->lchild = newNode;

else

pre->rchild = newNode;

//下面为早先实现的一个版本，可以实现，但代码不够简介

//BTreeNode *node = new BTreeNode;

//node->value = val;

//node->lchild = node->rchild = NULL;

//if (*root == NULL)

//{

// *root = node;

// return;

//}

//BTreeNode *bp = *root;

//while (bp->value > val && bp->lchild != NULL

// || bp->value < val && bp->rchild != NULL) {

// if (bp->value > val)

// bp = bp->lchild;

// else

// bp = bp->rchild;

//}

//if (bp->value > val)

// bp->lchild = node;

//else

// bp->rchild = node;

}

//函数：二叉树遍历-前序遍历

void PreOrderTraversal(BTree root)

{

if (root != NULL)

{

cout << root->value << "\t";

PreOrderTraversal(root->lchild);

PreOrderTraversal(root->rchild);

}

//函数：二叉树遍历-中序遍历

void InOrderTraversal(BTree root)

{

if (root != NULL)

{

InOrderTraversal(root->lchild);

cout << root->value << "\t";

InOrderTraversal(root->rchild);

}

//函数：二叉树遍历-后序遍历

void PostOrderTraversal(BTree root)

{

if (root != NULL)

{

PostOrderTraversal(root->lchild);

PostOrderTraversal(root->rchild);

cout << root->value << "\t";

}

//函数：二叉树遍历-前序遍历(非递归方式)

void PreOrderNonrecursive(BTreeNode* root)

{

assert(root != NULL);

int min, max;

min = INT_MAX;

max = INT_MIN;

stack<BTreeNode *> st;

BTreeNode *pn;

st.push(root);

while (!st.empty()) {

pn = st.top();

st.pop();

//cout << pn->value << "\t";

if (pn->value > max)

max = pn->value;

if (pn->value < min);

min = pn->value;

if (pn->rchild != NULL)

st.push(pn->rchild);

if (pn->lchild != NULL)

st.push(pn->lchild);

}

cout << min << " | " << max << endl;

}

//函数：二叉树遍历-中序遍历(非递归方式)

//思路：对于任一节点P

// 1.若其左孩子不为空，则将P入栈并将P的左孩子置为当前的P，然后对P执行同样处理

// 2.若其左孩子为空，则取栈顶元素，并进行出栈操作，访问该栈顶节点，然后将P置为该节点的右孩子

// 3.直到P为NULL并且栈为空则遍历结束

void InOrderNonrecursive(BTree root)

{

//assert(root != NULL);

stack<BTreeNode *> st;

BTreeNode *pn = root;

while (pn != NULL || !st.empty()) {

while (pn != NULL) {

st.push(pn);

pn = pn->lchild;

}

if (!st.empty()) {

pn = st.top();

st.pop();

cout << pn->value << "\t";

pn = pn->rchild;

}

//函数：二叉树遍历-后序遍历(非递归方式)

//思路：对于这样的节点：

// （1）叶节点

// （2）左孩子或右孩子都已被访问过

void PostOrderNonrecursive(BTree root)

{

stack<BTreeNode *> st;

st.push(root);

BTreeNode *pn, *pre = NULL;

while (!st.empty()) {

pn = st.top();

if ((pn->lchild == NULL && pn->rchild == NULL)

|| (pre != NULL &&

(pre == pn->lchild || pre == pn->rchild))) {

cout << pn->value << "\t";

st.pop();

pre = pn;

} else {

if (pn->rchild != NULL)

st.push(pn->rchild);

if (pn->lchild != NULL)

st.push(pn->lchild);

}

algorithm/tree/ali.cpp at master · viclab/algorithm · GitHub

Expand file tree

Breadcrumbs

ali.cpp

Latest commit

History

Breadcrumbs

ali.cpp

File metadata and controls