64遍历二叉树和线索二叉树 遍历二叉树 遍历二叉树是指按一定的规对二叉树的每个结 点,坊应且仅访问一次的处理过程。 访问是一种抽象操作,是对结点的某种处理,例如 可以是求结点的度、或层次、打印结点的信息,或做 其他任何工作。 次遍历后,使树中结点的非线性排列,按访问的 先后顺序变为某种线性排列。 遍历的次序:若设二叉树根为D,左子树为L,右子 树为R,并限定先左后右,则有以下三种遍历次序: LDR中序遍历;LRD后序遍历;DLR先序遍历
6.4 遍历二叉树和线索二叉树 一、遍历二叉树 遍历二叉树是指按一定的规律对二叉树的每个结 点，访问且仅访问一次的处理过程。 • 访问是一种抽象操作，是对结点的某种处理，例如 可以是求结点的度、或层次、打印结点的信息，或做 其他任何工作。 • 一次遍历后，使树中结点的非线性排列，按访问的 先后顺序变为某种线性排列。 • 遍历的次序：若设二叉树根为D，左子树为L，右子 树为R，并限定先左后右，则有以下三种遍历次序： LDR 中序遍历；LRD 后序遍历；DLR 先序遍历
64遍历二叉树和线索二叉树 1.前序遍历二又树第法颜述 算法思想 void Pre OrderTraverse (bitree t 若二叉树非空,则:{/先序遍历三又树算法 /*其中visi0是对数据元素* 1)访问根结点 /*的具体应用访问函数*/ 2)前序遍历左子树T)如果非空 3)前序遍历右子树 visit(T->data); PreOrderTraverse(t->lchild); PreOrderTraverse(t->rchild);
6.4 遍历二叉树和线索二叉树 1.前序遍历二叉树 算法思想: 若二叉树非空，则： 1）访问根结点 2）前序遍历左子树 3）前序遍历右子树 算法描述: void PreOrderTraverse(BiTree T) { /*先序遍历二叉树算法，*/ /*其中visit()是对数据元素*/ /*的具体应用访问函数*/ if(T) /*如果T非空*/ { visit(T->data); PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); } }
64遍历二叉树和线索二叉树 按前序序列建二叉树 假定 TElem Type是char型,则可用以下算法建立一个二叉树 BiTree Create Bitree( i BiTree t; char ch scanf(“%c~,&ch);∥依次输入前序序列当左(右)子树为空时输入空格 if(ch! it=(BiTree)malloc(sizeof( BiTnode) t->data=ch t->lchild= Create BiTree() t->rchild= Create BiTree(); else tNULL return t;)
6.4 遍历二叉树和线索二叉树 假定TElemType是char型，则可用以下算法建立一个二叉树 BiTree CreateBiTree( ) { BiTree t; char ch; scanf(“%c”,&ch); //依次输入前序序列当左(右)子树为空时输入空格 if(ch!=’’) {t=(BiTree)malloc(sizeof(BiTnode)); t->data=ch; t->lchild= CreateBiTree( ); t->rchild= CreateBiTree( );} else t=NULL; return t; } 按前序序列建二叉树
64遍历二叉树和线索二叉树 2后序遍历二叉树篁法述 算法想 void PostOrderTraverse(bitree t) /*后序遍历二叉树算法,* 若二叉树非空,则 /*其中 visit(是对数据元素*/ /*的具体应用访问函数*/ 后序遍历左子树f(m)产如果T非空* 2)后序遍历右子树{ 3)访问根结点 PostOrderTraverset->lchild); PostOrderTraverser->rchild); visi(T→>data) )
6.4 遍历二叉树和线索二叉树 2.后序遍历二叉树 算法思想: 若二叉树非空，则： 1）后序遍历左子树 2）后序遍历右子树 3）访问根结点 算法描述: void PostOrderTraverse(BiTree T) { /*后序遍历二叉树算法，*/ /*其中visit()是对数据元素*/ /*的具体应用访问函数*/ if(T) /*如果T非空*/ { PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); visit(T->data); } }
64遍历二叉树和线索二叉树 3中序遍历二叉树篁法述 算法思想: void InOrderTraverse(Bitree t) {/*中序遍历二叉树算法,* 若二叉树非空,则:/其中5Q是对数据元素+ /米的具体应用访问函数*/ 1)中序遍历左子树()/如果T非空* 2)访问根结点 3)中序遍历右子树 InOrderTraverset->lchild) visit(T->data); InOrderTraverset->rchild);
6.4 遍历二叉树和线索二叉树 3.中序遍历二叉树 算法思想: 若二叉树非空，则： 1）中序遍历左子树 2) 访问根结点 3）中序遍历右子树 算法描述: void InOrderTraverse(BiTree T) { /*中序遍历二叉树算法，*/ /*其中visit()是对数据元素*/ /*的具体应用访问函数*/ if(T) /*如果T非空*/ { InOrderTraverse(T->lchild); visit(T->data); InOrderTraverse(T->rchild); } }