以二叉链表表示二叉树,建立一棵二叉树
时间: 2023-03-21 19:03:04 浏览: 200
好的,我可以回答这个问题。以二叉链表表示二叉树,需要定义一个二叉树节点的结构体,结构体中包含三个成员变量,分别是数据域、左子树指针和右子树指针。建立二叉树的过程就是不断地创建新的节点,并将它们链接到已有的节点上,形成一个完整的二叉树结构。建立二叉树的具体方法可以使用递归或迭代的方式实现,这里以递归方式为例:
```
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
int inStart = 0;
int inEnd = inorder.size() - 1;
int postStart = 0;
int postEnd = postorder.size() - 1;
return buildTreeHelper(inorder, inStart, inEnd, postorder, postStart, postEnd);
}
TreeNode* buildTreeHelper(vector<int>& inorder, int inStart, int inEnd,
vector<int>& postorder, int postStart, int postEnd) {
if (inStart > inEnd || postStart > postEnd) {
return NULL;
}
int rootValue = postorder[postEnd];
TreeNode* root = new TreeNode(rootValue);
int rootIndex = -1;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == rootValue) {
rootIndex = i;
break;
}
}
int leftSubtreeSize = rootIndex - inStart;
root->left = buildTreeHelper(inorder, inStart, rootIndex - 1, postorder, postStart, postStart + leftSubtreeSize - 1);
root->right = buildTreeHelper(inorder, rootIndex + 1, inEnd, postorder, postStart + leftSubtreeSize, postEnd - 1);
return root;
}
```
以上是一个建立二叉树的示例代码,该代码使用了中序遍历和后序遍历的结果来建立二叉树。具体实现时,先根据后序遍历的结果确定根节点,然后根据中序遍历的结果将二叉树分为左子树和右子树,并递归地建立左子树和右子树。最终返回整个二叉树的根节点即可。
阅读全文