三叉链表的静态结构 root data parent left Child right Child ABC 12141 13 ⑥①3D 4|E 101133 1511 5F
三叉链表的静态结构 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 left Child, rightchild 3 Bintreenode typedef BinTreeNode Bin Tree; 很根指针
typedef char TreeData; //结点数据类型 typedef struct node { //结点定义 TreeData data; struct node * leftChild, * rightchild; } BinTreeNode; typedef BinTreeNode * BinTree; //根指针 二叉链表的定义
基本算法 Void destroy( Bin TreeNode *current) 删除根很为 Current的子树 if( current NULL)& destroy( current -> leftchild ); destroy( current-> rightchild ) delete current:
Void destroy ( BinTreeNode *current ) {//删除根为current的子树 if ( current != NULL ) { destroy ( current -> leftChild ); destroy ( current -> rightChild ); delete current; } } 基本算法
BinTreeNode parent( Bin TreeNode x start, BinTreeNode x cuurent) 找当前结点的双亲结点,并返回 if( start== NULL) return NULL if( start->leftChild ==current I start->rightchild = current return start;找到 BinTreenode*p;/则 if((p=Parent( start->left Child, current)!=NULL) return p;/在左子树中找 else return Parent(start->right child, 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( BinTreenode current, ostream &out 搜索并输出根为 current的二又树 if( current !=NULL) out<< current->data<<‘’; Traverse( current->leftChild, 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 ); } }