说明:源码来自作者:http://my.csdn.net/monsion 转载请联系作者!!!
main.cpp
#include "binaryTree.h" using namespace std; int main() { // int a[]={8,6,10,5,7,9,11}; //以-1标示空节点 int a[]={8,8,7,9,2,-1,-1,-1,-1,4,7}; binaryTree test; binaryTreeNode * root; root = test.initBTree(a,0,11); // test.preOrderTraverse(root);//递归版本 test.preOrderTraverse(root,true);//非递归版本 cout << "===========" << endl; // test.inOrderTraverse(root);//递归版本 test.inOrderTraverse(root,true);//非递归版本 cout << "===========" << endl; // test.postOrderTraverse(root);//递归版本 test.postOrderTraverse(root,true);//非递归版本 cout << "===========" << endl; test.levelOrderTraverse(root); return 0; }
binaryTree.h
#ifndef BINARY_TREE_H_H_H___ #define BINARY_TREE_H_H_H___ #include <iostream> #include <string> #include <stack> #include <queue> using namespace std; struct binaryTreeNode { int value; binaryTreeNode *pLeft; binaryTreeNode *pRight; }; class binaryTree { public: binaryTreeNode * initBTree(int a[],int i,int n); //以下三个函数为递归版本 void preOrderTraverse(binaryTreeNode * root); void inOrderTraverse(binaryTreeNode * root); void postOrderTraverse(binaryTreeNode * root); //以下三个版本为非递归版本,第二个参数为重载用,无意义 void preOrderTraverse(binaryTreeNode * root,bool type); void inOrderTraverse(binaryTreeNode * root,bool type); void postOrderTraverse(binaryTreeNode * root,bool type); //层次遍历 void levelOrderTraverse(binaryTreeNode * root); }; #endif
binaryTree.cpp
#include "binaryTree.h" using namespace std; //初始化二叉树 binaryTreeNode * binaryTree::initBTree(int a[],int i,int n) { //以-1标示空节点 if (i>=n || a[i]==-1) return NULL; binaryTreeNode * root = new binaryTreeNode(); root->value = a[i]; root->pLeft = initBTree(a,2*i+1,n); root->pRight = initBTree(a,2*i+2,n); return root; } //先序遍历,递归版本 void binaryTree::preOrderTraverse(binaryTreeNode * root) { if (root==NULL) return ; cout << root->value << endl; preOrderTraverse(root->pLeft); preOrderTraverse(root->pRight); } //先序遍历,非递归版本 void binaryTree::preOrderTraverse(binaryTreeNode * root,bool type) { if (root==NULL) return ; stack<binaryTreeNode *> treeStack; treeStack.push(root); while(!treeStack.empty()) { binaryTreeNode * node = treeStack.top(); treeStack.pop(); cout << node->value << endl; if (node->pRight!=NULL) treeStack.push(node->pRight); if (node->pLeft!=NULL) treeStack.push(node->pLeft); } } //中序遍历,递归版本 void binaryTree::inOrderTraverse(binaryTreeNode *root) { if (root==NULL) return ; if(root->pLeft!=NULL) { inOrderTraverse(root->pLeft); } cout << root->value << endl; if(root->pRight!=NULL) { inOrderTraverse(root->pRight); } } //中序遍历,非递归版本 void binaryTree::inOrderTraverse(binaryTreeNode * root,bool type) { if (root==NULL) return ; stack<binaryTreeNode *> treeStack; treeStack.push(root); binaryTreeNode * node = root; while(!treeStack.empty()) { while(node->pLeft!=NULL) { treeStack.push(node->pLeft); node = node->pLeft; } node=treeStack.top(); treeStack.pop(); cout << node->value << endl; if(node->pRight!=NULL) { treeStack.push(node->pRight); node = node->pRight; } } } //后序遍历,递归版本 void binaryTree::postOrderTraverse(binaryTreeNode *root) { if (root==NULL) return ; if(root->pLeft!=NULL) { postOrderTraverse(root->pLeft); } if(root->pRight!=NULL) { postOrderTraverse(root->pRight); } cout << root->value << endl; } //后序遍历,非递归版本 void binaryTree::postOrderTraverse(binaryTreeNode * root,bool type) { if (root==NULL) return; stack<binaryTreeNode *> treeStack; stack<binaryTreeNode *> output; treeStack.push(root); binaryTreeNode *node = NULL; while(!treeStack.empty()) { node=treeStack.top(); treeStack.pop(); output.push(node); if(node->pLeft) treeStack.push(node->pLeft); if(node->pRight) treeStack.push(node->pRight); } while(!output.empty()) { node = output.top(); output.pop(); cout << node->value << endl; } } //层次遍历 void binaryTree::levelOrderTraverse(binaryTreeNode *root) { if(root==NULL) return; queue<binaryTreeNode *> treeQueue; treeQueue.push(root); binaryTreeNode * node; while(!treeQueue.empty()) { node = treeQueue.front(); treeQueue.pop(); cout << node->value << endl; if (node->pLeft) treeQueue.push(node->pLeft); if (node->pRight) treeQueue.push(node->pRight); } }