分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请点击http://www.captainbed.net
/* * 把二元查找树转变成排序的双向链表 - by Chimomo * * 【思路】按照二叉树的中序遍历正好是按从小到大地顺序遍历全部节点。在遍历的过程中，更改它的逻辑结构。 */ #include
using namespace std; / * The binary search tree node. */ struct BSTreeNode { int m_nValue; // The value of node. BSTreeNode *m_pLeft; // The left child of node. BSTreeNode *m_pRight; // The right child of node. }; typedef BSTreeNode DoublyLinkedList; DoublyLinkedList *pHead = nullptr; DoublyLinkedList *pDoublyLinkedList = nullptr; / * Construct binary search tree recursively. * @param pCurrent The current pointer. Use & here since pCurrent will be changed in the function body. * @param value The value. */ void ConstructBSTree(BSTreeNode *&pCurrent, int value) { if (pCurrent == nullptr) { auto pTree = new BSTreeNode(); pTree->m_pLeft = nullptr; pTree->m_pRight = nullptr; pTree->m_nValue = value; pCurrent = pTree; } else { if (value > pCurrent->m_nValue) { ConstructBSTree(pCurrent->m_pRight, value); } else if (value < pCurrent->m_nValue) { ConstructBSTree(pCurrent->m_pLeft, value); } else { cout << "Invalid input, there already have the value!" << endl; } } } / * Convert binary search tree node to doubly linked list node. * @param pCurrent The current pointer. */ void ConvertBSTreeNodeToDoublyLinkedListNode(BSTreeNode *pCurrent) { pCurrent->m_pLeft = pDoublyLinkedList; if (pDoublyLinkedList == nullptr) { pHead = pCurrent; } else { pDoublyLinkedList->m_pRight = pCurrent; } pDoublyLinkedList = pCurrent; } / * Traverse binary search tree (in-order) to convert binary tree to doubly linked list. * @param pCurrent The current pointer. */ void TraverseBSTreeInOrder(BSTreeNode *pCurrent) { if (pCurrent == nullptr) { return; } else { if (pCurrent->m_pLeft != nullptr) { TraverseBSTreeInOrder(pCurrent->m_pLeft); } ConvertBSTreeNodeToDoublyLinkedListNode(pCurrent); if (pCurrent->m_pRight != nullptr) { TraverseBSTreeInOrder(pCurrent->m_pRight); } } } / * Test program. * @param argc The argument count. * @param argv The argument array. * @return The int. */ int main(int argc, char *argv[]) { int value; BSTreeNode *pBSTree = nullptr; cout << "Please input integers, -1 to end:"; cin >> value; while (-1 != value) { ConstructBSTree(pBSTree, value); cin >> value; } TraverseBSTreeInOrder(pBSTree); cout << "Print BST:"; while (pHead) { cout << pHead->m_nValue << ' '; pHead = pHead->m_pRight; } return 0; } // Output: /* Please input integers, -1 to end:6 7 8 5 1 3 9 2 4 0 10 -1 6 7 8 5 1 3 9 2 4 0 10 -1 Print BST:0 1 2 3 4 5 6 7 8 9 10 */
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/208897.html原文链接：https://javaforall.net
