程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> C說話完成二叉樹遍歷的迭代算法

C說話完成二叉樹遍歷的迭代算法

編輯:關於C++

C說話完成二叉樹遍歷的迭代算法。本站提示廣大學習愛好者:(C說話完成二叉樹遍歷的迭代算法)文章只能為提供參考,不一定能成為您想要的結果。以下是C說話完成二叉樹遍歷的迭代算法正文


本文實例講述了C說話完成二叉樹遍歷的迭代算法,是數據構造算法中異常經典的一類算法。分享給年夜家供年夜家參考。

詳細完成辦法以下:

二叉樹中序遍歷的迭代算法:

#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);
}

關於前序遍歷,後來又寫的算法以下,供年夜家參考:

void preOrderIterator(Node *root)
{
 if (root == NULL)
 return;

 stack<Node*> nstack;
 nstack.push(root);

 while (!nstack.empty())
 {
 Node *top = nstack.top();
 while (top != NULL)
 {
  if (top->left)
  nstack.push(top->left);
  cout << top->data << " ";
  top = top->left;
 }
 while (top == NULL && !nstack.empty())
 {
  top = nstack.top()->right;
  nstack.pop();
 }

 if (top != NULL)
  nstack.push(top);
 }
}

信任本文所述對年夜家C法式算法設計的進修有必定的自創價值。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved