輸入前序周遊和中序周遊輸出後序周遊——在構樹和不構樹兩種情況下輸出結果

#include<iostream>

using namespace std;

struct BinaryTreeNode

{

int m_nvalue;

BinaryTreeNode *m_pLeft;

BinaryTreeNode *m_pRigt;

};

BinaryTreeNode* ConstructCore(int *startpreorder, int *endpreorder, int *startinorder, int *endinorder)

{

//if (startpreorder == endpreorder)

//return startpreorder;

BinaryTreeNode *p = new BinaryTreeNode;

p->m_nvalue = startpreorder[0];

p->m_pLeft = NULL;

p->m_pRigt = NULL;

if (startpreorder == endpreorder)

return p;

int i = 0;

while (1)

{

if (startpreorder[0] == startinorder[i])

break;

else

++i;

}

if (i > 0)

p->m_pLeft = ConstructCore(startpreorder + 1, startpreorder + i, startinorder, startinorder + i-1);

if (i < endpreorder - startpreorder)

p->m_pRigt = ConstructCore(startpreorder + i + 1, endpreorder, startinorder + i + 1, endinorder);

return p;

}

BinaryTreeNode* 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);

}

//後序周遊列印二叉樹

void LastCout(BinaryTreeNode *root)

{

if (root == NULL)

return;

LastCout(root->m_pLeft);

LastCout(root->m_pRigt);

cout << root->m_nvalue << " ";

}

void ACore(int *startpreorder, int *endpreorder, int *startinorder, int *endinorder)

{

if (startpreorder == endpreorder)

{

cout << startinorder[0] << " ";

return;

}

int i = 0;

while (1)

{

if (startpreorder[0] == startinorder[i])

break;

else

++i;

}

if (i > 0)

ACore(startpreorder + 1, startpreorder + i, startinorder, startinorder + i - 1);

if (i < endpreorder - startpreorder)

ACore(startpreorder + i + 1, endpreorder, startinorder + i + 1, endinorder);

cout << startpreorder[0] << " ";

}

// 輸入前序周遊和中序周遊 輸出後序周遊（前提 數組中數不能相等）

void A(int *preorder, int *inorder, int length)

{

if (preorder == NULL || inorder == NULL || length <= 0)

return;

else

ACore(preorder, preorder + length - 1, inorder, inorder + length - 1);

}

int main()

{

int preorder[] = { 1, 2, 4, 5, 6, 7, 3 };

int inorder[] = { 4, 2, 6, 5, 7, 1, 3 };

const int length = sizeof(preorder) / sizeof(preorder[0]);

BinaryTreeNode *p = Construct(preorder, inorder, length);  //先構樹 再輸出後序周遊

LastCout(p);

cout << endl;

A(preorder, inorder, length); //直接輸出後序周遊

cout << endl;

return 0;

}