树

    root 没父节点
    leaf 没子节点

// BinaryTree.h
#pragma once

struct Node 
{
    int    key; 
    Node*  lc;  
    Node*  rc; 
};

Node* CreateBinaryTreeNode(int key);
void ConnectTreeNodes(Node* proot, Node* lc, Node* rc);
void DestroyTree(Node* proot);
void PrintTreeNode(Node* pnode);
void PrintTree(Node* proot);

// BinaryTree.cpp
#include "BinaryTree.h"
#include <stdio.h>

Node* CreateBinaryTreeNode(int key)
{
    Node* pNode = new Node();
    pNode->key = key;
    pNode->lc = NULL;
    pNode->rc = NULL;

    return pNode;
}

void ConnectTreeNodes(Node* pParent, Node* pLeft, Node* pRight)
{
    if(pParent != NULL)
    {
        pParent->lc = pLeft;
        pParent->rc = pRight;
    }
}

void DestroyTree(Node* pRoot)
{
    if (pRoot != NULL)
    {
        // (1) 记录 left/rc node 
        Node* lc = pRoot->lc;
        Node* rc = pRoot->rc;

        // (2) delete 本层 root 
        delete pRoot;
        pRoot = NULL;

        // (3) 递归 destory 左/右子树
        DestroyTree(lc);
        DestroyTree(rc);
    }
}

