1、二叉树的遍历是指从根节点出发,按照某种次序依次访问二叉树中的所有结点,使得每个节点被访问依次且仅被访问一次。
2、前序遍历:
规则是若二叉树为空,则空操作返回,否则先访问根节点,然后前序遍历左子树,再前序遍历右子树。
遍历的顺序为:1 2 4 8 5 3 6 9 10 7
/*前序遍历算法*/void PreOderTraverse(BiTree T){if(T==NULL)return;printf("%c",T->data); //显示结点数据,可以更改为其他对结点操作PreOderTraverse(T->lchild); //先遍历左子树PreOderTraverse(T->rchild); //最后遍历右子树 }
【操作】:调用PreOderTraverse(T),T的结点不为NULL,所以执行printf,打印数字1;调用PreOderTraverse(T->lchild),调访问1的左孩子,不为NULL,执行printf显示数字2…….
3、中序遍历:
若树为空树,则空操作返回,否则从根节点开始,中序遍历根节点的左子树,然后访问根节点,最后中序遍历右子树。
遍历顺序为:4 8 2 5 1 9 6 10 3 7
/*中序遍历递归算法*/void InOderTraverse(BiTree T){if(T==NULL)return ;InOderTraverse(T->lchild); //中序遍历左子树printf("%c",T->data); //显示结点数据,可以更改为其他对结点的操作InOderTraverse(T->rchild); //最后中序遍历右子树 }
【操作】:调用InOderTraverse(T),T的根节点不为NULL,于是调用InOderTraverse(T->lchild),访问结点2.当前指针不为NULL,继续调用InOderTraverse(T->lchild),访问结点4,不为NULL,继续调用InOderTraverse(T->lchild),访问4的左孩子,发现当前指针为NULL,于是返回,打印当前结点4。然后调用InOderTraverse(T->rchild),访问4的右孩子8,因为8没有左孩子,所以打印8,有因为8没有右孩子,返回,打印结点4的函数执行完毕,返回打印数字2。。。。。。
4、后序遍历:
若树为空,则空操作返回,否则从左到右先叶子后结点的方式遍历访问左右子树,最后访问根结点。
遍历顺序为:8 4 5 2 9 10 6 7 3 1
/*后序遍历递归算法*/void PostOderTraverse(T){if(T==NULL)return;PostOderTraverse(T->lchild); //先遍历左子树 PostsOderTraverse(T->rchild); //再遍历右子树 printf("%c",T->data); //显示结点数可以更改为其他对结点数据 }
【操作】:由根节点1-2-4,结点4没有左孩子,再看结点4的右孩子8,由于8没有左右孩子,打印8,返回。。。。。。
5、层序遍历:
若树为空,则空操作返回,否则从树的第一层,也就是根结点开始访问,从上而下逐层遍历,在同一层中,按从左到右的顺序对结点逐个访问。
遍历的顺序为:A B C D E F G H I
/*层序遍历*/void Tree<T>::Level_Order_Traverse(Tree_Node<T>* node){queue<Tree_Node<T>*> Visit_Queue;Tree_Node<T>* temp;assert(node == root);Visit_Queue.push(node);//根节点入队while (Visit_Queue.size()){//输出队头元素temp = Visit_Queue.front();cout << temp->data<< " ";//弹出队头元素Visit_Queue.pop();//左右节点非空入队if (temp->left_node != NULL) Visit_Queue.push(temp->left_node);if (temp->right_node != NULL) Visit_Queue.push(temp->right_node);}}