网站人群分析,做搜索网站挣钱,免费制作软件的网站,门户网站系统开发BinaryTree要实现的方法
总结 remove不在BinNode里#xff0c;而是BinTree里 递归的两种写法 从上往下#xff1a;同一对象的递归#xff08;参数多一个#xff0c;判空用一句话#xff09;#xff0c;子对象的递归#xff08;参数void#xff0c;判空用两句话#…BinaryTree要实现的方法
总结 remove不在BinNode里而是BinTree里 递归的两种写法 从上往下同一对象的递归参数多一个判空用一句话子对象的递归参数void判空用两句话因为分叉所以递归是真递归 从下往上不分叉为了效率可以用循环
// 我的最初写法递归更新一条路径上的全部节点high值
template typename T
void BinNodeT::updateHigh(void)
{int oldHigh high;high std::max(getHigh(left), getHigh(right)) 1;if (parent ! NULL oldHigh ! high) parent-updateHigh();
}// 调用
rt-updateHigh();// 改良版循环更新一条路径上的全部节点high值
template typename T
void BinTreeT::updateHighAbove(BinNodeT * rt)
{while (rt){if (!rt-updateHigh()) break; //这是书里说的优化但书中并未实现rt rt-parent;}
}
template typename T
bool BinNodeT::updateHigh(void) //返回是否更新了树高
{int oldHigh high;high std::max(getHigh(left), getHigh(right)) 1;return oldHigh ! high;
}
// 调用
updateHighAbove(rt);整棵树与根节点的区别整棵树的类型是BinTree 而根节点的类型是BinNode。二者都有成员变量high和size改了根节点的size没改整棵树的size 发现high也有上一条的问题。书上BinTree没有设置highBinNode没有size那就删掉省的单独更新 为什么remove写两个因为切断来自parent的指针和更新高度不用层层进行还是为了提高效率。remove_core负责递归remove在最外层负责切断来自parent的指针和更新高度 remove如果rt是根节点那么不进行切断来自parent的指针和更新高度析构函数要用 静态成员函数可以不依附于具体对象来调用。为了调用时简洁。静态成员函数就很像是面向过程了
code BinNode
# pragma once
# include algorithm
# define getHigh(x) x ? x-high : -1// 仿函数打印功能
template typename T
struct print {void operator ()(T data){std::cout data std::endl;}
};template typename T
struct BinNode {int high;T data;BinNodeT * left;BinNodeT * right;BinNodeT * parent;int Size(BinNodeT * x){if (x){return 1 Size(x-left) Size(x-right);}return 0;}BinNode(T const d, BinNodeT * p) : data(d), parent(p), left(NULL), right(NULL), size(1), high(0) {}BinNodeT * insertAsLeft(T const val){left new BinNodeT(val, this);return left;}BinNodeT * insertAsRight(T const val){right new BinNodeT(val, this);return right;}bool updateHigh(void){int oldHigh high;high std::max(getHigh(left), getHigh(right)) 1;return oldHigh ! high;}template typename T2void travPre(T2 visit){visit(data);if (left) left-travPre(visit);if (right) right-travPre(visit);}template typename T2void travIn(T2 visit){if (left) left-travIn(visit);visit(data);if (right) right-travIn(visit);}template typename T2void travPost(T2 visit){if (left) left-travPost(visit);if (right) right-travPost(visit);visit(data);}
};code BinTree
# pragma once
# include BinNode.htemplate typename T
class BinTree
{
protected:
public:int size;BinNodeT * root;public:BinTree():size(0), root(NULL){}~BinTree() { if (root) remove(root); }//***********************************************************只读*********************************************************int Size(void) const { return size; }bool empty(void) const { return size 0; }BinNodeT * Root(void) const { return root; }//***********************************************************可写*********************************************************// 节点插入BinNodeT * insertAsRoot(T const e){size 1;root new BinNodeT(e, NULL);return root;}BinNodeT * insertAsLeft(T const e, BinNodeT * rt){size;rt-insertAsLeft(e);updateHighAbove(rt);return rt-left;}BinNodeT * insertAsRight(T const e, BinNodeT * rt){size;rt-insertAsRight(e);updateHighAbove(rt);return rt-right;}// 子树接入,返回接入位置rtBinNodeT * attachAsLeft(BinTreeT * newSubtree, BinNodeT * rt){size newSubtree-size;rt-left newSubtree-root;updateHighAbove(rt);// 清空newSubtree原来的东西newSubtree-size 0;newSubtree-root NULL;return rt;}BinNodeT * attachAsRight(BinNodeT * newSubtree, BinNodeT * rt){size newSubtree-size;rt-right newSubtree-root;updateHighAbove(rt);// 清空newSubtree原来的东西newSubtree-size 0;newSubtree-root NULL;return rt;}int remove(BinNodeT * rt){// 切断来自parent的指针fromParentTo(rt) NULL;// 更新高度updateHighAbove(rt-parent);int ans remove_core(BinNodeT * rt);size - ansreturn ans;}int remove_core(BinNodeT * rt){if (!rt) return 0; // 递归出口int ans remove(rt-left) remove(rt-right) 1;delete rt;return ans;}BinTreeT * secede(BinNodeT * rt) // 先不考虑 如果rt是树根{// 切断来自parent的指针fromParentTo(rt) NULL;size - BinNodeT::Size(rt);BinTreeT * newTree new BinTreeT();newTree-root rt;rt-parent NULL;updateHighAbove(rt-parent);return newTree;}void updateHighAbove(BinNodeT * rt){while (rt){if (!rt-updateHigh()) break;rt rt-parent;}}//***********************************************************遍历*********************************************************template typename T2void travPre(T2 visit){if (root) root-travPre(visit);}template typename T2void travIn(T2 visit){if (root) root-travIn(visit);}template typename T2void travPost(T2 visit){if (root) root-travPost(visit);}private:BinNodeT * fromParentTo(BinNodeT * x){if (x x-parent-left) return x-parent-left;else return x-parent-right;}
};测试程序树的结构如图 # include iostream
# include BinTree.hint main(void)
{BinTreechar T1;BinNodechar * pA T1.insertAsRoot(A);BinNodechar * pB T1.insertAsLeft(B, pA);BinNodechar * pG T1.insertAsLeft(G, pB);BinNodechar * pC T1.insertAsRight(C, pA);BinNodechar * pE T1.insertAsRight(E, pC);BinNodechar * pH T1.insertAsRight(H, pG);BinNodechar * pD T1.insertAsLeft(D, pC);BinNodechar * pF T1.insertAsLeft(F, pD);printint p;std::cout T1.Size() \n;// 高度测试std::cout 根高度; std::cout T1.Root()-high; std::cout \n;std::cout C高度; std::cout pC-high; std::cout \n;// 遍历测试std::cout 后序遍历; T1.travPost(p); std::cout \n;std::cout 中序遍历; T1.travIn(p); std::cout \n;// 移除测试std::cout 删掉 T1.remove(pD) 个节点 \n;std::cout C高度; std::cout pC-high; std::cout \n;std::cout 中序遍历; T1.travIn(p); std::cout \n;std::cout T1.Size() \n;// 切断测试BinTreechar * pT2 T1.secede(pC);std::cout 中序遍历T1; T1.travIn(p); std::cout \n;std::cout 中序遍历T2; pT2-travIn(p); std::cout \n;std::cout T1.Size() \n;std::cout pT2-Size() \n;return 0;
}输出
8
根高度3
C高度2
后序遍历H G B F D E C A
中序遍历G H B A F D C E
删掉2个节点
C高度1
中序遍历G H B A C E
6
中序遍历T1G H B A
中序遍历T2C E
4
2迭代遍历
上面的代码是递归的遍历。现在再写迭代的前序、中序、后序遍历。
尾递归
前序遍历的递归代码左右子树都属于尾递归。中序遍历的递归代码右子树属于尾递归。而后序遍历完全不属于尾递归。所以后序遍历比前、中序遍历复杂得多。要理解这句话还要先了解尾递归转成迭代的方法而这也是编译器在编译之前常做的优化手段。
以汉诺塔为例理解递归转迭代
BinTree 的三个遍历接口不变只需修改BinNode 的遍历函数。
travPre迭代1直接转化但不可推广到中、后序
仅说思路根节点进栈。当栈非空出栈访问然后右子树入栈左子树入栈。
这个完全模拟了尾递归时编译器的操作。至于为什么先右后左因为这样出栈时才能先左后右。
汉诺塔那篇文章如果你把结果打印出来发现迭代的结果跟递归结果是反过来的如果将入栈的两句话交换位置那么输出结果一模一样
travPre迭代2新思路可推广
我们通过仔细观察travPre得到前序遍历的迭代算法。 template typename T2void travPre(T2 visit){// 出栈访问visit(data);// 左侧链一路访问到底if (left) left-travPre(visit);// 每访问一个左孩子将对应右孩子进栈备用if (right) right-travPre(visit);}迭代2的算法 template typename T2void travPre2(T2 visit){// 出栈顶。右孩子进栈访问左孩子。转到左孩子重复上一步。直到没有左孩子出栈顶。BinNodeT * current;StackBinNodeT* s;s.push(this);while (!s.empty()){current s.pop(); while (current){visit(current-data);if (current-right) s.push(current-right);current current-left;}}}travIn迭代
按图索骥继续先观察递归算法 void travIn(T2 visit){// 沿左侧链一路向左进栈if (left) left-travIn(visit);// 没有左子树时出栈访问visit(data);// 访问完马上转到右儿子进一个栈if (right) right-travIn(visit);}travIn迭代算法 template typename T2void travIn2(T2 visit){// 左孩子进栈没有左孩子时出栈顶访问一个右孩子进栈右孩子的左孩子到底进栈BinNodeT * current this;StackBinNodeT* s;while (current){s.push(current);current current-left;}while (!s.empty()){current s.pop();visit(current-data);current current-right;while (current){s.push(current);current current-left;}}}travPost迭代
比较复杂。邓老师将其描述为藤绕树。先找藤的头。
善后工作
为了调用更加友好BinTree 的三个遍历接口加一个tag参数缺省为0宏定义ITER(意为迭代)为1 template typename T2void travPre(T2 visit, int tag 0){if (root){if (tag ITER) root-travPre2(visit);else root-travPre(visit);}}template typename T2void travIn(T2 visit, int tag 0){if (root){if (tag ITER) root-travIn2(visit);else root-travIn(visit);}}template typename T2void travPost(T2 visit, int tag 0){if (root){if (tag ITER) root-travPost2(visit);else root-travPost(visit);}}theeeend ₍ᐢ…ᐢ₎♡
