◆树形结构是一类重要的非线性结构。树能够很好地描述结 构的分支关系和层次特性,它非常类似于自然界中的树。树 结构在客观世界中是大量存在的,例如家谱以及行政组织机 构都可用树形象地表示。树在计算机领域中也有着广泛的应 用,如在编译程序中,用树来表示源程序语法结构;在数据 库系统中,可以用树来组织信息。本章重点讨论二叉树的存 储表示及其各种运算,要求大家要学会编写实现二叉树的各 种运算的算法。 ◆二叉树是递归定义的,因此递归是它的固有特性,本小节 的练习中就要求大家完成许多操作二叉树的算法,且是递归 算法。 ◆下面我们给出一个以先序方式创建任意二叉树的算法,请 认真学习
◆树形结构是一类重要的非线性结构。树能够很好地描述结 构的分支关系和层次特性，它非常类似于自然界中的树。树 结构在客观世界中是大量存在的，例如家谱以及行政组织机 构都可用树形象地表示。树在计算机领域中也有着广泛的应 用，如在编译程序中，用树来表示源程序语法结构；在数据 库系统中，可以用树来组织信息。本章重点讨论二叉树的存 储表示及其各种运算，要求大家要学会编写实现二叉树的各 种运算的算法。 ◆二叉树是递归定义的，因此递归是它的固有特性，本小节 的练习中就要求大家完成许多操作二叉树的算法，且是递归 算法。 ◆下面我们给出一个以先序方式创建任意二叉树的算法，请 认真学习
template<class Entry> 递归建立 void Binary tree<Entry>: CreatBinary th 根结点指 I CreatBinary tree( root);) 表示建立根结点 的右子树 template<class Entry> ora Binary_tree ntry 立二叉链表 表示的二叉树 CreatBinary_ tree(Binary_nodesericry>*&rl f cin>>x; if(x==endmark )r=NULL else r= new RiMary_Node<Entr(x Create ar tree(r->left) CreatIn. y right); Entry 表示“空的 data member 数据
template<class Entry> void Binary_tree<Entry>::CreatBinary_tree() { CreatBinary_tree(root); } template<class Entry> void Binary_tree<Entry>:: CreatBinary_tree(Binary_node<Entry>* &r) { cin>>x; if ( x==endmark ) r = NULL; else{ r = new Binary_Node<Entry>(x); CreatBinary_tree(r->left); CreatBinary_tree(r->right); } } 建立二叉链表 表示的二叉树 递归建立以r为 根结点指针的二叉链表 表示的二叉树 建立”空”二叉树 建立根结点 的左子树 的右子树 Entry data member 表示‘空’的 数据
我们再给要求非递归 在二叉树tree中搜索 因此自行定义 岁标记域 灯印 在以二文栈结点类型又枫( 线结点类型名 写一非递归:打印值为x(二又树re 任 的根结点是x 搜 的结点不多于 ′花不空 寻找值进栈 ss T> printAnce ∠ tree /T>tree, type I st ct nary pode<T> htg: 3 Stack Node Stach lode S 00]: int i, /p/-1///nd=0 Binary Lnode>*t= tree/ GetRooto if(t->d ta==x)A cout<<y<"is Ryot\n", return; 1 while(t&&t->datal=X'll top!=-1) i while(t &&t->data !=x) IST[++ top]. ptr=t: ST[top]. tag =0; t=t->left; y
我们再给出一个应用例。 在以二叉链表存储的二叉树中查找值为x的结点，请编 写一非递归算法：打印值为x的结点的所有的祖先结点 的值。设值为x的结点不多于1个。 template <class T> printAncestors(Binary_tree<T> tree, T& x) { typedef struct { Binary_node<T>* ptr; int tag; } StackNode; StackNode ST[100]; int i, top = -1 ,find=0; Binary_node<T>* t = tree.GetRoot(); if(t->data==x) { cout<<x<<" is Root\n"; return; } while( t && t->data!=x || top!=-1 ) { while(t && t->data != x) { ST[++ top].ptr=t; ST[top].tag = 0; t=t->left; } 在二叉树tree中搜索 结点x，找到则打印 所有祖先结点及x 否则输出x不存在 要求非递归 因此自行定义 ‘栈结点’类型 指针域(保留从根到 搜索结点路径上 所以结点指针) 标记域 (tag==0左子树 否则是右子树 置空栈) 栈数组 栈结点类型名 取得二叉树tree 的根结点指针 做为t的初始值 指针不‘空’而且 其所指结点的 数据域不是 栈不‘空’x 搜索左子树 寻找值为x的结点 进栈 二叉树tree 的根结点是x
if(t&& t->data==X) 没找到值为x的结点 for(i=0; i=top e(<ST[DS cout<x≤ero;fnd= 重新回到wh9 H时结点 break. 辅所有祖先结点 (栈) se i while( top!=/1&& ST[top]. tag==1)top if(top!=-1)I STItop] tag=1; t=ST[top]. ptr->right; 1 }∥end(if-else) block }∥ end while if(find)cout<<"search"<<X<<not existsIn 在C++环境下演示创建二叉树及在建立的二又树上完成 各项操作的 bt main cpp
if (t && t->data==x) { for(i=0; i<=top; i++) cout<<ST[i].ptr->data<<endl; cout<<x<<endl; find=1; break; } else { while( top!=-1 && ST[top].tag==1) top--; if (top!=-1) { ST[top].tag=1; t=ST[top].ptr->right; } } // end_(if-else)block } // end_while if (!find) cout<<" search "<<x<<" not exists\n"; } 找到值为x的结点 输出所有祖先结点 (栈) 跳出while循环 如果栈顶是右指针 弹出 如果栈不空 栈顶是左指针 转向右子树 重新回到while 没找到值为x的结点 在C++环境下演示创建二叉树及在建立的二叉树上完成 各项操作的bt_main.cpp
10.2 Binary Search Trees Can we find an implementation for ordered lists in which we can search quickly(as with binary search on a contiguous list) and in which we can make insertions and deletions quickly(as with a linked list)? binary search tree Definitions pg445 A binary search tree is a binary trees that is either empty or in which the data entry of every node has a key and satisfies the conditions 1. The key of the root (if it exists)is greater than the key in any node in the left subtree of the root 2. The key of the root (if it exists)is less than the key in any node in the right subtree of the root 3. The left and right subtrees of the root are again binary search trees
10.2 Binary Search Trees Can we find an implementation for ordered lists in which we can search quickly (as with binary search on a contiguous list) and in which we can make insertions and deletions quickly (as with a linked list)? A binary search tree is a binary trees that is either empty or in which the data entry of every node has a key and satisfies the conditions: 1. The key of the root (if it exists) is greater than the key in any node in the left subtree of the root. 2. The key of the root (if it exists) is less than the key in any node in the right subtree of the root. 3. The left and right subtrees of the root are again binary search trees. binary search tree Definitions pg.445