結構和打印元件，從左至右，從下往上

Question

請讓我知道如何做到以下幾點：

我有一個二叉樹，這是不平衡，左邊的&右邊的子樹。我必須打印出從左至右的順序爲

（i）的數據結構的值，（ii）從下往上，（iii）從下往上數據結構的數值結構，以及（iii）將使用的數據結構其內存管理或內存分配。

最初我以爲是會進行層次順序遍歷，對元素進行排隊，然後打印和取消排隊隊列。

您對示例代碼，僞代碼，算法的幫助非常感謝。

Regards

Answer 1

這裏是一個使用C++的不平衡二叉樹的例子。每個節點 中攜帶的數據只是一個簡單的整數值（以及左右子指針的管理數據和節點級別的深度）。

希望這會顯示insert如何訪問樹中的節點，直到它找到將新節點插入樹中的適當位置。

左子樹包含的值小於當前節點。因此，如果當前節點包含值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; 
} 

從中插入節點之後打印出樹主輸出看起來像 以下。此輸出首先顯示按順序遍歷，其中按照從最小到最大的順序列出了 節點的值。下一個輸出提供了關於不平衡樹的結構 的想法，其示出了來自根元素的左子樹如何較長並且具有比右子樹更多數量的級別。您還可以從第二組輸出中看到哪個節點包含哪些值。例如，其值爲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。