// 打印出 该节点及其 left/rc 孩子
void PrintTreeNode(Node* pNode)
{
    if(pNode != NULL)
    {
        printf("key of this node is: %d\n", pNode->key);

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

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

    printf("\n");
}

// 先序遍历: 根左右
void PrintTree(Node* pRoot)
{
    PrintTreeNode(pRoot);

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

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

递归: 3 要素

(1) 递归函数: paras/returnValue

(2) 终止条件

(3) 本层递归逻辑

1 3种遍历 & 递归/迭代 => 6 种实现

    前/中/后 序: 先/中/后 根 

先序
    根          左           右
    |           |            |
    |           |            |
    |/          |/           |/
    立即出     后入先出   先(于左)入后出

    stack : 组织 pnode 进出顺序, 实现 根左右
        根入栈

        stack 循环: until 栈 empty

            根 出(key 放 vector) -> 右 入 -> 左 入
                |\                          |
                |_ _ _ _ _ _ _ _ _ _ _ _ _ _|

    vector: 存 遍历结果

中序: 左 根 右
    const Node* p = proot;
    while ( !stk.empty() || p != nullptr )
    [1] 沿左孩子 入栈 & walk, 直到 walk 到空
    [2] 取出(top)栈顶(放 遍历结果 vector),
        即 空左孩子的 root => 遍历顺序 `左根右` 转换为 `根右`
    [3] 遍历/walk 指针 p 移到 该 root 的 右孩子 => 对右孩子继续循环
    [4] pop 该 root

后序: 左 右 根

与 中序 区别:

    pnode 出栈 后, 不是 直接 放到 vector
    而是 判断 若 pnode->rc 已被访问, 才 放到 vector, else pnode 又入栈

    用 `标志(指针)变量` record 刚访问过 的 node

//  3   b_tree_client.cpp
#include "../Utilities/BinaryTree.h"
#include <cstdio>
#include <iostream>
#include <vector>
#include <stack>

//  === 1   3种 遍历 ( traverse ) * 2 种版本 ( 迭代 + 递归 )
// 先 根/序 : 根 -> 左 -> 右
// 中 序  : 左 -> 根 -> 右
// 后 序  : 左 -> 右 -> 根

void
preWalk(Node* walk)
{
    if (walk != NULL)
    {
        printf("%d ", walk->key);
        preWalk(walk->lc);
        preWalk(walk->rc);
    }
}

void
MidWalk(Node* walk)
{
    if (walk != NULL)
    {
        MidWalk(walk->lc);
        printf("%d ", walk->key);
        MidWalk(walk->rc);
    }
}

void
postWalk(Node* walk)
{
    if (walk != NULL)
    {
        postWalk(walk->lc);
        postWalk(walk->rc);
        printf("%d ", walk->key);
    }
}

/*
先序
    根          左           右
    |           |            |
    |           |            |
    |/          |/           |/
    立即出     后入先出   先(于左)入后出

    stack : 组织 pnode 进出顺序, 实现 根左右
        根入栈

        stack 循环: until 栈 empty

            根 出(key 放 vector) -> 右 入 -> 左 入
                |\                          |
                |_ _ _ _ _ _ _ _ _ _ _ _ _ _|

    vector: 存 遍历结果
*/

std::vector<int>
preWalkIter(Node* proot)
{
    std::vector<int> resVec;
    std::stack<const Node*> stk;

    if (proot != nullptr)
        stk.push(proot);    // (1) root 入栈 

    while (!stk.empty())    // (2) stack 循环: until 栈 empty
    {
        // (6) record root & 放 root->key 到 遍历结果的 vector
        // top -> push root->key 到 vector
        const Node* p = stk.top();
        resVec.push_back(p->key);


        stk.pop();           // (3) root 出

        if (p->rc != nullptr)
            stk.push(p->rc); // (4) 右入

        if (p->lc != nullptr)
            stk.push(p->lc); // (5) 左入
    }

    for (std::vector<int>::iterator iter = resVec.begin(); iter != resVec.end(); ++iter)
        std::cout << *iter << ' ' << std::endl;

    return resVec;
}

/*  中序: 左 根 右
    const Node* p = proot;
    while ( !stk.empty() || p != nullptr )
    [1] 沿左孩子 入栈 & walk, 直到 walk 到空
    [2] 取出(top)栈顶(放 遍历结果 vector),
        即 空左孩子的 root => 遍历顺序 `左根右` 转换为 `根右`
    [3] 遍历/walk 指针 p 移到 该 root 的 右孩子 => 对右孩子继续循环
    [4] pop 该 root
*/
std::vector<int>
MidWalkIter(Node* proot)
{
    std::vector<int> resVec;
    std::stack<const Node*> stk;

    const Node* p = proot;
    while (!stk.empty() || p != nullptr)
    {
        if (p != nullptr)
        {
            stk.push(p);
            p = p->lc;
        }
        else // == nullptr         
        {
            p = stk.top();
            resVec.push_back(p->key);

            p = p->rc;

            stk.pop();
        }
    }

    for (std::vector<int>::iterator iter = resVec.begin(); iter != resVec.end(); ++iter)
        std::cout << *iter << ' ' << std::endl;

    return resVec;
}

/*

后序: 左 右 根

与 中序 区别:

    pnode 出栈 后, 不是 直接 放到 vector
    而是 判断 若 pnode->rc 已被访问, 才 放到 vector, else pnode 又入栈

    用 `标志(指针)变量` record 刚访问过 的 node
*/

// 
std::vector<int>
postWalkIter(Node* proot)
{
    std::vector<int> resVec;
    std::stack<const Node*> stk;

    const Node* p = proot, * justVisited = nullptr;

    // 2 层 循环
    do
    {
        while (p != nullptr)
        {
            stk.push(p);
            p = p->lc;
        }

        justVisited = nullptr;

        while (!stk.empty())
        {
            p = stk.top();                  // pnode 取出 
            stk.pop();                      // pnode 出栈 

            if (p->rc == justVisited)       // 若 pnode->rc 已被访问
            {
                resVec.push_back(p->key);   //      pnode->key 放 vector 
                justVisited = p;
            }
            else                            // else
            {
                stk.push(p);                //      pnode 又入栈 

                p = p->rc;

                // 跳出 内层 循环
                break;
            }
        }

    } while (!stk.empty());

    for (std::vector<int>::iterator iter = resVec.begin(); iter != resVec.end(); ++iter)
        std::cout << *iter << ' ' << std::endl;

    return resVec;
}

void
Test(Node* pnode)
{

    printf("\n === MidWalk:\n");
    MidWalk(pnode);

    printf("\n === preWalkIter:\n");
    preWalkIter(pnode);

    printf("\n === MidWalkIter:\n");
    MidWalkIter(pnode);

    printf("\n === postWalkIter:\n");
    postWalkIter(pnode);

    printf("\n");
}

// 普通二叉树
//              1
//           /     \
//          2       3  
//         /       / \
//        4       5   6
void Test1()
{
    printf("Test1 begins.\n");

    Node* pnode1 = CreateBinaryTreeNode(1);
    Node* pnode2 = CreateBinaryTreeNode(2);
    Node* pnode3 = CreateBinaryTreeNode(3);
    Node* pnode4 = CreateBinaryTreeNode(4);
    Node* pnode5 = CreateBinaryTreeNode(5);
    Node* pnode6 = CreateBinaryTreeNode(6);

    ConnectTreeNodes(pnode1, pnode2, pnode3);
    ConnectTreeNodes(pnode2, pnode4, NULL);
    ConnectTreeNodes(pnode3, pnode5, pnode6);

    Test(pnode1);

    DestroyTree(pnode1);
}

void Test2()
{
    printf("Test2 begins.\n");
    Test(NULL);
}

int main()
{
    Test1();
    Test2();
}

Que24 后序遍历 迭代版

Que23 从上到下遍历二叉树: 宽度优先遍历

Que6 重建二叉树

    input: 前序 和 中序 遍历序列 & 结点数
    output: 重建二叉树, return root 指针

            1
          /   \
        2       3
       /       /  \
     4        5     6
     
    前序 {1, 2, 4, 3, 5, 6}
    中序 {4, 2, 1, 5, 3, 6}

序列: 数组

    前序  1       2       4       3       5       6
                    |       |       |       |       |
         root       - - - - -        - - - - - - - - 
                     左子树                右子树
    
    
    中序  4       2       1       5       3       6
            |_ _ _ _|               |_ _ _ _|_ _ _ _|
                             
                左           root        右

(1) 前序序列 中 第1个(index = 0) 是 root

(2) 据 root 在 中序序列中 find root 位置(index), 同时计算 左子树长度 leftTreeLen + 已知 树长度 treeLen

则, 可计算出 中序序列中 左/右子树 indexRange + 前序序列 => 前序序列 左/右子树 indexRange

(3) 递归重建 左/右子树

递归3要素

    1) 递归函数

    2) 终止条件
        前/中序序列 只剩1个 node    
        
    3) 本层递归逻辑
        [1] 据中序序列 第1个 elemValue jnew 1 个 node 作为 本层/子树 的 root 
            
            leftPtr/rightPtr = 递归重建 左右子树
                
        [2] 据 root 在 中序序列中 find root index, 计算 `左子树长度 leftTreeLen` 
            
            => 计算出 前&中序序列 中 左/右子树 indexRange
            
        [3] 递归 paras & returnValue 

        [4] 递归 returnValue: return 本层/子树 递归的 returnValue == rootPtr

