/* -*- Mode: C; indent-tabs-mode: t; c-basic-offset: 4; tab-width: 4 -*- */ /* * main.cc * Copyright (C) archermind 2012 <archermind@> * */ #include <iostream> using namespace std; //获取数组长度 template <class T> int getArrayLen(T& array) { return (sizeof(array) / sizeof(array[0])); } //打印数组元素 void printArrayVal(int values[],int index){ cout<< "values["<<index<<"]:"<<values[index]<<endl; } //节点 struct BSTreeNode { int m_nValue; // value of node BSTreeNode *m_pLeft; // left child of node BSTreeNode *m_pRight; // right child of node }; //添加节点到二叉树 void addNode(BSTreeNode* &pCurrentNode,int value){ if (pCurrentNode == NULL) { BSTreeNode *node = new BSTreeNode(); node->m_pLeft = NULL; node->m_pRight = NULL; node->m_nValue = value; pCurrentNode = node; }else if ((pCurrentNode->m_nValue)>value) { addNode(pCurrentNode->m_pLeft,value); }else if((pCurrentNode->m_nValue)<value){ addNode(pCurrentNode->m_pRight,value); }else { cout<<"value exist!"<<endl; } } //初始化二叉树 void initBSTree(BSTreeNode* root,int values[],int length){ for (int i=1;i< length; i++) { addNode(root,values[i]); } } //先根遍历 void preOrderTraverse(BSTreeNode* T) { if(T){ cout<<T->m_nValue<<endl; preOrderTraverse(T->m_pLeft); preOrderTraverse(T->m_pRight); } } //中根遍历 void inOrderTraverse(BSTreeNode* T) { if(T){ inOrderTraverse(T->m_pLeft); cout<<T->m_nValue<<endl; inOrderTraverse(T->m_pRight); } } //后根遍历 void postOrderTraverse(BSTreeNode* T) { if(T){ postOrderTraverse(T->m_pLeft); postOrderTraverse(T->m_pRight); cout<<T->m_nValue<<endl; } } int main(){ int vals[] = {10,4,12,6,8,14,16,15}; int length = getArrayLen(vals); BSTreeNode* root = new BSTreeNode(); root->m_pLeft = NULL; root->m_pRight = NULL; root->m_nValue = 10; initBSTree(root,vals,length); preOrderTraverse(root); inOrderTraverse(root); postOrderTraverse(root); return 0; }