二叉樹経典テーマ

1.ノードが一本の二叉の木の中にあるかどうかを判断し、左の子樹であるかどうかを判断し、もしそうであれば、もう右の子樹の中に探さない.いなかったら、また右の木の中を探しに行きます.再帰的条件の判断に注意しなければならない.

    bool _IsInTree(Node *root, Node *node)
    {
        if (root == NULL || node == NULL)
            return false;
        else if (root == node)
            return true;
        else if (_IsInTree(root->_left, node))
            return true;
        else
            _IsInTree(root->_right, node);
    }

    bool IsInTree(Node *node)
    {
        return _IsInTree(_root, node);
    }

2.一本の二叉の木が平衡二叉の木であるかどうかを判断する.一本の二叉の木はバランスが取れている二叉の木である.二叉の木をバランスさせる条件は、左サブツリーと右サブツリーの高さ差が1、0、−1です.

    bool _IsBalance(Node *root)
    {
        if (root == NULL)
            return true;

        size_t leftDepth = _Depth(root->_left);
        size_t rightDepth = _Depth(root->_right);
        size_t sub = leftDepth - rightDepth;
        if (sub < 2 && sub >-2)
            return true;

        return _IsBalance(root->_left) && _IsBalance(root->_right);
    }

    bool IsBalance()
    {
        return _IsBalance(_root);
    }

上記の方法は、ツリー中のノードを巡回することを何度も繰り返すので、効率が低すぎる.ノードを巡回しながらノードの深さを保存することができ、同じノードを巡回する必要がなくなり、効率が向上しました.

    bool _IsBalance(Node *root, int* depth)
    {
        if (root == NULL)
        {
            *depth = 0;
            return true;
        }

        int leftDepth;
        int rightDepth;
        if (_IsBalance(root->_left, &leftDepth) && _IsBalance(root->_right, &rightDepth))
        {
            int sub = leftDepth - rightDepth;
            if (sub < 2 && sub >-2)
            {
                *depth = leftDepth > rightDepth ? leftDepth+1 : rightDepth+1;
                return true;
            }
            else
                return false;
        }
    }

    bool IsBalance()
    {
        int depth = 0;
        return _IsBalance(_root, &depth);
    }

3.二叉の木の鏡像を求めて、名前の通りに、二叉の木が鏡に映っている.つまり、二叉樹では、各ノードの左右のツリーが互いに交換されています.

    void _MirrorTree(Node *root)
    {
        if (root == NULL)
            return;
        else if (root->_left == NULL && root->_right == NULL)
            return;
        else
        {
            Node* temp = root->_left;
            root->_left = root->_right;
            root->_right = temp;
        }

        if (root->_left)
            _MirrorTree(root->_left);
        if (root->_right)
            _MirrorTree(root->_right);
    }

    void MirrorTree()
    {
        _MirrorTree(_root);
    }

4.2つのノードの最近の共通の祖先の1)二叉樹の各ノードにparentポインタ(三叉チェーン)二叉樹のノード構造があることを求めます.

struct Node1
{
    int _data;
    Node1* _parent;
    Node1* _left;
    Node1* _right;

    Node1(const int& data)
        :_data(data)
        , _parent(NULL)
        , _left(NULL)
        , _right(NULL)
    {}
};

ここでは二つの方法を示します.

//    O(N^2)
Node1* LastAncestor(Node1* node1, Node1* node2)
{
    if (node1 == NULL && node2 == NULL)
        return NULL;
    if (node1 == node2)
        return node1;

    Node1* cur1 = NULL;
    while (node2)
    {
        cur1 = node1;
        while (cur1)
        {
            if (cur1->_parent != node2->_parent)
                cur1 = cur1->_parent;
            else
                return cur1->_parent;
        }
        node2 = node2->_parent;
    }
    return NULL;
}

//   ，           O(N)
int GetLength(Node1* node)
{
    if (node == NULL)
        return 0;

    int length = 0;
    while (node)
    {
        length++;
        node = node->_parent;
    }
    return length;
}