// ConstructBinaryTree.cpp

#include "..\Utilities\BinaryTree.h"
#include <exception>
#include <stdio.h>

Node* ConstructCore(int* startIndexPreOrder, int* endIndexPreOrder, 
    int* startIndexInOrder, int* endIndexInOrder);

Node* Construct(int* preorder, int* inorder, int length)
{
    if(preorder == NULL || inorder == NULL || length <= 0)
        return NULL;

    return ConstructCore(preorder, preorder + length - 1,
        inorder, inorder + length - 1);
}

// preOredr/InOrder SquenceRange: 前闭后闭 
Node* ConstructCore(int* startIndexPreOrder, int* endIndexPreOrder, 
    int* startIndexInOrder, int* endIndexInOrder
)
{
    // (1-1) 前序遍历序列的第一个数字是根结点的值
    int rootValue = startIndexPreOrder[0];
    Node* root = new Node();
    root->key = rootValue;
    root->lc = root->rc = NULL;

    // (2) 递归终止条件: 只有1个 node 
    if(startIndexPreOrder == endIndexPreOrder)
    {
        if(startIndexInOrder == endIndexInOrder && *startIndexPreOrder == *startIndexInOrder)
            return root;
        else
            throw std::exception("Invalid input.");
    }

    // (1-2) 据 root `在 中序序列中 find rootIndex
    int* rootIndexInorder = startIndexInOrder;
    while(rootIndexInorder <= endIndexInOrder && *rootIndexInorder != rootValue)
        ++ rootIndexInorder;

    if(rootIndexInorder == endIndexInOrder && *rootIndexInorder != rootValue)
        throw std::exception("Invalid input.");

    // (1-3) 计算 左子树长度 leftTreeLen => 前&中序序列 中 左/右子树 indexRange: 递归 paras
    int leftSubTreeLen = rootIndexInorder - startIndexInOrder;

    // (3) 递归重建 左/右子树
    if(leftSubTreeLen > 0)
    {
        // 构建左子树
        root->lc = ConstructCore(startIndexPreOrder + 1, startIndexPreOrder + leftSubTreeLen,
            startIndexInOrder, rootIndexInorder - 1);
    }
    if(leftSubTreeLen < endIndexPreOrder - startIndexPreOrder)
    {
        // 构建右子树
        root->rc = ConstructCore(startIndexPreOrder + leftSubTreeLen + 1, endIndexPreOrder,
            rootIndexInorder + 1, endIndexInOrder);
    }

    // (1-4) 本层/子树 递归 returnValue
    return root;
}

