Question

编写一算法，判别给定的二叉树是否是完全二叉树，二叉树用二叉链表存储结构存储

Answer 1

算法不会写
满二叉树,所有孩子节点不为空
完全二叉树,除最后一层外,其他节点均不为空
那么,遍历一下不就知道了是不是完全二叉树了

Answer 2

假定空的指针已经被赋成null = 0

int isComplete(struct node *root)
{
if (root==0) return 1;
else
if (root->lch && root->rch)
return isComplete(root->lch) && isComplete(root->rch);
else
return !root->lch && !root->rch;

}

Answer 3

遍历概念：
　　所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问 题。
　　遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。
　　遍历方案：
　　1．遍历方案
　　从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：
　　（1）访问结点本身(N)，
　　（2）遍历该结点的左子树(L)，
　　（3）遍历该结点的右子树(R)。
　　以上三种操作有六种执行次序：
　　NLR、LNR、LRN、NRL、RNL、RLN。
　　注意：
　　前三种次序与后三种次序对称，故只讨论先左后右的前三种次序。
　　2．三种遍历的命名
　　根据访问结点操作发生位置命名：
　　① NLR：前序遍历(PreorderTraversal亦称(先序遍历))
　　——访问结点的操作发生在遍历其左右子树之前。
　　② LNR：中序遍历(InorderTraversal)
　　——访问结点的操作发生在遍历其左右子树之中(间)。
　　③ LRN：后序遍历(PostorderTraversal)
　　——访问结点的操作发生在遍历其左右子树之后。
　　注意：
　　由于被访问的结点必是某子树的根，所以N(Node)、L(Left subtree)和R(Right subtree)又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。
　　遍历算法
　　1．中序遍历的递归算法定义：
　　若二叉树非空，则依次执行如下操作：
　　(1)遍历左子树；
　　(2)访问根结点；
　　(3)遍历右子树。
　　2．先序遍历的递归算法定义：
　　若二叉树非空，则依次执行如下操作：
　　(1) 访问根结点；
　　(2) 遍历左子树；
　　(3) 遍历右子树。
　　3．后序遍历得递归算法定义：
　　若二叉树非空，则依次执行如下操作：
　　(1)遍历左子树；
　　(2)遍历右子树；
　　(3)访问根结点。
　　4．中序遍历的算法实现
　　用二叉链表做为存储结构，中序遍历算法可描述为：
　　void InOrder(BinTree T)
　　{ //算法里①~⑥是为了说明执行过程加入的标号
　　① if(T) { // 如果二叉树非空
　　② InOrder(T->lchild)；
　　③ printf("％c"，T->data)； // 访问结点
　　④ InOrder(T->rchild);
　　⑤ }
　　⑥ } // InOrder
　　遍历序列

Answer 4

算法不会写