利用一维数组构造二叉树
定义结构体
typedef struct TreeNode{
int data;
struct TreeNode *lChild, *rChild;
} TreeNode, *BinaryTree;
创建结点
TreeNode *newTreeNode(int data){
auto node = new TreeNode;
node->data = data;
node->lChild = node->rChild = NULL;
return node;
}
构造二叉树
若从0开始编号,结点i的左孩子序号为2 i + 1,右孩子序号为2 i + 2
BinaryTree BinaryTreeBuilder(int arr[], BinaryTree &root, int i, int n){
if (i < n){
root = newTreeNode(arr[i]);
BinaryTreeBuilder(arr, root->lChild, 2 * i + 1, n);
BinaryTreeBuilder(arr, root->rChild, 2 * i + 2, n);
}
return root;
}
中序遍历
void inOrder(BinaryTree root){
if (root){
inOrder(root->lChild);
cout << root->data << " ";
inOrder(root->rChild);
}
}
main函数
int main(){
BinaryTree root;
int arr[] = {1, 2, 3, 4, 5, 6, 6, 6, 6};
int len = sizeof(arr) / sizeof(int);
BinaryTreeBuilder(arr, root, 0, len);
inOrder(root);
}
本作品采用《CC 协议》,转载必须注明作者和本文链接