void Test(const char* testName, int* preorder, int* inorder, int length)
{
    if(testName != NULL)
        printf("%s begins:\n", testName);

    printf("The preorder sequence is: ");
    for(int i = 0; i < length; ++ i)
        printf("%d ", preorder[i]);
    printf("\n");

    printf("The inorder sequence is: ");
    for(int i = 0; i < length; ++ i)
        printf("%d ", inorder[i]);
    printf("\n");

    try
    {
        Node* root = Construct(preorder, inorder, length);
        PrintTree(root);

        DestroyTree(root);
    }
    catch(std::exception& exception)
    {
        printf("Invalid Input.\n");
    }
}

// 普通二叉树
//              1
//           /     \
//          2       3  
//         /       / \
//        4       5   6
void Test1()
{
    const int length = 6;
    int preorder[length] = { 1, 2, 4, 3, 5, 6 };
    int inorder[length] = { 4, 2, 1, 5, 3, 6 };

    Test("Test1", preorder, inorder, length);
}

// 所有结点都没有右子结点
//            1
//           / 
//          2   
//         / 
//        3 
void Test2()
{
    const int length = 3;
    int preorder[length] = {1, 2, 3};
    int inorder[length] = {3, 2, 1};

    Test("Test2", preorder, inorder, length);
}


// 树中只有一个结点
void Test3()
{
    const int length = 1;
    int preorder[length] = {1};
    int inorder[length] = {1};

    Test("Test3", preorder, inorder, length);
}

// 空指针
void Test4()
{
    Test("Test4", NULL, NULL, 0);
}

// 两个序列不匹配
void Test5()
{
    const int length = 7;
    int preorder[length] = {1, 2, 4, 5, 3, 6, 7};
    int inorder[length] = {4, 2, 8, 1, 6, 3, 7};

    Test("Test5: for unmatched input", preorder, inorder, length);
}

int main(int argc, char* argv[])
{
    Test1();
    Test2();
    Test3();
    Test4();
    Test5();
}

Que18 树的子结构

Que25 二叉树中和为某值的路径

Que39 二叉树深度

2 二叉搜索树: 左 <= 根 <= 右

Que27 二叉树与双向链表

Que50 树中两个节点的最低公共祖先

3 heap

最大堆: 堆中 根最大 => 可解决 快速查找最大值问题

Que30 求最小的 k 个数字

4 红黑树

