c语言的二叉树和python,重建二叉树（C++和Python实现）

(说明：本博客中的题目、题目详细说明及参考代码均摘自 “何海涛《剑指Offer：名企面试官精讲典型编程题》2012年”)

题目

输入某二叉树前序遍历和中序遍历结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

进一步详细说明：

例如输入前序遍历序列 {1, 2, 4, 7, 3, 5, 6, 8} 和 中序遍历序列 {4, 7, 2, 1, 5, 3, 8, 6}， 则重建出图2.6所示的二叉树并输出它的头结点。二叉树结点的定义如下：

structBinaryTreeNode

{intm_nValue;

BinaryTreeNode*m_pLeft;

BinaryTreeNode*m_pRight;

};

算法设计思想

前序遍历序列的第一个元素为根结点的值，然后在中序遍历序列中寻找根节点的值的位置(索引)。

从中序遍历序列的起始位置到根结点的值的位置(不包含)为根结点左子树的中序遍历序列；从中序遍历序列的根结点的值的位置(不包含)到结束位置为根结点右子树的中序遍历序列；相应的，从前序遍历序列的第二个元素开始的根结点左子树结点数个元素的子序列为根结点左子树的前序遍历序列，从下一个元素开始，直到结束位置的子序列为根结点右子树的前序遍历序列。如图 2.7 所示，

C++ 实现

#include #include //exit()

structBinaryTreeNode

{intm_nValue;

BinaryTreeNode*m_pLeft;

BinaryTreeNode*m_pRight;

};

BinaryTreeNode* ConstructCore(int* preorderSta, int* preorderEnd, int* inorderSta, int*inorderEnd)

{//Create binary tree root node

BinaryTreeNode* root = newBinaryTreeNode;

root->m_nValue = *preorderSta;

root->m_pLeft = root->m_pRight =NULL;//Base condition

if (preorderSta ==preorderEnd)

{if (inorderSta == inorderEnd && *preorderSta == *inorderSta) // 易漏点returnroot;else{

printf("Invalid input: line %d in Function %s.", __LINE__, __func__);

exit(-1);

}

}//Find root node position in in-order sequence

int* rootInorder =inorderSta;while (rootInorder < inorderEnd && *rootInorder != *preorderSta) // 易错点，注意比较符号，没有等号。++rootInorder;if (rootInorder == inorderEnd && *rootInorder != *preorderSta) { // 易漏点

printf("Invalid input: line %d in Function %s.", __LINE__, __func__);

exit(-1);

}//Construct left subtree

if (rootInorder >inorderSta)

root->m_pLeft = ConstructCore(preorderSta+1, preorderSta+(rootInorder-inorderSta), inorderSta, rootInorder-1);//Construct right subtree

if (rootInorder

root->m_pRight = ConstructCore(preorderSta+(rootInorder-inorderSta)+1, preorderEnd, rootInorder+1, inorderEnd);returnroot;

}//Re-construct the binary tree, then return the root node pointer

BinaryTreeNode* Construct(int* preorder, int* inorder, intnodesNum)

{if (preorder == NULL || inorder == NULL || nodesNum <= 0) // 易漏点returnNULL;return ConstructCore(preorder, preorder+nodesNum-1, inorder, inorder+nodesNum-1);

}//Destroy Binary Tree

void destroyBinaryTree(BinaryTreeNode* &root)

{if (root !=NULL) // 易漏点

{//Postorder traversalif (root->m_pLeft !=NULL)

destroyBinaryTree(root->m_pLeft);if (root->m_pRight !=NULL)

destroyBinaryTree(root->m_pRight);deleteroot;

root=NULL; // 易漏点

}

}//Print binary tree elements in post-traversal

void printBinaryTree(const BinaryTreeNode*root)

{if(root) // 易漏点

{

printBinaryTree(root->m_pLeft);

printBinaryTree(root->m_pRight);

printf("%d,", root->m_nValue);

}

}voidunitest()

