6_数据结构与算法_北京大学2008_张铭_树1.ppt

6.3.2 带双标记的先根次序表示 带右链的先根次序表示”中rlink也有冗余，可以把rlink指针替换为一个标志位rtag，成为“带双标记的先根次序表示”。其中，每个结点包括结点本身数据，以及两个标志位ltag和rtag，其结点的形式为： 由结点的先根次序以及ltag、rtag两个标志位，就可以确定树“左孩子/右兄弟”链表中结点的llink和rlink值。其中llink的确定与带右链的先根次序表示法相同。 6.3.2 带双标记的先根次序表示 由结点的排列次序和ltag，rtag的值就可推知rlink的值 当一个结点x的rtag为1时，它的rlink显然应为空 当一个结点x的rtag为0时，它的rlink应指向结点序列中排在结点x的子树结点后面的那个结点y 由于树的先根次序中子树结点是嵌套出现的，在顺序有哪些信誉好的足球投注网站的过程中需要嵌套处理x的所有子树，因此确定y的过程要用到栈结构 扫描到一个rtag为0的结点就将它进栈。扫描到一个ltag为1的结点就从栈顶弹出一个结点并为它设置rlink 6.3.2 带双标记的先根次序表示 A B C D E F G H I J 图6.15 带双标记的先根次序表示法 6.3.2 带双标记的先根次序表示 【算法6.10】带双标记位先根次序树构造算法 templateclass T class DualTagTreeNode { // 双标记位先根次序树结点类 public: T info; // 结点数据信息 int ltag; // 左标记 int rtag; // 右标记 DualTagTreeNode(); // 构造函数 virtual ~DualTagTreeNode(); // 析构函数 }; template class T TreeT::Tree(DualTagTreeNodeT *nodeArray, int count) { // 利用带双标记位的先根次序表示构造左孩子右兄弟表示的树 6.3.2 带双标记的先根次序表示 using std::stack; // 使用STL中的栈 stackTreeNodeT* aStack; TreeNodeT *pointer = new TreeNodeT; // 准备建立根结点 root = pointer; for (int i = 0; i count-1; i++) { // 处理一个结点 pointer-setValue(nodeArray[i].info); // 结点赋值 if (nodeArray[i].rtag == 0) // 若右标记为0则将结点压栈 aStack.push(pointer); else pointer-setSibling(NULL); // 若右标记为1则将兄弟指针设为空 TreeNodeT *temppointer = new TreeNodeT; if (nodeArray[i].ltag == 0) // 如果左标记为0则设置一个孩子结点 pointer-setChild(temppointer); else { // 若左标记为1 6.3.2 带双标记的先根次序表示 pointer-setChild(NULL); // 孩子指针设为空 pointer = aStack.top(); // 取栈顶元素 aStack.pop(); pointer-setSibling(temppointer); // 为其设置一个兄弟结点 } pointer = temppointer; } // 处理最后一个结点 pointer-setValue(nodeArray[count-1].info); pointer-setChild(NULL); pointer-setSibling(NULL); } 6.3.3 带度数的后根次序表示 在带度数的后根次序表示中，结点按后根次序顺序存储在一片连续的存储单元中，结点的形式为 其中info是结点的数据，degree是结点的度数 6.3.3 带度数的后根次序表示 图6.16 带度数的后根次序表示法 A B C D E F G H I J 6.3.3 带度数的后根次序表示 这种表示法不包括指针，但它仍能完全反映树的结构 由于在后序序列中每一棵子树的结点都存储在一起，且每一棵子树在后序序列中的最后一个位置存储这棵子树的根结点，那么将带度数的