树

admin管理员组

文章数量:1026989

树

1. 根据先序序列创建树
2. 先序后序序列创建树
3. 后序中序序列创建树

二叉树节点的结构体如下：

typedef char ElemType;
typedef struct Node
{ElemType val;Node* lTree;Node* rTree;
}Node;

1、根据先序序列创建树

只通过先序序列创建二叉树，序列必须是满二叉树的形式，因此没有元素的节点必须用特殊字符补齐，例如:"#"。

思路：

• 首先申请节点存放当前元素。
• 递归创建左子树
• 递归创建右子树

代码如下：
 

Node* PreCreate(ElemType* &str)
{Node *s = NULL;while (*str != '#'){s = BuyNode();s->val = *str;s->lTree = PreCreate(++str);s->rTree = PreCreate(++str);}return s;
}

注意：形参必须传地址的引用，否则递归过程总对指针的++操作会无效。

2、先序中序序列创建树

思路：

• 先序序列的第一个节点为根节点
• 在中序序列找根节点的位置，该位置左边即为左子树的节点，右边为右子树的节点。
• 递归创建左子树和右子树

代码如下：
 

int FindPos(ElemType* in, ElemType val, int n)
{int pos = -1;for (int i = 0; i < n; i++){if (in[i] == val){pos = i;}}return pos;
}
Node* PreInCreate(ElemType* pre, ElemType* in, int n)
{Node* s = NULL;//先序序列第一个结点为根节点if (n > 0){s = BuyNode();s->val = pre[0];//在中序序列中找到根节点的位置int pos = FindPos(in, pre[0], n);if (pos == -1){cout << "输入错误" << endl;exit(1);}s->lTree = PreInCreate(pre + 1, in, pos);s->rTree = PreInCreate(pre + pos + 1, in + pos + 1, n - pos - 1);}return s;
}
Node* CreatePI(ElemType* pre, ElemType* in, int n)
{if (pre == NULL || in == NULL || n < 1){return NULL;}else{return PreInCreate(pre, in, n);}
}

3、后序中序序列创建树

思路：

• 后序序列的最后一个元素为根节点
• 在中序序列中找到根节点位置，则该位置左边为左子树所有节点，右边为右子树所有节点。
• 递归创建左子树和右子树

代码如下:
 

Node* InPastCreate(ElemType* in, ElemType* l, int n)
{Node* s = NULL;if (n > 0){s = BuyNode();//后序序列中最后一个结点为根节点s->val = l[n - 1];//在中序序列中找到根节点的位置int pos = FindPos(in, l[n - 1], n);s->lTree = InPastCreate(in, l, pos);s->rTree = InPastCreate(in + pos + 1, l + pos, n - pos - 1);}return s;
}
Node* CreateIL(ElemType* in, ElemType* l, int n)
{if (in == NULL || l == NULL || n < 1){return NULL;}else{return InPastCreate(in, l, n);}
}

 

树

1. 根据先序序列创建树
2. 先序后序序列创建树
3. 后序中序序列创建树

二叉树节点的结构体如下：

typedef char ElemType;
typedef struct Node
{ElemType val;Node* lTree;Node* rTree;
}Node;

1、根据先序序列创建树

只通过先序序列创建二叉树，序列必须是满二叉树的形式，因此没有元素的节点必须用特殊字符补齐，例如:"#"。

思路：

• 首先申请节点存放当前元素。
• 递归创建左子树
• 递归创建右子树

代码如下：
 

Node* PreCreate(ElemType* &str)
{Node *s = NULL;while (*str != '#'){s = BuyNode();s->val = *str;s->lTree = PreCreate(++str);s->rTree = PreCreate(++str);}return s;
}

注意：形参必须传地址的引用，否则递归过程总对指针的++操作会无效。

2、先序中序序列创建树

思路：

• 先序序列的第一个节点为根节点
• 在中序序列找根节点的位置，该位置左边即为左子树的节点，右边为右子树的节点。
• 递归创建左子树和右子树

代码如下：
 

int FindPos(ElemType* in, ElemType val, int n)
{int pos = -1;for (int i = 0; i < n; i++){if (in[i] == val){pos = i;}}return pos;
}
Node* PreInCreate(ElemType* pre, ElemType* in, int n)
{Node* s = NULL;//先序序列第一个结点为根节点if (n > 0){s = BuyNode();s->val = pre[0];//在中序序列中找到根节点的位置int pos = FindPos(in, pre[0], n);if (pos == -1){cout << "输入错误" << endl;exit(1);}s->lTree = PreInCreate(pre + 1, in, pos);s->rTree = PreInCreate(pre + pos + 1, in + pos + 1, n - pos - 1);}return s;
}
Node* CreatePI(ElemType* pre, ElemType* in, int n)
{if (pre == NULL || in == NULL || n < 1){return NULL;}else{return PreInCreate(pre, in, n);}
}

3、后序中序序列创建树

思路：

• 后序序列的最后一个元素为根节点
• 在中序序列中找到根节点位置，则该位置左边为左子树所有节点，右边为右子树所有节点。
• 递归创建左子树和右子树

代码如下:
 

Node* InPastCreate(ElemType* in, ElemType* l, int n)
{Node* s = NULL;if (n > 0){s = BuyNode();//后序序列中最后一个结点为根节点s->val = l[n - 1];//在中序序列中找到根节点的位置int pos = FindPos(in, l[n - 1], n);s->lTree = InPastCreate(in, l, pos);s->rTree = InPastCreate(in + pos + 1, l + pos, n - pos - 1);}return s;
}
Node* CreateIL(ElemType* in, ElemType* l, int n)
{if (in == NULL || l == NULL || n < 1){return NULL;}else{return InPastCreate(in, l, n);}
}

 

本文标签： 树