5 二叉 搜索/排序 树

    //  1   BinaryTree.h
    #ifndef _BT_H
    #define _BT_H

    typedef struct Node 
    {
        int             key; 
        struct Node* p;
        struct Node* lc;  
        struct Node* rc; 
    }Node;

    Node* 
    createNode(int key);

    void 
    connectNodes(Node* p, 
                  Node* lc, 
                  Node* rc);

    void 
    freeTree(Node* proot);
                  
    void 
    printNode(Node* pnode);

    void 
    printTree(Node* proot);
                  
    #endif

    //  2   BinaryTree.cpp
    #include <cstdio>
    #include <stdlib.h>    // malloc / free
    #include "BinaryTree.h"

    Node* 
    createNode(int key)
    {
        Node* pnode = (Node*) malloc( sizeof(Node) );
        
        pnode->key = key;
        pnode->p = NULL;
        pnode->lc = NULL;
        pnode->rc = NULL;

        return pnode;
    }

    void 
    connectNodes(Node* p, 
                  Node* lc, 
                  Node* rc)
    {
        if( p != NULL)
        {
            p->lc = lc;
            p->rc = rc;
        }
        
        if(lc != NULL)
            lc->p = p;
        if(rc != NULL)
            rc->p = p;
    }

    void
    freeTree(Node* proot)
    {
        if (proot != NULL)
        {
            Node* lc = proot->lc;
            Node* rc = proot->rc;

            free(proot);
            proot = NULL;

            freeTree(lc);
            freeTree(rc);
        }
    }

    void 
    printNode(Node* pnode)
    {
        if(pnode != NULL)
            printf("node key: %d\n", pnode->key);
        else
            printf("this node is null.\n");
    }

    void 
    printTree(Node* proot)
    {
        printNode(proot);

        if(proot != NULL)
        {
            if(proot->lc != NULL)
                printTree(proot->lc);

            if(proot->rc != NULL)
                printTree(proot->rc);
        }
    }

    //  3   b_tree_client.cpp
    #include <cstdio>
    #include <iostream>
    #include <vector>
    #include <stack>
    #include "BinaryTree.h"

    //---2. find: 指定 / 最小 / 最大 node 
    //            指定 node 的 next / prev
    Node*
    tree_search(Node* walk, int key)
    {
        /* 
            until: walk == NIL || walk.key == key
                                    |
                                    |   隐含  
                                    |/
                执行到 || 右侧 =>  walk != NIL
        */
        while (walk != NULL && walk->key != key)
        {
            if (key < walk->key)
                walk = walk->lc;
            else
                walk = walk->rc;
        }
        return walk;
    }

    Node*
    tree_minimum(Node* walk)
    {
        while (walk != NULL && walk->lc != NULL)
            walk = walk->lc;
        return walk;
    }

    //(3) 与 tree_minimum 对称
    Node*
    tree_maximum(Node* walk)
    {
        while (walk != NULL && walk->rc != NULL)
            walk = walk->rc;
        return walk;
    }

    // (4)
    Node*
    tree_successor(Node* walk)
    {
        if (walk == NULL)
            return walk;
        // below 初始 必 walk != NIL

        // walk 有 右孩子 -> 后继 为 右孩子 最小值
        if (walk->rc != NULL) 
            return tree_minimum(walk->rc);

        // 取 walk.p -> 据 walk 是 root / lc / rc 分别处理
        Node* walk_p = walk->p;

        while (walk_p != NULL && walk == walk_p->rc)
        {
            walk = walk_p;           
            walk_p = walk_p->p; 
        }
        return walk_p;
    }

    // (5) 与 tree_successor 对称
    Node*
    tree_predecessor(Node* walk)
    {
        if (walk == NULL)
            return walk;
        if (walk->lc != NULL)
            return tree_maximum(walk->lc);

        Node* walk_p = walk->p;

        while (walk_p != NULL && walk == walk_p->lc)
        {
            walk = walk_p; 
            walk_p = walk_p->p; 
        }
        return walk_p;
    }

    //---3. insert / delete
    // 可能改变 根指针 => 将 根指针 的 指针 传进来 
    void
    tree_insert(Node** proot, Node* z)
    {
        Node* walk_p = NULL;
        Node* walk = *proot;

        while (walk != NULL)
        {
            walk_p = walk;

            if(z->key < walk->key)
                walk = walk->lc;
            else  // >=
                walk = walk->rc;
        }

        z->p = walk_p;

        if (walk_p == NULL)
            *proot = z;     // 改变 根指针
        else if (z->key < walk_p->key) // below: walk_p != NIL
            walk_p->lc = z;
        else
            walk_p->rc = z;
    }

    // 可能改变 根指针 => 将 根指针 的 指针 传进来 
    void 
    transplant(Node** proot, 
               Node* u, 
               Node* v)
    {
        if (u == *proot && u == NULL)
            *proot = v;

        if (u->p == NULL)   // u == *proot
            *proot = v;
        else if (u == u->p->lc) // below: firstly u.p != NIL
            u->p->lc = v;
        else // if u == u.p.rc
            u->p->rc = v;

        if (v != NULL)
            v->p = u->p;
    }

    void
    tree_delete(Node** proot, Node* z)
    {
        if (z->lc == NULL)        // below: firstly z.lc ！= NIL // 可 z.rc == NIL
            transplant(proot, z, z->rc);
        else if (z->rc == NULL)   // z.lc ！= NIL && z.rc == NIL 
            transplant(proot, z, z->lc);
        else                      // z.lc ！= NIL && z.rc ！= NIL
        {
            Node* y = tree_minimum(z->rc); // z_next / y

            if( y->p != z )
            {
                //(1)
                transplant(proot, y, y->rc);

                //(2) link y <-> z.rc
                y->rc = z->rc;
                y->rc->p = y;
            }
            //(3)
            transplant(proot, z, y);

            //(4) link y<-> z.lc
            y->lc = z->lc;
            y->lc->p = y;
        }

    }
    //---4. depth

    // 用 queue, 时/空 复杂度 O(N)
    std::vector<int>
    BFS_tree_walk(Node* proot)
    {
        //(1) vector: 存 output sequence
        std::vector<int> res;

        //(2) queue: 存 即将 遍历的 pnode, 
        //           后 进 先 出/遍历
        std::queue<const Node*> que;

        //(3) root pointer 先入栈
        if (proot != nullptr)
            que.push(proot);

        //(4) stack 再循环: 若 栈 not empty
        while (!que.empty())
        {
            // 1) get/top old_top elem/pnode
            // 2) pop top elem
            // 3) old_top.key 入 vector
            // 4) old_top->lc 入 queue
            // 5) old_top->rc 入 queue
            const Node* p = que.front();
            que.pop();

            res.push_back(p->key);

            if (p->lc != nullptr)
                que.push(p->lc);
            if (p->rc != nullptr)
                que.push(p->rc);
        }

        for (std::vector<int>::iterator
            iter = res.begin();
            iter != res.end();
            ++iter)
            std::cout << *iter << ' ' << std::endl;

        return res;
    }

    int tree_depth(Node* proot)
    {
        if(proot == NULL)
            return 0;

        int ldepth = tree_depth(proot->lc);
        int rdepth = tree_depth(proot->rc);

        return (ldepth > rdepth) ? (ldepth + 1) : (rdepth + 1);
    }

    // ===test cases:===
    void 
    Test(Node** pnode, Node* z)
    {
        // ---1. walk
        // MidWalk(pnode);
        // preWalkIter(pnode);
        // MidWalkIter(pnode);
        // postWalkIter(pnode);
        
        //--- 2. find
        /*
        Node* result = tree_search(pnode, 5);
        if (result)
            printf("found");
        else
            printf("not found");
        */

        /*
        Node* result = tree_maximum(pnode);
        // Node* result = tree_minimum(pnode);
        if (result)
            printf("found: %d", result->key );
        else
            printf("not found");
        */

        /*
        Node* result = tree_predecessor(pnode);
        //Node* result = tree_successor(pnode);
        if (result)
            printf("found successor: %d", result->key);
        else
            printf("not found successor:");
        */
        
        //--- 3. insert / delete
        //Node* pnode_new = createNode(8);
        //tree_insert(pnode, pnode_new);

        tree_delete(pnode, z);
        //--- 4. depth

        printf("\n");
    }

    void 
    Test_tree_depth(Node* proot, 
                    int          expected_result)
    {
        int result = tree_depth(proot);

        if(expected_result == result)
            printf("Test passed.\n");
        else
            printf("Test failed.\n");
    }

    //           5
    //         /   \
    //        2     6
    //       /\      \
    //      1  4      7
    //        /
    //       3
    void Test1()
    {
        printf("Test1 begins.\n");

        Node* pnode1 = createNode(5);
        Node* pnode2 = createNode(2);
        Node* pnode3 = createNode(6);
        Node* pnode4 = createNode(1);
        Node* pnode5 = createNode(4);
        Node* pnode6 = createNode(7);
        Node* pnode7 = createNode(3);

        connectNodes(pnode1, pnode2, pnode3);
        connectNodes(pnode2, pnode4, pnode5);
        connectNodes(pnode3, NULL, pnode6);
        connectNodes(pnode5, pnode7, NULL);

        //Test(pnode5);
        //Test(pnode7);
        Test(&pnode1, pnode2);

        printTree(pnode1);
        freeTree(pnode1);
    }

    //           5
    //          /
    //        4
    //       /
    //      3
    //     /
    //    2
    //   /
    //  1
    void Test2_left_list()
    {
        printf("Test2_left_list begins.\n");

        Node* pnode1 = createNode(5);
        Node* pnode2 = createNode(4);
        Node* pnode3 = createNode(3);
        Node* pnode4 = createNode(2);
        Node* pnode5 = createNode(1);

        connectNodes(pnode1, pnode2, NULL);
        connectNodes(pnode2, pnode3, NULL);
        connectNodes(pnode3, pnode4, NULL);
        connectNodes(pnode4, pnode5, NULL);

        Test(&pnode1, pnode3);

        printTree(pnode1);

        freeTree(pnode1);
    }

    void Test3_only_one_node()
    {
        printf("Test4_only_one_node begins.\n");

        Node* pnode1 = createNode(1);
        
        Test(&pnode1, pnode1);
        printTree(pnode1);
        freeTree(pnode1);
    }

    void Test4_empty_tree()
    {
        printf("Test5_empty_tree begins.\n");

        //Test(NULL);
    }

    int main()
    {
        Test1();
        Test2_left_list();
        Test3_only_one_node();
        Test4_empty_tree();

        return 0;
    }