Hal Sadofsky is correct, there is no fsck available for hfs. This is the one area where you will still need the mac. Frankly if Norton and Disk FirstAid are both unable to fix the problem, then I doubt you could do it automatically. I think the only option other than recovery from backups is a professional data recovery service. However, the data is in principle probably still accessible.
"b-tree 4" is the catalog tree, a sort of database of directory entries, holding the name, size, type, etc. of all files and directories. Unlike in DOS or Un*x where the tree has the same structure as the directory structure, HFS throws all the entries together in a single balanced tree (a b-tree). Each entry is sorted in the tree by a key composed of its name preceded by the ID number of its parent directory. Thus all the files in the same directory are adjacent in the tree (because there keys start with the same parent ID). Corresponding to the '..' directory entry, each group of files belonging to the same directory is preceded by a special type of entry called a thread entry. It's key is just the ID number of the directory, with an empty filename appended. It holds the ID of the directory's parent. When any directory is accessed to list its contents, it is the thread record which is read first. If it cannot be found the system decides that the directory doesn't exist, even though it knows its name.
What appears likely is that one of more "pointers" in the tree have become corrupted and so the thread records for the "missing" directories are inaccessible. This surely means that the entries for at least some of the entries in those directories are also inaccessible, but not necessarily ALL of them. It may still be possible to access some files or directories in the "missing" ones by name, but not by 'ls', 'find', 'du' or anything else which tries to do the equivalent of an 'ls' in the "missing" directories. If you know the names of files under the "missing" directories, then give it a try.
In principle the "extents tree", which holds to info on what blocks are used by what files, should still know about the files with inaccessible catalog entries. If an fsck existed, it would do as Michael Knox suggests: find all catalog entries is COULD get to and then find al the extents that weren't accounted for by the accesible catalog entries and make them into files again, thought there names, types, and otehr vital statistics would be lost. This is what Norton tries to do too, but I imagine that the catalog tree is too badly damaged for it to be able to create any entries for the lost files. I think you should assume that is the case any not try to create of delete any files or directories on the disk for fear of further corrupting the catalog tree.
My only USEFULL suggestion is to be sure you have the newest Norton Utilities for Mac which you can find. There is always the hope that a newer version can fix the problem.