algorithm - 构造和打印二叉树（不平衡二叉树）的元素，从左到右，自下而上

Question

请让我知道如何实现以下目标：

我有一棵不平衡的二叉树，它同时具有左右子树。我必须按顺序打印该不平衡二叉树的节点值

(i) 从左到右，(ii) 从下到上，以及 (iii) 还将使用的数据结构及其内存管理或内存分配。

最初我的想法是，将进行级别顺序遍历，将元素排队，然后打印并取消排队队列。

非常感谢您对示例代码、伪代码、算法的帮助。

问候

Answer 1

这是使用 C++ 的不平衡二叉树的示例。每个节点携带的数据只是一个简单的整数值（连同左右子指针的管理数据和节点层级的深度）。

希望这显示了插入如何访问树中的节点，直到找到合适的位置将新节点插入树中。

左子树包含小于当前节点的值。因此，如果当前节点包含值 9，则该节点的左子树由值小于 9 的节点组成。

右子树包含大于当前节点的值。因此，如果当前节点包含值 9，则该节点的右子树由值大于 9 的节点组成。

当您访问每个节点时，如果您想找到一个大于当前节点值的值，则遍历右子树。如果要查找小于当前节点值的值，则遍历左子树。

// tree_data.cpp : Defines the entry point for the console application.
//

// VS2005 standard include for precompiled headers, etc.
#include "stdafx.h"

// C++ iostream header for standard output in namespace std::
#include <iostream>

// An unbalanced, ordered binary tree
// Left subtree are items less than the node value.
// Right subtree are items greater than the node value.

// The items are in order from left most leaf to the right most leaf
// however the left and right subtrees may be unbalanced meaning not the same
// depth depending on the order of inserts.  In other words if there are
// a large number of consecutive inserts with decreasing values the
// result will be a tree whose root is the first value inserted with a
// long left tree of decreasing values and no right hand tree at all.

struct TreeNode {
    TreeNode *pLeft;    // node that is less than the current node
    TreeNode *pRight;   // node that is greater than the current node
    int    iValue;      // value for this node
    int    iDepth;      // depth of this node in the tree, number of levels
};

typedef TreeNode *TreeHead;

const TreeHead emptyTree = 0;


// Since we use new to allocate tree nodes, the InsertNode () function could
// conceivably throw a memory allocation exception.
void InsertNode (int iValue, TreeHead &pTree)
{
    TreeNode TreeHeadInit = {emptyTree, emptyTree, iValue, 0};

    if (pTree == emptyTree) {
        // initialize the tree with this first item and return
        pTree = new TreeNode;
        *pTree = TreeHeadInit;
        return;
    }

    // Tree is not empty so lets find the place to put this new item to
    // be inserted.  We traverse the tree until we find the correct empty
    // spot in the tree and then we put it there.  If we come across the
    // value already in the tree then we do nothing and just return.
    TreeHead pTreeStruct = pTree;
    while (pTreeStruct != emptyTree) {
        // remember the depth of the current node as it will become the parent
        // node if we reach the outer most leaf and need to add a new node.
        TreeHeadInit.iDepth = pTreeStruct->iDepth;
        if (pTreeStruct->iValue == iValue) {
            // since we have found a node with the value specified then we
            // are done and we do nothing.
            return;  // do nothing
        } else  if (pTreeStruct->iValue < iValue) {
            if (pTreeStruct->pRight == emptyTree) {
                // we have reached the place where we need to add a new node to
                // extend the right tree with this greater value than the current
                // node contains.  allocate the node then break to initialize it.
                pTreeStruct = pTreeStruct->pRight = new TreeNode;
                break;
            }
            // the value to insert is greater than this node so we
            // traverse to the right where values greater than the
            // value of the current node are located.
            pTreeStruct = pTreeStruct->pRight;
        } else {
            if (pTreeStruct->pLeft == emptyTree) {
                // we have reached the place where we need to add a new node to
                // extend the left tree with this greater value than the current
                // node contains.  allocate the node then break to initialize it.
                pTreeStruct = pTreeStruct->pLeft = new TreeNode;
                break;
            }
            // the value to insert is less than this node so we
            // traverse to the left where values less than the
            // value of the current node are located.
            pTreeStruct = pTreeStruct->pLeft;
        }
    }

    // update this new node that has been added to the tree and
    // set its depth to be one more than the depth of its parent node.
    TreeHeadInit.iDepth++;
    *pTreeStruct = TreeHeadInit;
    return;
}