Node1* LastAncestor1(Node1* node1, Node1* node2)
{
    if (node1 == NULL && node2 == NULL)
        return NULL;

    int len1 = GetLength(node1);
    int len2 = GetLength(node2);

    while (len1 > len2)
    {
        node1 = node1->_parent;
        len1--;
    }
    while (len2 > len1)
    {
        node2 = node2->_parent;
        len2--;
    }

    while (node1 && node2 && node1 != node2)
    {
        node1 = node1->_parent;
        node2 = node2->_parent;
    }
    if (node1 == node2)
        return node1;

    return NULL;
}

2)二叉樹は、二叉樹O(N)を検索して二叉樹を検索する特徴として、左サブツリーのノードはいずれもルートノードより小さく、右サブツリーのノードは全てルートノードより大きく、左サブツリーと右サブツリーも二叉樹を検索することができる.このようにして、2つのノードとそのルートノードのサイズを比較することによって、それらの最近の共通ノードを求めることができる.1つのノードがルートノードより大きい場合、1つのノードがルートノードより小さい場合、ルートノードはそれらの一番近い共通ノードである.両方のノードがルートノードより小さい場合、ルートノードの左のサブツリーから探す.両方のノードがルートノードより大きい場合、ルートノードの右サブツリーから探す.

typedef struct SearchBinaryTreeNode
{
    int _key;
    SearchBinaryTreeNode* _left;
    SearchBinaryTreeNode* _right;

    SearchBinaryTreeNode(const int& key)
        :_key(key)
        , _left(NULL)
        , _right(NULL)
    {}
}Node2;

void Insert1(Node2* root, const int& key)
{
    if (root == NULL)
    {
        root = new Node2(key);
        return;
    }
    else
    {
        Node2* parent = NULL;
        Node2* cur = root;
        while (cur)
        {
            if (cur->_key < key)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_key > key)
            {
                parent = cur;
                cur = cur->_left;
            }
            else
            {
                return;
            }
        }
        if (parent->_key < key)
        {
            parent->_right = new Node2(key);
        }
        if (parent->_key > key)
        {
            parent->_left = new Node2(key);
        }
    }
}

Node2* LastAncestor2(Node2* root, Node2* node1, Node2* node2)
{
    if (root == NULL || (node1 == NULL && node2 == NULL))
        return NULL;

    while (root)
    {
        if (node1 == root || node2 == root)
            return root;

        if (node1->_key < root->_key && node2->_key < root->_key)
        {
            root = root->_left;
        }
        else if (node1->_key > root->_key && node2->_key > root->_key)
        {
            root = root->_right;
        }
        else
        {
            return root;
        }
    }
    return NULL;
}

3)二叉樹は普通の二叉樹である.

typedef struct Node3
{
    int _data;
    Node3* _left;
    Node3* _right;

    Node3(const int& data)
        :_data(data)
        , _left(NULL)
        , _right(NULL)
    {}
};

Node3* CreateTree(int *arr, size_t n, const int& invalid, size_t& index)
{
    Node3 *root = NULL;
    if (index < n && arr[index] != invalid)
    {
        root = new Node3(arr[index]);
        index++;
        root->_left = CreateTree(arr, n, invalid, index);
        index++;
        root->_right = CreateTree(arr, n, invalid, index);
    }
    return root;
}

//1.     O(N^2)
Node3* LastAncestor3(Node3* root, Node3* node1, Node3* node2)
{
    if (root == NULL || (node1 == NULL && node2 == NULL))
        return NULL;
    if (node1 == root || node2 == root)
    {
        return root;
    }
    if ((root->_left == node1 && root->_right == node2) || (root->_left == node2 && root->_right == node1))
    {
        return root;
    }

    Node3* left = LastAncestor3(root->_left, node1, node2);
    Node3* right = LastAncestor3(root->_right, node1, node2);
    if (left && right)
        return root;
    if (left == NULL)
        return right;
    else
        return left;
}

