共计 1980 个字符,预计需要花费 5 分钟才能阅读完成。
首先数组递归版
struct Node
{
int val;
int l;
int r;
Node(int V,int L ,int R):val(V),l(L),r(R){};}node[2005];
int insert(int val, int x){if (x==0)
{
cnt++;
x = cnt;
node[x].val = val;
node[x].l = node[x].r = 0;
return x;
}
if(val<node[x].val){node[x].l=insert(val, node[x].l);
// 标记行
}
else {node[x].r = insert(val, node[x].r);
// 标记行
}
return x;// 标记行 2
}
/* 此处保留一个疑问:当标记行 2 的语句放在俩标记行位置时和上述语句的执行效果会有区别吗?
当然也可借鉴下面这一套二叉搜索树模板(由于需求问题未完全实现)*/
struct TreeNode
{
int key;
TreeNodePosion p;
TreeNodePosion l;
TreeNodePosion r;
TreeNode(int val) :key(val), l(NULL), r(NULL), p(NULL) {};};
struct Tree
{TreeNodePosion root;};
TreeNodePosion tree_search(TreeNodePosion x, int k) {if (x == NULL || x->key == k)return x;
if (x->key < k)tree_search(x->l, k);
if (x->key > k)tree_search(x->r, k);
}
TreeNodePosion find_max(TreeNodePosion x) {while ((x->r) != NULL)x = x->r;
return x;
}
TreeNodePosion find_min(TreeNodePosion x) {while ((x->l) != NULL)x = x->l;
return x;
}
TreeNodePosion find_succ(TreeNodePosion x) {if (x->r != NULL)return find_min(x->r);
TreeNodePosion p = x->p;
TreeNodePosion y = x;
while (p != NULL)
{if (p->l == y)break;
y = p;
p = p->p;
}
return p;
}
TreeNodePosion find_pre(TreeNodePosion x) {if (x->l != NULL)return find_max(x->l);
TreeNodePosion p = x->p;
TreeNodePosion y = x;
while (p != NULL)
{if (p->r == y)break;
y = p;
p = p->p;
}
return p;
}
void insert(TreeNodePosion& root, int k) {if (root == NULL) {root = new TreeNode(k); return; }
TreeNodePosion tem = root;
TreeNodePosion tem1 = tem;
while (tem != NULL)
{
tem1 = tem;
if (tem->key > k) {tem = tem->l;}
else if (tem->key < k) {tem = tem->r;}
else
{return;};
}
TreeNodePosion new_node = new TreeNode(k);
new_node->p = tem1;
if (k < tem1->key) {tem1->l = new_node;}
else if (k > tem1->key) {tem1->r = new_node;}
}
void pre_order(TreeNodePosion p) {if (p != NULL)
{
cout << p->key << ' ';
pre_order(p->l);
pre_order(p->r);
}
}
void in_order(TreeNodePosion p) {if (p != NULL) {in_order(p->l);
cout << p->key << ' ';
in_order(p->r);
}
}
void post_order(TreeNodePosion p) {if (p != NULL) {post_order(p->l);
post_order(p->r);
cout << p->key << ' ';
}
}
int main() {ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n; TreeNodePosion root = NULL;
cin >> n; int k;
while (n--)
{
cin >> k;
insert(root, k);
}
pre_order(root); cout << '\n';
post_order(root);
return 0;
}
正文完