{int preorderArr[] = {1, 2, 4, 7, 3, 5, 6, 8};int inorderArr[] = {4, 7, 2, 1, 5, 3, 8, 6};int nodesNum = sizeof(preorderArr)/sizeof(preorderArr[0]);//Re-construct Binary tree from preorder sequence and inorder sequence

BinaryTreeNode* root =Construct(preorderArr, inorderArr, nodesNum);//Print Binary Tree

printBinaryTree(root);//Destroy Binary Tree

destroyBinaryTree(root);

}intmain()

{

unitest();return 0;

}

Python 实现

#!/usr/bin/python#-*- coding: utf8 -*-

classBinaryTreeNode:def __init__(self, value, left_node=None, right_node=None):

self.value=value

self.left_node=left_node

self.right_node=right_nodedefprint_binarytree_postorder(head):ifhead:

print_binarytree_postorder(head.left_node)

print_binarytree_postorder(head.right_node)print "%d," %head.value,defconstruct(preorder, inorder, nodes_num):if (preorder is None) or (inorder is None) or (nodes_num <=0):returnNonereturn construct_core(preorder, 0, nodes_num-1, inorder, 0, nodes_num-1)defconstruct_core(preorder, start_index_preorder, end_index_preorder,

inorder, start_index_inorder, end_index_inorder):#Create root node

root =BinaryTreeNode(preorder[start_index_preorder])#Base condition

if start_index_preorder ==end_index_preorder:if (start_index_inorder == end_index_inorder) and (preorder[start_index_preorder] ==inorder[start_index_inorder]):returnrootelse:print "Invalid input!"exit(-1)#Recursive condition

root_index_inorder =start_index_inorderwhile (root_index_inorder < end_index_inorder) and (inorder[root_index_inorder] !=preorder[start_index_preorder]):

root_index_inorder+= 1

if (root_index_inorder == end_index_inorder) and (inorder[root_index_inorder] !=preorder[start_index_preorder]):print "Invalid input!"exit(-1)#Construct left subtree

if root_index_inorder >start_index_inorder:

root.left_node= construct_core(preorder, start_index_preorder+1, start_index_preorder+root_index_inorder-start_index_inorder,

inorder, start_index_inorder, root_index_inorder-1)#Construct right subtree

if root_index_inorder

root.right_node= construct_core(preorder, start_index_preorder+root_index_inorder-start_index_inorder+1, end_index_preorder,

inorder, root_index_inorder+1, end_index_inorder)returnrootdefunitest():

preorder_list= [1, 2, 4, 7, 3, 5, 6, 8]

inorder_list= [4, 7, 2, 1, 5, 3, 8, 6]#Reconstruct binary tree, then return root node

root_binarytree =construct(preorder_list, inorder_list, len(preorder_list))#Print Binary Tree

print_binarytree_postorder(root_binarytree)if __name__ == '__main__':

unitest()

参考代码

1. targetver.h (06_ConstructBinaryTree/ 目录)

#pragma once

//The following macros define the minimum required platform. The minimum required platform//is the earliest version of Windows, Internet Explorer etc. that has the necessary features to run//your application. The macros work by enabling all features available on platform versions up to and//including the version specified.//Modify the following defines if you have to target a platform prior to the ones specified below.//Refer to MSDN for the latest info on corresponding values for different platforms.

#ifndef _WIN32_WINNT //Specifies that the minimum required platform is Windows Vista.

#define _WIN32_WINNT 0x0600 //Change this to the appropriate value to target other versions of Windows.

#endif

View Code

2. stdafx.h (06_ConstructBinaryTree/ 目录)

//stdafx.h : include file for standard system include files,//or project specific include files that are used frequently, but//are changed infrequently//

#pragma once#include"targetver.h"#include#include

//TODO: reference additional headers your program requires here

View Code

3. stdafx.cpp (06_ConstructBinaryTree/ 目录)

//stdafx.cpp : source file that includes just the standard includes//ConstructBinaryTree.pch will be the pre-compiled header//stdafx.obj will contain the pre-compiled type information

#include"stdafx.h"

//TODO: reference any additional headers you need in STDAFX.H//and not in this file

View Code

4. ConstructBinaryTree.cpp

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

//《剑指Offer——名企面试官精讲典型编程题》代码//著作权所有者：何海涛

#include"stdafx.h"#include"..UtilitiesBinaryTree.h"#includeBinaryTreeNode* ConstructCore(int* startPreorder, int* endPreorder, int* startInorder, int*endInorder);