//2.       ，                   O(N)，     O(N*lgN) 
bool GetNodePath(Node3* root, Node3* node, stack& path)
{
    if (root == NULL || node == NULL)
        return NULL;

    Node3* cur = root;
    path.push(cur);
    if (path.top() == node)
        return true;
    if (GetNodePath(root->_left, node, path))
        return true;
    if (GetNodePath(root->_right, node, path))
        return true;

    path.pop();
    return false;
}

Node3* LastAncestor4(Node3* root, Node3* node1, Node3* node2)
{
    if (root == NULL || (node1 == NULL && node2 == NULL))
        return NULL;

    stack path1;
    stack path2;
    if (GetNodePath(root, node1, path1) == false)
        return NULL;
    if (GetNodePath(root, node2, path2) == false)
        return NULL;

    while (path1.size() != path2.size())
    {
        if (path1.size() > path2.size())
            path1.pop();
        else
            path2.pop();
    }

    while (path1.top() != path2.top())
    {
        path1.pop();
        path2.pop();
    }
    if (path1.top() == path2.top())
        return path1.top();
}

以上のすべての方法のテスト用例

void test5()
{
    Node1* root1 = new Node1(1);

    Node1* cur = root1;
    queue q;
    Node1* top = NULL;

    q.push(root1);
    for (int i = 2; i <= 7; i++)
    {
        if (!q.empty())
        {
            top = q.front();
            if (cur == top->_left)
            {
                cur = new Node1(i);
                top->_right = cur;
                cur->_parent = top;
                q.pop();
            }
            else
            {
                cur = new Node1(i);
                top->_left = cur;
                cur->_parent = top;
            }
            q.push(cur);
        }
    }
    Node1* node1 = root1->_left->_left;
    Node1* node2 = root1->_right;
    cout << LastAncestor(node1, node2)->_data << endl;
    cout << LastAncestor1(node1, node2)->_data << endl;

    Node2* root2 = new Node2(10);
    Insert1(root2, 8);
    Insert1(root2, 15);
    Insert1(root2, 5);
    Insert1(root2, 9);
    Insert1(root2, 13);
    Insert1(root2, 18);

    Node2* node3 = root2->_left->_left;
    Node2* node4 = root2->_left->_right;
    cout << LastAncestor2(root2, node3, node4)->_key << endl;

    int array[] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6 };
    size_t index = 0;
    Node3* root3 = CreateTree(array, sizeof(array) / sizeof(array[0]), '#', index);
    Node3* node5 = root3->_left->_left;
    Node3* node6 = root3->_right->_left;
    cout << LastAncestor3(root3, node5, node6)->_data << endl;

    cout << LastAncestor4(root3, node5, node6)->_data << endl;
}

5.二叉樹の中で最も遠い二つのノードの距離を求めて、現在のノードを根とする二叉樹の中で最も遠い二つのノードの距離を求めて、先に現在のノードの左の子供を根とする二叉樹の中で最も遠い二つのノードの距離と、現在のノードの右の子供を根とする二叉樹の中で最も遠い二つのノードの距離を求めます.

int _GetMaxDistance(Node3* node, int& distance)
{
    if (node == NULL)
        return 0;

    int l = _GetMaxDistance(node->_left, distance);
    int r = _GetMaxDistance(node->_right, distance);

    if (l + r > distance)
    {
        distance = l + r;
    }

    return l > r ? l + 1 : r + 1;
}

int GetMaxDistance(Node3* root)
{
    int distance = 0;
    _GetMaxDistance(root, distance);
    return distance;
}

6.前の順序で巡回し、中の順序で二叉の木を再構築します.前のシーケンス:1 2 3 4 5-中のシーケンス:3 4 6

    Node* RebuildBinaryTree1(int* prev, int* in, int n)
    {
        if (n <= 0)  //         ！！！
            return NULL;
        Node* root = (Node*)malloc(sizeof(Node));
        root->_data = prev[0];
        root->_left = root->_right = NULL;
        int* p = in;
        int k = 0;
        while (*p != *prev)
        {
            p++;
        }
        k = p - in;
        root->_left = RebuildBinaryTree1(prev + 1, in, k);
        root->_right = RebuildBinaryTree1(prev + k + 1, p + 1, n - k - 1);

        return root;
    }

