C语言实现二叉树遍历的迭代算法

本文实例讲述了C语言实现二叉树遍历的迭代算法，是数据结构算法中非常经典的一类算法。分享给大家供大家参考。

具体实现方法如下：

二叉树中序遍历的迭代算法：

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

#include <iostream>

#include <stack>

using namespace std;

struct Node {

Node(int i, Node* l = NULL, Node* r = NULL) : item(i), left(l), right(r) {}

int item;

Node* left;

Node* right;

};

Node* construct() {

Node* node6 = new Node(16);

Node* node5 = new Node(12);

Node* node4 = new Node(8);

Node* node3 = new Node(4);

Node* node2 = new Node(14, node5, node6);

Node* node1 = new Node(6, node3, node4);

Node* node0 = new Node(10, node1, node2);

return node0;

}

//递归算法

void inorder(Node *root)

{

if (root == NULL)

return;

inorder(root->left);

cout << root->item << " ";

inorder(root->right);

}

void preorder(Node *root)

{

if(root == NULL)

return;

cout << root->item << " ";

preorder(root->left);

preorder(root->right);

}

void postorder(Node *root)

{

if (root == NULL)

return;

postorder(root->left);

postorder(root->right);

cout << root->item << " ";

}

void postorder2(Node *root)

{

if (root == NULL)

return;

stack<Node *> nstack;

Node *pre = NULL;

nstack.push(root);

Node *node = NULL;

while (!nstack.empty())

{

node = nstack.top();

if (pre != node->left && pre != node->right)

{

if (node->right)

nstack.push(node->right);

if (node->left)

nstack.push(node->left);

}

if (node->left == NULL && node->right == NULL

|| pre == node->left || pre == node->right)

{

cout << node->item << " ";

nstack.pop();

}

pre = node;

}

void preorder2(Node *root)

{

if(root == NULL)

return;

stack<Node *> nstack;

Node *node = root;

while (node != NULL || !nstack.empty())

{

while(node != NULL)

{

cout << node->item << " ";

nstack.push(node);

node = node->left;

}

node = nstack.top();

nstack.pop();

node = node->right;

}

void preorder3(Node *root)

{

if (root == NULL)

return;

stack<Node *> nstack;

nstack.push(root);

Node *node = NULL;

while (!nstack.empty())

{

node = nstack.top();

nstack.pop();

cout << node->item << " ";

if (node->right)

nstack.push(node->right);

if (node->left)

nstack.push(node->left);

}

//迭代算法

void inorder2(Node *root)

{

if(root == NULL)

return;

stack<Node *> nstack;

nstack.push(root);

Node *next = root->left;

while (next != NULL || !nstack.empty())

{

while (next != NULL)

{

nstack.push(next);

next = next->left;

}

next = nstack.top();

nstack.pop();

cout << next->item << " ";

next = next->right;

}

int main()

{

Node *root = construct();

cout << "---------中序遍历递归---------" << endl;

inorder(root);

cout << endl;

cout << "---------中序遍历迭代---------" << endl;

inorder2(root);

cout << endl;

cout << "---------先序遍历递归---------" << endl;

preorder(root);

cout << endl;

cout << "---------先序遍历迭代1---------" << endl;

preorder2(root);

cout << endl;

cout << "---------先序遍历迭代2---------" << endl;

preorder3(root);

cout << endl;

cout << "---------后序遍历递归---------" << endl;

postorder(root);

cout << endl;

cout << "---------后序遍历迭代---------" << endl;

postorder2(root);

}

关于前序遍历，后来又写的算法如下，供大家参考：

C语言实现二叉树遍历的迭代算法

相关文章

快网idc优惠网

相关文章

微信

快网idc优惠网

QQ交流群