// print the tree starting with the lowest value to the highest value.
// for each node we want to print out the left item which is lower than
// the node's value and then the right item which is higher than the
// node's value.
void PrintTreeInOrder (TreeHead pTree)
{
    if (pTree != emptyTree) {
        PrintTreeInOrder (pTree->pLeft);
        std::cout << "  value " << pTree->iValue << " depth " << pTree->iDepth << std::endl;
        PrintTreeInOrder (pTree->pRight);
    }
}

// print the tree from the root element indenting the printed lines to give an
// idea as to a diagram of the tree and how the nodes are sequenced.
void PrintTreeInDepth (TreeHead pTree)
{
    if (pTree != emptyTree) {
        for (int i = 0; i < pTree->iDepth; i++) std::cout << "|..";
        std::cout << " value " << pTree->iValue << " depth " << pTree->iDepth;
        if (pTree->pLeft != emptyTree) {
            std::cout << " left " << pTree->pLeft->iValue << " ";
        } else {
            std::cout << " left NULL ";
        }
        if (pTree->pRight != emptyTree) {
            std::cout << " right " << pTree->pRight->iValue << " ";
        } else {
            std::cout << " right NULL ";
        }
        std::cout << std::endl;
        PrintTreeInDepth (pTree->pLeft);
        PrintTreeInDepth (pTree->pRight);
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    TreeHead myTree = emptyTree;

    // this is the first insert so will be the root of the unbalanced tree
    InsertNode (9, myTree);

    // now insert several items in decending order
    InsertNode (8, myTree);
    InsertNode (6, myTree);
    InsertNode (5, myTree);
    InsertNode (3, myTree);
    InsertNode (2, myTree);

    // now insert some other nodes haphazardly
    InsertNode (12, myTree);
    InsertNode (4, myTree);
    InsertNode (1, myTree);
    InsertNode (22, myTree);
    InsertNode (16, myTree);
    InsertNode (18, myTree);
    InsertNode (17, myTree);
    InsertNode (7, myTree);
    InsertNode (13, myTree);
    InsertNode (14, myTree);
    InsertNode (15, myTree);

    std::cout << "In order print" << std::endl;
    PrintTreeInOrder (myTree);
    std::cout << std::endl << std::endl;
    std::cout << "Depth diagram from Root using left traversal" << std::endl;
    PrintTreeInDepth (myTree);
    return 0;
}

插入节点后打印出树的 main 的输出如下所示。此输出首先显示按顺序遍历，它按从小到大的顺序列出节点的值。下一个输出给出了关于不平衡树结构的想法，显示了来自根元素的左子树如何比右子树更长并且具有更多级别。您还可以从第二组输出中看到哪个节点包含哪些值。例如，值为 6 的节点有一个值为 5 的节点作为其左子节点，并有一个值为 7 的节点作为其右子节点。

In order print
  value 1 depth 6
  value 2 depth 5
  value 3 depth 4
  value 4 depth 5
  value 5 depth 3
  value 6 depth 2
  value 7 depth 3
  value 8 depth 1
  value 9 depth 0
  value 12 depth 1
  value 13 depth 4
  value 14 depth 5
  value 15 depth 6
  value 16 depth 3
  value 17 depth 5
  value 18 depth 4
  value 22 depth 2


Depth diagram from Root using left traversal
 value 9 depth 0 left 8  right 12
|.. value 8 depth 1 left 6  right NULL
|..|.. value 6 depth 2 left 5  right 7
|..|..|.. value 5 depth 3 left 3  right NULL
|..|..|..|.. value 3 depth 4 left 2  right 4
|..|..|..|..|.. value 2 depth 5 left 1  right NULL
|..|..|..|..|..|.. value 1 depth 6 left NULL  right NULL
|..|..|..|..|.. value 4 depth 5 left NULL  right NULL
|..|..|.. value 7 depth 3 left NULL  right NULL
|.. value 12 depth 1 left NULL  right 22
|..|.. value 22 depth 2 left 16  right NULL
|..|..|.. value 16 depth 3 left 13  right 18
|..|..|..|.. value 13 depth 4 left NULL  right 14
|..|..|..|..|.. value 14 depth 5 left NULL  right 15
|..|..|..|..|..|.. value 15 depth 6 left NULL  right NULL
|..|..|..|.. value 18 depth 4 left 17  right NULL
|..|..|..|..|.. value 17 depth 5 left NULL  right NULL

Answer 2

看来你已经了解了算法。请记住，树是不平衡的，正常的递归实现可能会导致 StackOverflow。