7.後順順に巡回し、中順に二叉樹を再構築します.例えば:後序シーケンス:3 4 2 6 1-中序シーケンス:3 4 1 6 5

    Node* RebuildBinaryTree2(int* post, int* in, int n)
    {
        if (n <= 0)
            return NULL;
        Node* root = (Node*)malloc(sizeof(Node));
        root->_data = *(post + n - 1);
        root->_left = root->_right = NULL;
        int* p = in;
        int k = 0;
        while (*p != *(post + n - 1))
        {
            p++;
        }
        k = p - in;
        root->_left = RebuildBinaryTree2(post, in, k);
        root->_right = RebuildBinaryTree2(post + k, p + 1, n - k - 1);

        return root;
    }

8.一本の木が完全に二叉の木かどうかを判断する:最後の層を除いて、各層のノード数が最大値に達する;最後の層では、右のいくつかの結点だけが欠けています.つまり、右のノードが必ず左のノードを持っています.マークの設定方法を考えると多すぎて、間違えやすいです.ここでは、空間キューを補助的に記憶することによって、空ノードおよび葉っぱノードを含む2つのツリーのすべてのノードを、階層的に巡回する方法でキューに入れ、対応するノードをイジェクトするより簡便で信頼できる方法を紹介する.完全に二叉の木であれば、最後の列に残っているのは全部空のノードです.そうでなければ、完全に二叉の木ではありません.

bool IsComplexBinaryTree(TreeNode* root)
{
    queue q;
    TreeNode* cur = root;
    if (root == NULL)
        return true;
    q.push(cur);
    while (cur)
    {
        q.push(cur->_left);
        q.push(cur->_right);
        q.pop();
        cur = q.front();
    }
    while (!q.empty())
    {
        if (q.front() != NULL)
            return false;
        q.pop();
    }
    return true;
}

9.二叉検索ツリーを並べ替えた双方向チェーンテーブルです.任意の新しい結点を作成することができず、ツリー内の結点ポインタの方向を調整するしかないことを要求します.leftをprevとして、rightをnextとして考えることができます.

    //            ，         ，              
    void _ConvertNode(Node* root, Node*& tailOfList)
    {
        if (root == NULL)
            return;
        Node* cur = root;
        if (cur->_left)
            _ConvertNode(cur->_left, tailOfList);

        cur->_left = tailOfList;
        if (tailOfList != NULL)
            tailOfList->_right = cur;
        tailOfList = cur;

        if (cur->_right)
            _ConvertNode(cur->_right, tailOfList);
    }

    Node* Convert()
    {
        Node* tailOfList = NULL;
        _ConvertNode(_root, tailOfList);

        Node* headOfList = tailOfList;
        while (headOfList && headOfList->_left)
        {
            headOfList = headOfList->_left;
        }

        return headOfList;
    }

10.二叉の木が別の木かどうかを判断する.

//1.  tree1      tree2         
bool DoseTree1HasTree2(TreeNode *root1, TreeNode *root2);

bool IsSubTree(TreeNode* root1, TreeNode* root2)
{
    if (root1 == NULL || root2 == NULL)
        return false;

    bool ret = false;
    if (DoseTree1HasTree2(root1, root2))
        ret = true;
    if (!ret)
    {
        ret = IsSubTree(root1->_left, root2);
    }
    if (!ret)
    {
        ret = IsSubTree(root1->_right, root2);
    }

    return ret;
}

//2.  tree1  root1          tree2      
bool DoseTree1HasTree2(TreeNode *root1, TreeNode *root2)
{
    if (root2 == NULL)
        return true;
    if (root1 == NULL)
        return false;
    if (root1->_data != root2->_data)
        return false;

    return DoseTree1HasTree2(root1->_left, root2->_left) && DoseTree1HasTree2(root1->_right, root2->_right);
}