请问下题的思路:设中序线索二叉树的类型为TBTNode* InThTree 设计算法,在一棵中序

请问下题的思路:设中序线索二叉树的类型为TBTNode* InThTree 设计算法,在一棵中序
请问下题的思路:
设中序线索二叉树的类型为TBTNode* InThTree
设计算法,在一棵中序线索二叉树中寻找结点t的子树上中序最后一个结点.
谁能理解oo 1年前 已收到1个回答 举报

88kky 幼苗

共回答了16个问题采纳率:81.3% 举报

一种方法是先求出以节点t为根节点的树的结点个数 设节点个数为n 然后中序遍历的时候 每访问一个数 则访问数+1 一直访问到n则该节点即中序遍历最后一个节点

1年前 追问

2

谁能理解oo 举报

是一种解答。但在求出n的时候就需要遍历一遍,在遍历的时候需要有终止遍历的条件,而这一点又恰好与中序遍历最后一个结点有关。所以理论上可行但实际上有些不便。

谁能理解oo 举报

我的想法是,根据中序遍历二叉树的特点,最后一个结点就是结点t的右方向上最末尾的结点,如果t的右子树不存在,则末尾结点即为t本身

举报 88kky

其实我那个方法操作也是简单的 但是我认为这个和遍历的终止条件没关系 因为在遍历的终止条件满足之前 肯定能够找到需要的结点的


大概要写的话就这样子:

Node * BinaryTree::find(Node *t) const
{
static Node *p = NULL;
static int n = total_jiedian(t);
static int i = 0;
if(t != NULL)
{
find(t->left);
cout << t->elem << endl;
++i;
if(i == n)
{
p = t;
}
find(t->right);
}
return p;
}

不过你的方法确实可行 应该是最简单的了 抓住了题目的规律 !

可能相似的问题
Copyright © 2024 YULUCN.COM - 雨露学习互助 - 17 q. 0.020 s. - webmaster@yulucn.com