大家好,又见面了,我是全栈君。
称号: 在队列中,队列给定二进制序列前导,这种二元结构。 例 前言: a b d c e f 后序: d b a e c f 使用递归实现例如以下:
#include<stdio.h>
#include<iostream>
using namespace std;
typedef struct tagNode{
tagNode* left;
tagNode* right;
char value;
} Node;
void rebuildtree(char* pPreOrder, char* pInOrder, int len, Node** root)
{
if(len <= 0) return;
//1: find root's value and create root Node
char chroot = *pPreOrder;
Node* pNode = new Node();
pNode->left = NULL;
pNode->right = NULL;
pNode->value = chroot;
*root = pNode;
if(len == 1) return;
//2: find root's left child and find right child
int i = 0;
while(i < len)
{
if(*(pInOrder + i) == chroot) break;
i ++;
}
if(i == len) return;
//leftchild
rebuildtree(pPreOrder+1, pInOrder, i, &((*root)->left));
//rightchild
rebuildtree(pPreOrder+i+1, pInOrder+i+1, len -i -1, &((*root)->right));
}
void printTree(Node* root)
{
if(root == NULL) return;
printTree(root->left);
printTree(root->right);
cout << root->value << ",";
}
int main()
{
char p1[7] = "abdcef";
char p2[7] = "dbaecf";
Node* root = NULL;
rebuildtree(p1, p2, 6, &root);
//end print tree
printTree(root);
getchar();
}
版权声明:本文博客原创文章,博客,未经同意,不得转载。
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/117422.html原文链接:https://javaforall.cn