深度遍历
void recurve(Node * ptr){
if (null==ptr){
return;
}
//前序 access(ptr)
recurve(ptr->left);
//中序 access(ptr)
recurve(ptr->right);
//后序 access(ptr)
}
前序遍历
中序遍历
后序遍历
广度遍历
前序+中序 / 后序+中序 可以构建二叉树
算法
建立二叉树
复制二叉树
计算深度
求节点总数
求叶子节点总数
线索搜索树
利用二叉链表的空指针域
具有n个节点的二叉链表，一共有2n个指针域，因为n个节点有n-1个孩子，即2n个指针域中，剩余指针域为 2n-（n-1）=n+1、
如果某个节点左孩子为空，则指向前驱，如果右孩子为空，则指向后继。这种改变指向的指针称之为“线索”。加上线索的二叉树称之为线索二叉树。按照某种遍历顺序使其变为线索二叉树的过程称之为“线索化”。
为了区分指针指向孩子还是指向前驱或后继，每个节点增加标志语ltag和rtag。tag为0则指向孩子，为1则指向前驱或后继。
typedef struct{
TElementType data;
int lTag,rTag;
Node * l,*r;
} Node;
网友评论