二叉树遍历怎么正确理解二叉树的遍历

二叉树遍历

0是初始节点数 输入时请一次性输完ABCффDEфGффFффф在按ENTER键 不要输入一个按一下 #include"stdio.h" #include"string.h" #include"stdlib.h" #define Max 20 //结点的最大个数 typedef struct node{ char data; struct node *lchild,*rchild; }BinTNode; //自定义二叉树的结点类型 typedef BinTNode *BinTree; //定义二叉树的指针 int NodeNum,leaf; //NodeNum为结点数，leaf为叶子数 //==========基于先序遍历算法创建二叉树============== //=====要求输入先序序列，其中加入虚结点"#"以示空指针的位置========== BinTree CreatBinTree(void) { BinTree T; char ch; if((ch=getchar())==) return(NULL); //读入#，返回空指针 else{ T=(BinTNode *)malloc(sizeof(BinTNode));//生成结点 T->data=ch; T->lchild=CreatBinTree(); //构造左子树 T->rchild=CreatBinTree(); //构造右子树 return(T); } } //========NLR 先序遍历============= void Preorder(BinTree T) { if(T) { printf("%c",T->data); //访问结点 Preorder(T->lchild); //先序遍历左子树 Preorder(T->rchild); //先序遍历右子树 } } //========LNR 中序遍历=============== void Inorder(BinTree T) { if(T) { Inorder(T->lchild); //中序遍历左子树 printf("%c",T->data); //访问结点 Inorder(T->rchild); //中序遍历右子树 } } //==========LRN 后序遍历============ void Postorder(BinTree T) { if(T) { Postorder(T->lchild); //后序遍历左子树 Postorder(T->rchild); //后序遍历右子树 printf("%c",T->data); //访问结点 } } //=====采用后序遍历求二叉树的深度、结点数及叶子数的递归算法======== int TreeDepth(BinTree T) { int hl,hr,max; if(T){ hl=TreeDepth(T->lchild); //求左深度 hr=TreeDepth(T->rchild); //求右深度 max=hl>hr? hl:hr; //取左右深度的最大值 NodeNum=NodeNum+1; //求结点数 if(hl==0&&hr==0) leaf=leaf+1; //若左右深度为0，即为叶子。

return(max+1); } else return(0); } //====利用"先进先出"（FIFO）队列，按层次遍历二叉树========== void Levelorder(BinTree T) { int front=0,rear=1; BinTNode *cq[Max],*p; //定义结点的指针数组cq cq[1]=T; //根入队 while(front!=rear) { front=(front+1)%NodeNum; p=cq[front]; //出队 printf("%c",p->data); //出队，输出结点的值 if(p->lchild!=NULL){ rear=(rear+1)%NodeNum; cq[rear]=p->lchild; //左子树入队 } if(p->rchild!=NULL){ rear=(rear+1)%NodeNum; cq[rear]=p->rchild; //右子树入队 } } } //==========主函数================= void main() { BinTree root; int i,depth; printf("NodeNum:%d ",NodeNum); printf("Creat Bin_Tree； Input preorder:"); //输入完全二叉树的先序序列， // 用#代表虚结点，如ABD###CE##F## root=CreatBinTree(); //创建二叉树，返回根结点 do { //从菜单中选择遍历方式，输入序号。

printf(" ********** select ************ "); printf(" 1: Preorder Traversal "); printf(" 2: Iorder Traversal "); printf(" 3: Postorder traversal "); printf(" 4: PostTreeDepth,Node number,Leaf number "); printf(" 5: Level Depth "); //先判断节点数是否已有。

不用再先选择4，求出该树的结点数。

printf(" 0: Exit "); printf(" ******************************* "); scanf("%d",&i); //输入菜单序号（0-5） switch (i){ case 1: printf("Print Bin_tree Preorder: "); Preorder(root); //先序遍历 break; case 2: printf("Print Bin_Tree Inorder: "); Inorder(root); //中序遍历 break; case 3: printf("Print Bin_Tree Postorder: "); Postorder(root); //后序遍历 break; case 4: depth=TreeDepth(root); //求树的深度及叶子数 printf("BinTree Depth=%d BinTree Node number=%d",depth,NodeNum); printf(" BinTree Leaf number=%d",leaf); break; case 5: if(!NodeNum) TreeDepth(root); printf("LevePrint Bin_Tree: "); Levelorder(root); //按层次遍历 break; default: exit(1); } printf(" "); } while(i!=0); }

二叉树的遍历？

9二叉树的遍历

（1）遍历：遍历（traverse）一个有限结点的集合，意味着对该集合中的每个结点访问且仅访问一次。

（2）三种遍历方式

先序遍历（VLR）：先序就是先访问结点元素，然后是左，然后是右。

若二叉树不为空

访问根结点；

先序遍历左子树；

先序遍历右子树。

