三叉链表的静态结构 root data parent leftChild rightChild 0A 101 1 1 B 23 B 2 C ①@3|D14 4|E 1 ①5F311
三叉链表的静态结构 A B C D E F root data parent leftChild rightChild 0 1 2 3 4 5 A -1 1 -1 B 0 2 3 C 1 -1 -1 D 1 4 5 E 3 -1 -1 F 3 -1 -1
二叉链表的定义 typedef char TreeData;/)结点数据类型 typedef struct node{/)结点定义 TreeData data struct node x leftChild,* rightchild; i Bintreenodes typedef BinTreeNode Bin trees /根指针
typedef char TreeData; //结点数据类型 typedef struct node { //结点定义 TreeData data; struct node * leftChild, * rightchild; } BinTreeNode; typedef BinTreeNode * BinTree; //根指针 二叉链表的定义
基本算法 Void destroy( BinTreeNode * current 删除根为 current的子树 if (current!=NULL) destroy( current-> leftChild ) destroy( current-> rightchild ); delete currents
Void destroy ( BinTreeNode *current ) {//删除根为current的子树 if ( current != NULL ) { destroy ( current -> leftChild ); destroy ( current -> rightChild ); delete current; } } 基本算法
Bin TreeNode *Parent( BinTreeNode x start, BinTreeNode x cuurent) {找当前结点的双亲结点,并返回 if( start== NULL) return NULL; if( start->left Child==current start->right child == current return start.;找到 Bi Intreenode p;/则 if((p= Parent( start->leftchild, current)!=NULL) return p;/在左子树中找 else return Parent(start-> rightChild current);/在右子树中找
BinTreeNode *Parent ( BinTreeNode * start, BinTreeNode * cuurent ) {//找当前结点的双亲结点，并返回 if ( start == NULL ) return NULL; if ( start->leftChild == current || start->rightChild == current ) return start; //找到 BinTreeNode *p; //否则 if (( p = Parent ( start->leftChild, current ))!= NULL ) return p; //在左子树中找 else return Parent(start->rightChild, current); //在右子树中找 }
void Binary Tree Traverse( Bin Treenode *current, ostream &out) 搜索并输出根为 current的二叉树 if( current !=NULL)( 0ut<< current->data<<‘’; Traverse( current-> left Child, out ) Traverse( current->rightChild, out );
void BinaryTree Traverse ( BinTreeNode *current, ostream &out ) {//搜索并输出根为current的二叉树 if ( current != NULL ) { out << current->data << ‘ ’; Traverse ( current->leftChild, out ); Traverse ( current->rightChild, out ); } }