BinaryTreeNode* Construct(int* preorder, int* inorder, intlength)

{if(preorder == NULL || inorder == NULL || length <= 0)returnNULL;return ConstructCore(preorder, preorder + length - 1,

inorder, inorder+ length - 1);

}

BinaryTreeNode*ConstructCore

(int* startPreorder, int*endPreorder,int* startInorder, int*endInorder

)

{//前序遍历序列的第一个数字是根结点的值

int rootValue = startPreorder[0];

BinaryTreeNode* root = newBinaryTreeNode();

root->m_nValue =rootValue;

root->m_pLeft = root->m_pRight =NULL;if(startPreorder ==endPreorder)

{if(startInorder == endInorder && *startPreorder == *startInorder)returnroot;else

throw std::exception("Invalid input.");

}//在中序遍历中找到根结点的值

int* rootInorder =startInorder;while(rootInorder <= endInorder && *rootInorder !=rootValue)++rootInorder;if(rootInorder == endInorder && *rootInorder !=rootValue)throw std::exception("Invalid input.");int leftLength = rootInorder -startInorder;int* leftPreorderEnd = startPreorder +leftLength;if(leftLength > 0)

{//构建左子树

root->m_pLeft = ConstructCore(startPreorder + 1, leftPreorderEnd,

startInorder, rootInorder- 1);

}if(leftLength < endPreorder -startPreorder)

{//构建右子树

root->m_pRight = ConstructCore(leftPreorderEnd + 1, endPreorder,

rootInorder+ 1, endInorder);

}returnroot;

}//====================测试代码====================

void Test(char* testName, int* preorder, int* inorder, intlength)

{if(testName !=NULL)

printf("%s begins:", testName);

printf("The preorder sequence is:");for(int i = 0; i < length; ++i)

printf("%d", preorder[i]);

printf("");

printf("The inorder sequence is:");for(int i = 0; i < length; ++i)

printf("%d", inorder[i]);

printf("");try{

BinaryTreeNode* root =Construct(preorder, inorder, length);

PrintTree(root);

DestroyTree(root);

}catch(std::exception&exception)

{

printf("Invalid Input.");

}

}//普通二叉树//1/2 3/// ///4 5 6/7 8

voidTest1()

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

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

}//所有结点都没有右子结点//1/2/3/4/5

voidTest2()

{const int length = 5;int preorder[length] = {1, 2, 3, 4, 5};int inorder[length] = {5, 4, 3, 2, 1};

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

}//所有结点都没有左子结点//12345

voidTest3()

{const int length = 5;int preorder[length] = {1, 2, 3, 4, 5};int inorder[length] = {1, 2, 3, 4, 5};

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

}//树中只有一个结点

voidTest4()

{const int length = 1;int preorder[length] = {1};int inorder[length] = {1};

Test("Test4", preorder, inorder, length);

}//完全二叉树//1/2 3/// ///4 5 6 7

voidTest5()

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

Test("Test5", preorder, inorder, length);

}//输入空指针

voidTest6()

{

Test("Test6", NULL, NULL, 0);

}//输入的两个序列不匹配

voidTest7()

{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("Test7: for unmatched input", preorder, inorder, length);

}int _tmain(int argc, _TCHAR*argv[])

{

Test1();

Test2();

Test3();

Test4();

Test5();

Test6();

Test7();return 0;

}

View Code

5. targetver.h (Utilities/ 目录)

#pragma once

//The following macros define the minimum required platform. The minimum required platform//is the earliest version of Windows, Internet Explorer etc. that has the necessary features to run//your application. The macros work by enabling all features available on platform versions up to and//including the version specified.//Modify the following defines if you have to target a platform prior to the ones specified below.//Refer to MSDN for the latest info on corresponding values for different platforms.

#ifndef WINVER //Specifies that the minimum required platform is Windows Vista.

#define WINVER 0x0600 //Change this to the appropriate value to target other versions of Windows.

#endif#ifndef _WIN32_WINNT//Specifies that the minimum required platform is Windows Vista.

#define _WIN32_WINNT 0x0600 //Change this to the appropriate value to target other versions of Windows.