先序遍历序列： A B D C E F

template<class T>

void BinaryTree<T>::PreOrder()

{

PreOrder(root);

}

template<class T>

void BinaryTree<T>::PreOrder(BTNode<T>* t)

{

if(t)

{

cout<<(t->element);

PreOrder(t->lChild);

PreOrder(t->rChild);

}

}

中序遍历（LVR）

若二叉树不为空

中序遍历左子树；

访问根结点；

中序遍历右子树。

中序遍历序列：B D A E C F

template<class T>

void BinaryTree<T>::InOrder()

{

InOrder(root);

}

template<class T>

void BinaryTree<T>::InOrder(BTNode<T>* t)

{

if(t)

{

InOrder(t->lChild);

cout<<(t->element);

InOrder(t->rChild);

}

}

后序遍历 （LRV）

若二叉树不为空 后序遍历左子树； 后序遍历右子树； 访问根结点。

后序遍历序列：D B E F C A

template<class T>

void BinaryTree<T>::PostOrder()

{

PostOrder(root);

}

template<class T>

void BinaryTree<T>::PostOrder(BTNode<T>* t)

{

if(t)

{

PostOrder(t->lChild);

PostOrder(t->rChild);

cout<<(t->element);

}

}

二叉树遍历

很显然你还不懂的遍历一棵二叉树的原理 当你拿到一棵二叉树，无论它的形状如何的千奇百怪 我们都可以将它按照如下的方式划分 根 / 左子树 右子树 一棵有很多个节点的二叉树可以划分为以上的形式 也可以这么理解，只要是按以上形式组合的都可以称为是二叉树 一个仅仅只有根节点的二叉树也可以划分成以上的形式，只不过他的左右子树都为空罢了 所以，我们发现，二叉树的定义其实是一个递归定义的过程 大的二叉树是由小的二叉树构建而成的 所以，当我们考虑要遍历一棵二叉树时 也是首选递归的遍历 遍历二叉树 它的基本思想是先按照上面的形式把整棵二叉树划分为3部分 哪么接下来的工作就很简单了 我们只需要将这3部分都遍历一遍就可以了（这里用到了分而治之的思想） 而对于这3部分来说 根节点的遍历无疑是最方便的，直接访问就ok了 而对于左右子树呢？ 我们不难发现，左右子树其实分别成为了两棵完整的树 他们拥有各自独立的根节点，左子树和右子树 对他们的遍历，很显然应该与刚才的遍历方法一致便可 （如果上面的都理解了，那么这个题就是小菜一碟了，如果觉得无法理解，可以按照下面的方法自己多分解几棵树） 对于这个题目，中序遍历这可二叉树 先看根节点 1 / 左子树 右子树 我们应该先遍历左子树 也就是下面这棵树 2 / 4 5 对于这棵树在进行中序遍历 我们应先遍历她的左子树 他只有一个根节点4，左右子树都为空 哪么遍历这个只有一个根节点的二叉树 先访问她的左子树，为空 返回 访问该树的根节点4 在访问右子树也为空 此时，这棵树已经被完全的遍历了 我们需要返回上一e69da5e887aa3231313335323631343130323136353331333238646361层也就是 2 / 4 5 这棵树 此时，她的左子树已经被访问完毕 根据中序遍历的规则 需要访问此树的根节点2 此时的访问顺序是4-2 访问了根节点 在访问右子树只有一个根节点的5（具体过程看4的访问） 5访问完毕 也就意味着 2 / 4 5 这棵树已经访问完了 需要返回上一层 也就是1为根的树 此时这棵树的左子树已经访问完毕 此时访问的顺序是4-2-5应该没有问题 接下来访问根节点1 在访问右子树 3 / 4 7 是不是觉得似曾相识？？？ 她的访问应该跟 2 / 4 5 一致 哪么最终遍历的顺序也出来了 4-2-5-1-6-3-7 ----------------------------- 花了10多分钟 希望对你有所帮助 顺便自己也复习下 呵呵

怎么正确理解二叉树的遍历

在计算机科学中，二叉树是每个节点最多有两个子树的树结构。

通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。

二叉树的遍历分为三类：前序遍历、中序遍历和后序遍历。

（1）前序遍历 先访问根节点，再遍历左子树，最后遍历右子树；并且在遍历左右子树时，仍需先遍历左子树，然后访问根节点，最后遍历右子树。

上图的前序遍历如下。

（2）中序遍历 先遍历左子树、然后访问根节点，最后遍历右子树；并且在遍历左右子树的时候。

仍然是先遍历左子树，然后访问根节点，最后遍历右子树。

前图的中序遍历如下。

（3）后序遍历 先遍历左子树，然后遍历右子树，最后访问根节点；同样，在遍历左右子树的时候同样要先遍历左子树，然后遍历右子树，最后访问根节点。