100-1

最近ネット上に流れているマイクロソフトのアルゴリズム100題をしっかりやりたいと思っています.オリジナルではないかもしれませんが、ネット上の資料と自分の理解を統合することで、本当にこのようなことをすることができて、堅持できれば、自分にも向上すると思います.毎日1題を頑張りましょう.

/*
 ============================================================================
 Name        : 100-1.cpp
 Author      : dapengking
 Version     :
 Copyright   : Your copyright notice
 Description :
	 1.                
	   ：
	          ，                   。
	             ，        。
	 10
	 / \
	 6 14
	 / \ / \
	4 8 12 16
	        
	 4=6=8=10=12=14=16。
	                      ：
	 struct BSTreeNode
	 {
	 int m_nValue; // value of node
	 BSTreeNode *m_pLeft; // left child of node
	 BSTreeNode *m_pRight; // right child of node
	 };
 ============================================================================
 */

#include <iostream>

using namespace std;

struct BSTreeNode {
	int m_nValue;
	BSTreeNode *m_pLeft;
	BSTreeNode *m_pRight;
};

BSTreeNode *pre = NULL;
BSTreeNode head;
BSTreeNode *pHead = &head;

/**
 *        
 */
void addBSTreeNode(BSTreeNode *&pCurrent, int value) {
	if (NULL == pCurrent) {
		BSTreeNode *pNewNode = new BSTreeNode;
		pNewNode->m_nValue = value;
		pNewNode->m_pLeft = NULL;
		pNewNode->m_pRight = NULL;
		pCurrent = pNewNode;
	} else if (pCurrent->m_nValue < value) {
		addBSTreeNode(pCurrent->m_pRight, value);
	} else if (pCurrent->m_nValue > value) {
		addBSTreeNode(pCurrent->m_pLeft,value);
	} else {
		cout << "error:repeat value" << endl;
	}
}

void inOrderBSTree(BSTreeNode *pRoot){
	if(NULL != pRoot){
		inOrderBSTree(pRoot->m_pLeft);
		cout << pRoot->m_nValue << " ";
		pRoot->m_pLeft = pre;//                 
		if(NULL != pre){
			pre->m_pRight = pRoot;
		}else if(NULL == pre){
			pHead->m_pRight = pRoot;
		}
		pre = pRoot;//    
		inOrderBSTree(pRoot->m_pRight);
	}
}

/**
 *         
 *         
 */
void printList(BSTreeNode *pHead) {
	BSTreeNode *pIndex = pHead->m_pRight;
	while (NULL != pIndex) {
		cout << pIndex->m_nValue << " ";
		pIndex = pIndex->m_pRight;
	}
}

int main(void) {
	BSTreeNode *pRoot = NULL;
	addBSTreeNode(pRoot,10);
	addBSTreeNode(pRoot,6);
	addBSTreeNode(pRoot,14);
	addBSTreeNode(pRoot,4);
	addBSTreeNode(pRoot,8);
	addBSTreeNode(pRoot,12);
	addBSTreeNode(pRoot,16);
	inOrderBSTree(pRoot);
	cout << endl;
	printList(pHead);//    
	return 0;
}

多くの資料が結合されているので、引用点は説明しません.これらはすべて比較的経典の問題で、ネット上の関連資料はとても多いです.私はここでただ自分の将来の復習に役立つだけで、自分に対する促しでもあります.牛たちが私たちのためにこんなにたくさんの良い学習資料を残してくれたことに感謝します.