精华内容
下载资源
问答
  • 利用递归,构造二叉查找树, ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 给一个升序的单向链表,把他转换成一个二叉查找树 ++++++++++++++++++++++++++++++++++++++...

    利用递归,构造二叉查找树,

     

    ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

    给一个升序的单向链表,把他转换成一个二叉查找树

    ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

    Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST. 

    ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
    test.cpp
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
     
    #include <iostream>
    #include <cstdio>
    #include <cstdlib>
    #include <stack>
    #include <vector>
    #include "BinaryTree.h"
    #include "List.h"

    using namespace std;


    /**
     * Definition for binary tree
     * struct TreeNode {
     * int val;
     * TreeNode *left;
     * TreeNode *right;
     * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */

    void findmid(ListNode *head, ListNode *end, ListNode *&mid)
    {

        if(head == NULL)
        {
            mid = NULL;
            return;
        }
        if(head->next == end)
        {
            mid = head;
            return;
        }
        /*pre就是传说中的快马*/
        ListNode *pre = head;
        mid = head;
        while(pre->next != end)
        {
            pre = pre->next;
            if(pre->next != end)
            {
                pre = pre->next;
            }
            else
            {
                break;
            }
            mid = mid->next;
        }

    }

    TreeNode *tobst(ListNode *head, ListNode *tail)
    {

        if(head == tail)
        {
            return NULL;
        }
        if(head->next == tail)
        {
            int val = head->val;
            delete head;
            return new TreeNode(val);
        }
        ListNode *mid;
        findmid(head, tail, mid);
        TreeNode *tmp = new TreeNode(mid->val);
        tmp->left = tobst(head, mid);
        if(mid->next)
        {
            tmp->right = tobst(mid->next, tail);
        }
        delete mid;
        return tmp;
    }

    TreeNode *sortedListToBST(ListNode *head)
    {

        if(head == NULL)
        {
            return NULL;
        }
        return tobst(head, NULL);

    }


    vector<vector<int> > levelOrder(TreeNode *root)
    {

        vector<vector<int> > matrix;
        if(root == NULL)
        {
            return matrix;
        }
        vector<int> temp;
        temp.push_back(root->val);
        matrix.push_back(temp);

        vector<TreeNode *> path;
        path.push_back(root);

        int count = 1;
        while(!path.empty())
        {
            TreeNode *tn = path.front();
            if(tn->left)
            {
                path.push_back(tn->left);
            }
            if(tn->right)
            {
                path.push_back(tn->right);
            }
            path.erase(path.begin());
            count--;

            if(count == 0)
            {
                vector<int> tmp;
                vector<TreeNode *>::iterator it = path.begin();
                for(; it != path.end(); ++it)
                {
                    tmp.push_back((*it)->val);
                }
                if(tmp.size() > 0)
                {
                    matrix.push_back(tmp);
                }
                count = path.size();
            }
        }
        return matrix;
    }



    // 树中结点含有分叉,
    //                  4
    //              /       \
    //             2         6
    //           /   \      /  \
    //          1     3    5    7
    int main()
    {

        ListNode *pListNode1 = CreateListNode(1);
        ListNode *pListNode2 = CreateListNode(2);
        ListNode *pListNode3 = CreateListNode(3);
        ListNode *pListNode4 = CreateListNode(4);
        ListNode *pListNode5 = CreateListNode(5);
        ListNode *pListNode6 = CreateListNode(6);
        ListNode *pListNode7 = CreateListNode(7);


        ConnectListNodes(pListNode1, pListNode2);
        ConnectListNodes(pListNode2, pListNode3);
        ConnectListNodes(pListNode3, pListNode4);
        ConnectListNodes(pListNode4, pListNode5);
        ConnectListNodes(pListNode5, pListNode6);
        ConnectListNodes(pListNode6, pListNode7);

        TreeNode *root = sortedListToBST(pListNode1);

        vector<vector<int> > ans = levelOrder(root);

        for (int i = 0; i < ans.size(); ++i)
        {
            for (int j = 0; j < ans[i].size(); ++j)
            {
                cout << ans[i][j] << " ";
            }
        }
        cout << endl;
        DestroyTree(root);
        return 0;
    }
    输出结果:
    4 2 6 1 3 5 7
    
    List.h:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
     
    #ifndef _LIST_H_
    #define _LIST_H_

    #include <cstdlib>

    struct ListNode
    {
        int val;
        ListNode *next;
        ListNode(int x) : val(x), next(NULL) {}
    };

    ListNode *CreateListNode(int value);
    void ConnectListNodes(ListNode *pCurrent, ListNode *pNext);
    void PrintListNode(ListNode *pNode);
    void PrintList(ListNode *pHead);
    void DestroyList(ListNode *pHead);
    void AddToTail(ListNode **pHead, int value);
    void RemoveNode(ListNode **pHead, int value);

    #endif //_LIST_H_
    List.cpp:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
     
    #include "List.h"
    #include <cstdio>
    #include <cstdlib>

    ListNode *CreateListNode(int value)
    {
        ListNode *pNode = new ListNode(0);
        pNode->val = value;
        pNode->next = NULL;

        return pNode;
    }

    void ConnectListNodes(ListNode *pCurrent, ListNode *pNext)
    {
        if(pCurrent == NULL)
        {
            printf("Error to connect two nodes.\n");
            exit(1);
        }

        pCurrent->next = pNext;
    }

    void PrintListNode(ListNode *pNode)
    {
        if(pNode == NULL)
        {
            printf("The node is NULL\n");
        }
        else
        {
            printf("The key in node is %d.\n", pNode->val);
        }
    }

    void PrintList(ListNode *pHead)
    {
        printf("PrintList starts.\n");

        ListNode *pNode = pHead;
        while(pNode != NULL)
        {
            printf("%d\t", pNode->val);
            pNode = pNode->next;
        }

        printf("\nPrintList ends.\n");
    }

    void DestroyList(ListNode *pHead)
    {
        ListNode *pNode = pHead;
        while(pNode != NULL)
        {
            pHead = pHead->next;
            delete pNode;
            pNode = pHead;
        }
    }

    void AddToTail(ListNode **pHead, int value)
    {
        ListNode *pNew = new ListNode(0);
        pNew->val = value;
        pNew->next = NULL;

        if(*pHead == NULL)
        {
            *pHead = pNew;
        }
        else
        {
            ListNode *pNode = *pHead;
            while(pNode->next != NULL)
                pNode = pNode->next;

            pNode->next = pNew;
        }
    }

    void RemoveNode(ListNode **pHead, int value)
    {
        if(pHead == NULL || *pHead == NULL)
            return;

        ListNode *pToBeDeleted = NULL;
        if((*pHead)->val == value)
        {
            pToBeDeleted = *pHead;
            *pHead = (*pHead)->next;
        }
        else
        {
            ListNode *pNode = *pHead;
            while(pNode->next != NULL && pNode->next->val != value)
                pNode = pNode->next;

            if(pNode->next != NULL && pNode->next->val == value)
            {
                pToBeDeleted = pNode->next;
                pNode->next = pNode->next->next;
            }
        }

        if(pToBeDeleted != NULL)
        {
            delete pToBeDeleted;
            pToBeDeleted = NULL;
        }
    }
    BinaryTree.h:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
     
    #ifndef _BINARY_TREE_H_
    #define _BINARY_TREE_H_

    struct TreeNode
    {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };


    TreeNode *CreateBinaryTreeNode(int value);
    void ConnectTreeNodes(TreeNode *pParent,
                          TreeNode *pLeft, TreeNode *pRight);
    void PrintTreeNode(TreeNode *pNode);
    void PrintTree(TreeNode *pRoot);
    void DestroyTree(TreeNode *pRoot);


    #endif /*_BINARY_TREE_H_*/
    BinaryTree.cpp:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
     
    #include <iostream>
    #include <cstdio>
    #include "BinaryTree.h"

    using namespace std;

    /**
     * Definition for binary tree
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */


    //创建结点
    TreeNode *CreateBinaryTreeNode(int value)
    {
        TreeNode *pNode = new TreeNode(value);

        return pNode;
    }

    //连接结点
    void ConnectTreeNodes(TreeNode *pParent, TreeNode *pLeft, TreeNode *pRight)
    {
        if(pParent != NULL)
        {
            pParent->left = pLeft;
            pParent->right = pRight;
        }
    }

    //打印节点内容以及左右子结点内容
    void PrintTreeNode(TreeNode *pNode)
    {
        if(pNode != NULL)
        {
            printf("value of this node is: %d\n", pNode->val);

            if(pNode->left != NULL)
                printf("value of its left child is: %d.\n", pNode->left->val);
            else
                printf("left child is null.\n");

            if(pNode->right != NULL)
                printf("value of its right child is: %d.\n", pNode->right->val);
            else
                printf("right child is null.\n");
        }
        else
        {
            printf("this node is null.\n");
        }

        printf("\n");
    }

    //前序遍历递归方法打印结点内容
    void PrintTree(TreeNode *pRoot)
    {
        PrintTreeNode(pRoot);

        if(pRoot != NULL)
        {
            if(pRoot->left != NULL)
                PrintTree(pRoot->left);

            if(pRoot->right != NULL)
                PrintTree(pRoot->right);
        }
    }

    void DestroyTree(TreeNode *pRoot)
    {
        if(pRoot != NULL)
        {
            TreeNode *pLeft = pRoot->left;
            TreeNode *pRight = pRoot->right;

            delete pRoot;
            pRoot = NULL;

            DestroyTree(pLeft);
            DestroyTree(pRight);
        }
    }
     
     
     

     
     

    转载于:https://www.cnblogs.com/codemylife/p/3652371.html

    展开全文
  • 二叉查找树通俗说就是左孩子比父亲小,右孩子比父亲大。构造这么一个树,树嘛,递归即可。  例如一棵树后序遍历是这样(下图的树):2 9 8 16 15 10 25 38 45 42 30 20。最后的20肯定是树根,这里要抓住一个规律:...

      二叉查找树通俗说就是左孩子比父亲小,右孩子比父亲大。构造这么一个树,树嘛,递归即可。

      例如一棵树后序遍历是这样(下图的树):2 9 8 16 15 10 25 38 45 42 30 20。最后的20肯定是树根,这里要抓住一个规律:20是树根,那么2 9 8 16 15 10都是左子树,25 38 42 45 30在右子树,因为左边都小于根、右边都大于根嘛。然后递归即可。

      下面是树的样子和代码和src.txt(后序遍历的结果)以及运行结果:

     1 #include <iostream>
     2 #include <vector>
     3 #include <fstream>
     4 
     5 using std::cin;
     6 using std::cout;
     7 using std::endl;
     8 using std::vector;
     9 
    10 #define MY_DEBUG
    11 
    12 struct Node
    13 {
    14     int data;
    15     Node* pLC;
    16     Node* pRC;
    17 };
    18 
    19 Node* creatBSTree(vector<int>& arr)
    20 {
    21     //数组里面没有元素
    22     if (!arr.size())
    23         return nullptr;
    24 
    25     Node* pNode = new Node;
    26     int thisData = arr.back();
    27     pNode->data = thisData;
    28 
    29     //只有一个元素就不要折腾了,它就是叶子节点,它没有左右孩子
    30     if (1 == arr.size())
    31     {
    32         pNode->pLC = pNode->pRC = nullptr;
    33         return pNode;
    34     }
    35 
    36     //下面找出左半边
    37     vector<int> arrLeft;
    38     for (int i = 0; i < arr.size() - 1; i++)
    39     {
    40         if (arr[i] < thisData)
    41             arrLeft.push_back(arr[i]);
    42         else
    43             break;
    44     }
    45 
    46     //下面找出右半边
    47     vector<int> arrRight;
    48     for (int i = arrLeft.size(); i < arr.size() - 1; i++)
    49         arrRight.push_back(arr[i]);
    50 
    51 #ifdef MY_DEBUG
    52     for (int i = 0; i < arrLeft.size(); i++)
    53         cout << arrLeft[i] << " ";
    54     cout << endl;
    55 
    56     for (int i = 0; i < arrRight.size(); i++)
    57         cout << arrRight[i] << " ";
    58     cout << endl << endl;
    59 #endif
    60 
    61     //递归处理左右孩子。arrLeft和arrRight可能为空,不要紧,在函数的开头处理了
    62     pNode->pLC = creatBSTree(arrLeft);
    63     pNode->pRC = creatBSTree(arrRight);
    64 
    65     return pNode;
    66 }
    67 
    68 
    69 //中序遍历
    70 void show(Node* pNode)
    71 {
    72     if (!pNode)
    73         return;
    74 
    75     show(pNode->pLC);
    76     cout << pNode->data << "  ";
    77     show(pNode->pRC);
    78 }
    79 
    80 int main(void)
    81 {
    82     vector<int> arr;
    83     std::ifstream fin("src.txt");
    84 
    85     int temp;
    86     while (fin >> temp)
    87         arr.push_back(temp);
    88 
    89     Node* pHead = creatBSTree(arr);
    90     show(pHead);
    91     cout << endl;
    92     cin.get();
    93 }
    View Code
    2 9 8 16 15 10 25 38 45 42 30 20

      由其他的遍历方式得到树的道理类似。




     

    题目:

      输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true,否则返回false。

    分析:

      这不是很简单了嘛,由最后的根把输入分成三份,第一份是左孩子,第二份是右孩子,最后是树根。7、4、6、5就不能构成了,因为5是根,那么7,4,6都是右子树里面的,但是里面有小于5的4,所以不行。递归即可。




     

    题目:

      输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点,只调整指针的指向。

      例如如果树如上图,那么得到的链表是 2=8=9=……=42=45。

    分析:

      树嘛,递归就是啦。

      如上树,先递归处理左子树(根为10的树),处理完左子树就成了一个链表了,并要能够返回左子树的最大节点16;然后递归处理右子树(根为30的树),处理完右子树也成了一个有序链表,并返回右子树的最小节点25,然后把16、20、25串起来,不就是链表了嘛?

      这里要注意一点:在处理根为20的树时,这是不是要递归处理根为10的左子树嘛,那么这个左子树怎么知道它要返回16节点呢?同样对于20的右子树,它怎么知道返回25以和20串起来呢?所以在处理子树的时候,要传给它一个标志,表明它是父亲的左子树还是右子树。我在这里纠结好久……

    代码:

      1 #include <iostream>
      2 #include <set>
      3 #include <fstream>
      4 #include <queue>
      5 
      6 using std::cin;
      7 using std::cout;
      8 using std::endl;
      9 using std::set;
     10 using std::vector;
     11 
     12 struct Node
     13 {
     14     int data;
     15     Node* pLC;
     16     Node* pRC;
     17 };
     18 
     19 Node* creatBSTree(vector<int>& arr)
     20 {
     21     //数组里面没有元素
     22     if (!arr.size())
     23         return nullptr;
     24 
     25     Node* pNode = new Node;
     26     int thisData = arr.back();
     27     pNode->data = thisData;
     28 
     29     //只有一个元素就不要折腾了,它就是叶子节点,它没有左右孩子
     30     if (1 == arr.size())
     31     {
     32         pNode->pLC = pNode->pRC = nullptr;
     33         return pNode;
     34     }
     35 
     36     //下面找出左半边
     37     vector<int> arrLeft;
     38     for (int i = 0; i < arr.size() - 1; i++)
     39     {
     40         if (arr[i] < thisData)
     41             arrLeft.push_back(arr[i]);
     42         else
     43             break;
     44     }
     45 
     46     //下面找出右半边
     47     vector<int> arrRight;
     48     for (int i = arrLeft.size(); i < arr.size() - 1; i++)
     49         arrRight.push_back(arr[i]);
     50 
     51 #ifdef MY_DEBUG
     52     for (int i = 0; i < arrLeft.size(); i++)
     53         cout << arrLeft[i] << " ";
     54     cout << endl;
     55 
     56     for (int i = 0; i < arrRight.size(); i++)
     57         cout << arrRight[i] << " ";
     58     cout << endl << endl;
     59 #endif
     60 
     61     //递归处理左右孩子。arrLeft和arrRight可能为空,不要紧,在函数的开头处理了
     62     pNode->pLC = creatBSTree(arrLeft);
     63     pNode->pRC = creatBSTree(arrRight);
     64 
     65     return pNode;
     66 }
     67 
     68 //中序遍历
     69 void show(Node* pNode)
     70 {
     71     if (!pNode)
     72         return;
     73 
     74     show(pNode->pLC);
     75     cout << pNode->data << " ";
     76     show(pNode->pRC);
     77 }
     78 
     79 //这个函数多传了一个参数 asLeft,表明树根是树根的左子树还是右子树
     80 //因为如果是左子树的话,那么要返回左子树最大节点,右子树要返回最小节点
     81 //不要这个标志的话 pNode 不知道指向的树到底是父亲的左子树还是右子树
     82 Node* letStraight(Node* pNode, bool asLeft)
     83 {
     84     //如果是空树或者只是一个叶子节点,返回自身
     85     if (!pNode || (!pNode->pLC && !pNode->pRC))
     86         return pNode;
     87 
     88     //递归处理左右子树
     89     Node* pLMax = nullptr;
     90     if (pNode->pLC)
     91         pLMax = letStraight(pNode->pLC, true);
     92 
     93     Node* pRMin = nullptr;
     94     if (pNode->pRC)
     95         pRMin = letStraight(pNode->pRC, false);
     96 
     97     //连接左子树、右子树、树根
     98     if (pLMax)
     99     {
    100         pNode->pLC = pLMax;
    101         pLMax->pRC = pNode;
    102     }
    103     if (pRMin)
    104     {
    105         pNode->pRC = pRMin;
    106         pRMin->pLC = pNode;
    107     }
    108 
    109     //返回值处理,注意 asLeft 表明这棵树是它父亲的左子树还是右子树,所以它要重新找到合适的返回节点
    110     // pNode 的左孩子最大或右孩子最小并不是它要返回的值,它要返回的还是要看这整棵树,而不是单单看左右孩子
    111     Node* pRetutnNode = pNode;
    112     if (asLeft)
    113     {
    114         while (pRetutnNode->pRC)
    115             pRetutnNode = pRetutnNode->pRC;
    116     } 
    117     else
    118     {
    119         while (pRetutnNode->pLC)
    120             pRetutnNode = pRetutnNode->pLC;
    121     }
    122     return pRetutnNode;
    123 }
    124 
    125 int main(void)
    126 {
    127     vector<int> arr;
    128     std::ifstream fin("src.txt");
    129 
    130     int temp;
    131     while (fin >> temp)
    132         arr.push_back(temp);
    133 
    134     Node* pHead = creatBSTree(arr);
    135     show(pHead);
    136     cout << endl;
    137 
    138     //顺序链表化并返回第一个节点
    139     pHead = letStraight(pHead, false);
    140     while (pHead)
    141     {
    142         cout << pHead->data << " ";
    143         pHead = pHead->pRC;
    144     }
    145     cout << endl;
    146 
    147     cin.get();
    148 }
    View Code

    结果:

    转载于:https://www.cnblogs.com/jiayith/p/3935895.html

    展开全文
  • 构造二叉查找树package binary_tree;public class BuildBinarySearchTree { private Node root; public BuildBinarySearchTree(){ root=null; } public void insert(int data){ Node newNode=n

    构造二叉查找树

    package binary_tree;
    
    public class BuildBinarySearchTree {
    
        private Node root;
    
        public BuildBinarySearchTree(){
            root=null;
        }
    
        public void insert(int data){
            Node newNode=new Node(data);
            if(root==null){
                root=newNode;
            }else{
                Node current=root;
                Node parent=root;
                while(true){
                    parent=current;
                    if(newNode.value<current.value){
                        current=current.left;
                        if(current==null){
                            parent.left=newNode;
                            return;
                        }
                    }else{
                        current=current.right;
                        if(current==null){
                            parent.right=newNode;
                            return;
                        }
                    }
                }
            }
    
        }
    
        public void buildTree(int[] data){
            for(int i=0;i<data.length;i++){
                insert(data[i]);
            }
        }
    
    
        public void inOrder(Node node){
            if(node!=null){
                inOrder(node.left);
                System.out.print(node.value+" ");
                inOrder(node.right);
            }
        }
    
        /**
         * @param args
         */
        public static void main(String[] args) {
            BuildBinarySearchTree BT=new BuildBinarySearchTree();
            int[] data={2,8,7,4,9,3,1,6,7,5};
            BT.buildTree(data);
            BT.inOrder(BT.root);
        }
    
    
        class Node{
            int value;
            Node left;
            Node right;
    
            public Node(int data){
                this.value=data;
                this.left=null;
                this.right=null;
            }
        }
    
    }
    
    展开全文
  • +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++...给定一个升序的数组,把他转换成一个高度平衡的二叉查找树 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++...

    ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

    给定一个升序的数组,把他转换成一个高度平衡的二叉查找树

    ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

    Given an array where elements are sorted in ascending order, convert it to a height balanced BST. 

    ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
    递归的方法:
    test.cpp:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
     
    #include <iostream>
    #include <cstdio>
    #include <stack>
    #include <vector>
    #include "BinaryTree.h"

    using namespace std;


    /**
     * Definition for binary tree
     * struct TreeNode {
     * int val;
     * TreeNode *left;
     * TreeNode *right;
     * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */

    TreeNode *tobst(vector<int> num, int begin, int end)
    {

        if(begin > end)
        {
            return NULL;
        }
        if(begin == end)
        {
            return new TreeNode(num[begin]);
        }
        int mid = begin + (end - begin) / 2;
        TreeNode *tmp = new TreeNode(num[mid]);
        tmp->left = tobst(num, begin, mid - 1);
        tmp->right = tobst(num, mid + 1, end);
        return tmp;
    }

    TreeNode *sortedArrayToBST(vector<int> &num)
    {
        return tobst(num, 0, num.size() - 1);
    }


    vector<vector<int> > levelOrder(TreeNode *root)
    {

        vector<vector<int> > matrix;
        if(root == NULL)
        {
            return matrix;
        }
        vector<int> temp;
        temp.push_back(root->val);
        matrix.push_back(temp);

        vector<TreeNode *> path;
        path.push_back(root);

        int count = 1;
        while(!path.empty())
        {
            TreeNode *tn = path.front();
            if(tn->left)
            {
                path.push_back(tn->left);
            }
            if(tn->right)
            {
                path.push_back(tn->right);
            }
            path.erase(path.begin());
            count--;

            if(count == 0)
            {
                vector<int> tmp;
                vector<TreeNode *>::iterator it = path.begin();
                for(; it != path.end(); ++it)
                {
                    tmp.push_back((*it)->val);
                }
                if(tmp.size() > 0)
                {
                    matrix.push_back(tmp);
                }
                count = path.size();
            }
        }
        return matrix;
    }



    // 树中结点含有分叉,
    //                  4
    //              /       \
    //             2         6
    //           /   \      /  \
    //          1     3    5    7
    int main()
    {
        int arr[7] = {1234567};
        vector<int> num(arr, arr + 7);

        TreeNode *root = sortedArrayToBST(num);

        vector<vector<int> > ans = levelOrder(root);

        for (int i = 0; i < ans.size(); ++i)
        {
            for (int j = 0; j < ans[i].size(); ++j)
            {
                cout << ans[i][j] << " ";
            }
        }
        cout << endl;
        DestroyTree(root);
        return 0;
    }
    结果输出:
    4 2 6 1 3 5 7
    
    BinaryTree.h:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
     
    #ifndef _BINARY_TREE_H_
    #define _BINARY_TREE_H_

    struct TreeNode
    {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };


    TreeNode *CreateBinaryTreeNode(int value);
    void ConnectTreeNodes(TreeNode *pParent,
                          TreeNode *pLeft, TreeNode *pRight);
    void PrintTreeNode(TreeNode *pNode);
    void PrintTree(TreeNode *pRoot);
    void DestroyTree(TreeNode *pRoot);


    #endif /*_BINARY_TREE_H_*/
    BinaryTree.cpp:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
     
    #include <iostream>
    #include <cstdio>
    #include "BinaryTree.h"

    using namespace std;

    /**
     * Definition for binary tree
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */


    //创建结点
    TreeNode *CreateBinaryTreeNode(int value)
    {
        TreeNode *pNode = new TreeNode(value);

        return pNode;
    }

    //连接结点
    void ConnectTreeNodes(TreeNode *pParent, TreeNode *pLeft, TreeNode *pRight)
    {
        if(pParent != NULL)
        {
            pParent->left = pLeft;
            pParent->right = pRight;
        }
    }

    //打印节点内容以及左右子结点内容
    void PrintTreeNode(TreeNode *pNode)
    {
        if(pNode != NULL)
        {
            printf("value of this node is: %d\n", pNode->val);

            if(pNode->left != NULL)
                printf("value of its left child is: %d.\n", pNode->left->val);
            else
                printf("left child is null.\n");

            if(pNode->right != NULL)
                printf("value of its right child is: %d.\n", pNode->right->val);
            else
                printf("right child is null.\n");
        }
        else
        {
            printf("this node is null.\n");
        }

        printf("\n");
    }

    //前序遍历递归方法打印结点内容
    void PrintTree(TreeNode *pRoot)
    {
        PrintTreeNode(pRoot);

        if(pRoot != NULL)
        {
            if(pRoot->left != NULL)
                PrintTree(pRoot->left);

            if(pRoot->right != NULL)
                PrintTree(pRoot->right);
        }
    }

    void DestroyTree(TreeNode *pRoot)
    {
        if(pRoot != NULL)
        {
            TreeNode *pLeft = pRoot->left;
            TreeNode *pRight = pRoot->right;

            delete pRoot;
            pRoot = NULL;

            DestroyTree(pLeft);
            DestroyTree(pRight);
        }
    }
     
     
     


    转载于:https://www.cnblogs.com/codemylife/p/3652368.html

    展开全文
  • 构造二叉查找树(Java实现)

    千次阅读 2018-09-18 21:02:01
    一颗二叉查找树(BST)是一颗二叉树,每个结点的键都大于其左子树中的任意结点而小于右子树的任意结点,在Java实现中每个结点都含有一个Comparable的键(以及相关联的值)。 二叉查找树类似于快速排序,跟结点就是...
  • 我写的非递归构造二叉查找树的算法#include;#include;typedef struct Search_Tree{ int key; struct Search_Tree *right; struct Search_Tree *left;}Search_Node;Search_Node* Build_SearchTree(int n){int i;...
  • 将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索。 本题中,一个高度平衡二叉树是指一个...解题思路: 构造二叉平衡,由于数组是有序的,所以最简单的方法就是用数组的中间元素作为根节点,左半...
  • 将有序数组转换为二叉搜索 【easy】 给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索。 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过...
  • 1064Complete Binary Search Tree(30分) A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties: The left subtree of a node contains only nodes with key.....
  • [LeetCode] Convert Sorted Array to Binary Search Tree 将有序数组转为二叉搜索 Given an array where elements are sorted in ascending order, convert it to a height balanced BST. For this problem, a...
  • 问题:Given a singly linked list...思路:二叉查找树构造往往伴随着二分查找的过程。这是一个单链表而不是数组。二分查找不好用。就用递归吧。每次找到链表的最中间结点, 作为树根节点,左右两侧作为左右孩子。 代
  • 题目所给序列放入数组origin,放入的同时构造二叉查找树和其镜像树,然后分别进行前序遍历,将遍历结果分别放入数组pre和mpre。当pre和origin相等时输出YES,然后后序遍历这棵树,输出后序序列;mpre和origin相等时...
  • 题目源自于leetcode。 题目:Given an array where elements are sorted in ascending order, convert it to a height ...把正中间的数作为树根,然后左和右两半段作为左子树和右子。 代码: /** * Definit
  • 二叉查找树

    2019-10-30 23:14:08
    文章目录二叉查找树(二叉搜索树、二叉排序树)构造二叉查找树二叉查找树查找结点二叉查找树插入结点二叉查找树删除结点删除叶子结点删除只有左子树的结点删除只有右子树的结点删除同时有左右子树结点删除结点代码实现...
  • 因此我们在构造二叉查找树的查找算法的时候总是用要查找的数来和节点的值做一个比较,如果节点的值大于要查找的数,那么继续查找其左节点,反之则继续查找器右节点,一直到查找到你要的数。 本算法包括计算树的高度...
  • 二叉排序树(二叉查找树)--查找 注:构造一棵二叉排序树的目的,其实并不是为了排序(中序遍历),而是为了提高查找、插入、删除关键字的速度。定义 二叉排序树又叫二叉查找树,英文名称是:Binary Sort Tree.BST的定义...
  • 运用c语言,贪心算法构造最优二叉查找树
  • 运用c语言,动态规划算法构造最优二叉查找树
  • 构造所有二叉查找树

    2015-09-27 10:52:19
    给出n,生成所有由1...n为节点组成的不同的二叉查找树 您在真实的面试中是否遇到过这个题?  Yes 样例 给出n = 3,生成所有5种不同形态的二叉查找树: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 ...
  • 二叉查找树 BST 查找树是一种数据结构,支持动态集合操作。在二叉查找树上执行基本操作的时间与树的高度成... 一颗随机构造二叉查找树的操作平均时间是O(logn). 性质: 对于任何节点x,其左子树的关键字最大不
  • 一组相同的数据所构造出来的二叉查找树不同。 二叉查找树的查找:(一个函数) struct Node{ int data; Node* lchild,rchild; }; //查找 void search(Node* root,int x){ //指向树的指针,要查找的树 if...
  • 给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。 本题中,一个高度平衡二叉树是指一个二叉树每个节点的左右两个...解题思路:这道题与上一题的根据有序的数组构造二叉查找树相同,唯一不...
  • 构造二叉搜索C++

    2015-04-08 20:31:49
    构造一颗二叉搜索树,树的结构如图(a),下面上代码(最后输出是中序遍历输出的) #include using namespace std; typedef struct BSTree { char node_value;.../*****构造二叉查找树*******************
  • 这是一篇两年前写的东西,自我感觉还是相当不错的Treap教程...详细实现了二叉查找树的各种操作:插入结点、构造二叉树、删除结点、查找、 查找最大值、查找最小值、查找指定结点的前驱和后继 2、二叉查找树简介 ...
  • 二叉排序树(BST)的构造,节点插入,节点查找,节点删除(java) 高度最小BST(同样数据...// 二叉排序树(二叉查找树)BST // 对于给定数组(数据完全一样,并且数据顺序一定)构造二叉排序树一定,但是数据一样,顺序不一样

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,070
精华内容 428
关键字:

构造二叉查找树