#endif#ifndef _WIN32_WINDOWS//Specifies that the minimum required platform is Windows 98.

#define _WIN32_WINDOWS 0x0410 //Change this to the appropriate value to target Windows Me or later.

#endif#ifndef _WIN32_IE//Specifies that the minimum required platform is Internet Explorer 7.0.

#define _WIN32_IE 0x0700 //Change this to the appropriate value to target other versions of IE.

#endif

View Code

6. stdafx.h (Utilities/ 目录)

//stdafx.h : include file for standard system include files,//or project specific include files that are used frequently, but//are changed infrequently//

#pragma once#include"targetver.h"

#define WIN32_LEAN_AND_MEAN //Exclude rarely-used stuff from Windows headers

//Windows Header Files:

#include #include

//TODO: reference additional headers your program requires here

View Code

7. stdafx.cpp (Utilities/ 目录)

//stdafx.cpp : source file that includes just the standard includes//Utilities.pch will be the pre-compiled header//stdafx.obj will contain the pre-compiled type information

#include"stdafx.h"

//TODO: reference any additional headers you need in STDAFX.H//and not in this file

View Code

8. BinaryTree.h

//《剑指Offer——名企面试官精讲典型编程题》代码//著作权所有者：何海涛

#pragma once

structBinaryTreeNode

{intm_nValue;

BinaryTreeNode*m_pLeft;

BinaryTreeNode*m_pRight;

};

__declspec( dllexport ) BinaryTreeNode* CreateBinaryTreeNode(intvalue);

__declspec( dllexport )void ConnectTreeNodes(BinaryTreeNode* pParent, BinaryTreeNode* pLeft, BinaryTreeNode*pRight);

__declspec( dllexport )void PrintTreeNode(BinaryTreeNode*pNode);

__declspec( dllexport )void PrintTree(BinaryTreeNode*pRoot);

__declspec( dllexport )void DestroyTree(BinaryTreeNode* pRoot);

View Code

9. BinaryTree.cpp

//《剑指Offer——名企面试官精讲典型编程题》代码//著作权所有者：何海涛

#include"StdAfx.h"#include"BinaryTree.h"BinaryTreeNode* CreateBinaryTreeNode(intvalue)

{

BinaryTreeNode* pNode = newBinaryTreeNode();

pNode->m_nValue =value;

pNode->m_pLeft =NULL;

pNode->m_pRight =NULL;returnpNode;

}void ConnectTreeNodes(BinaryTreeNode* pParent, BinaryTreeNode* pLeft, BinaryTreeNode*pRight)

{if(pParent !=NULL)

{

pParent->m_pLeft =pLeft;

pParent->m_pRight =pRight;

}

}void PrintTreeNode(BinaryTreeNode*pNode)

{if(pNode !=NULL)

{

printf("value of this node is: %d", pNode->m_nValue);if(pNode->m_pLeft !=NULL)

printf("value of its left child is: %d.", pNode->m_pLeft->m_nValue);elseprintf("left child is null.");if(pNode->m_pRight !=NULL)

printf("value of its right child is: %d.", pNode->m_pRight->m_nValue);elseprintf("right child is null.");

}else{

printf("this node is null.");

}

printf("");

}void PrintTree(BinaryTreeNode*pRoot)

{

PrintTreeNode(pRoot);if(pRoot !=NULL)

{if(pRoot->m_pLeft !=NULL)

PrintTree(pRoot->m_pLeft);if(pRoot->m_pRight !=NULL)

PrintTree(pRoot->m_pRight);

}

}void DestroyTree(BinaryTreeNode*pRoot)

{if(pRoot !=NULL)

{

BinaryTreeNode* pLeft = pRoot->m_pLeft;

BinaryTreeNode* pRight = pRoot->m_pRight;deletepRoot;

pRoot=NULL;

DestroyTree(pLeft);

DestroyTree(pRight);

}

}

View Code

10. 参考代码下载

项目 06_ConstructBinaryTree 下载： 百度网盘

何海涛《剑指Offer：名企面试官精讲典型编程题》 所有参考代码下载：百度网盘

参考资料

[1]  何海涛. 剑指 Offer：名企面试官精讲典型编程题 [M]. 北京：电子工业出版社，2012. 53-58.