(二叉树)谈一谈各类算法和数据结构的c++实现以及相关操作的复杂度（二）

接着上一篇， 上一篇主要说了各种排序算法， 但对几个常用的数据结构还未提及，所以这一篇主要讲二叉树, 二叉树已经包括很多链表的知识了。所有代码都是测试过的, 可以直接撸.

二叉树

这里不举太多数字方面的东西， 我们直接看图， 直观感性的认识满二叉树和完全二叉树：

有一点性质需要牢记：具有n个结点的完全二叉树的最大高度为log2n+1

二叉树的二叉链式存储方案的代码表示：

typedef struct BinaryTreeNode { int data; BinaryTreeNode *LeftChild, *RightChild; // BTN *LeftChild, *RightChild; // error : BTN doesn't name a typecat }BTN, *BTN_Ptr;

创建

int create_BT(BTN_Ptr *btp) { int temp_data = 0; std::cin >> temp_data; if (temp_data == 0) { *btp = NULL; printf("leaf\n"); } else { if ( !(*btp = (BTN_Ptr)malloc( sizeof(BTN) ) ) ) { printf("error : malloc error"); return -1; } (*btp)->data = temp_data; create_BT(&((*btp)->LeftChild)); create_BT(&((*btp)->RightChild)); } return 0; }

遍历

如上图得到的相应的遍历的序列分别为：

先序遍历 ： ABCDEGF中序遍历 ： CBEGDFA后序遍历 ： CGEFDBA

递归遍历

void pre_order_traverse(const BTN_Ptr *btp) { if ( *btp != NULL) { cout << (*btp)->data << endl; pre_order_traverse( &(*btp)->LeftChild ); pre_order_traverse( &(*btp)->RightChild ); } } void in_order_traverse(const BTN_Ptr *btp) { if ( *btp != NULL) { in_order_traverse( &(*btp)->LeftChild ); cout << (*btp)->data << endl; in_order_traverse( &(*btp)->RightChild ); } } void post_order_traverse(const BTN_Ptr *btp) { if ( *btp != NULL) { post_order_traverse( &(*btp)->LeftChild ); post_order_traverse( &(*btp)->RightChild ); cout << (*btp)->data << endl; } }

非递归遍历

非递归的二叉树三种遍历方式其实思想是统一的 : 都是从左到右的将各个结点依次入栈, 当左边已经走到头了, 就开始走右边, 在适当的条件就出栈, 只是每个遍历方式的出栈条件不一样而已.

先序和中序遍历都很好理解, 着重讲一下后序遍历 : 后序遍历的出栈条件有点不一样, 因为后序是先左后右再中的, 比如某个结点p要出栈, 需要遍历完了p的所有右子树之后才能出栈, 而不能第一次就出栈, 所以专门构造了一个结构体F_bt来记录他是否是第一次出栈 (F_bt结构体里有个is_first的数据来记录)

void pre_order_traverse_non_recursion(const BTN_Ptr *btp) { stack<BTN_Ptr> stack_bt; BTN_Ptr temp_btp = *btp; while ( !stack_bt.empty() || temp_btp != NULL ) { while ( temp_btp != NULL ) { cout << temp_btp->data << endl; stack_bt.push(temp_btp); temp_btp = temp_btp->LeftChild; } if ( !stack_bt.empty() ) { temp_btp = stack_bt.top()->RightChild; stack_bt.pop(); } } } void in_order_traverse_non_recursion(const BTN_Ptr *btp) { stack<BTN_Ptr> stack_bt; BTN_Ptr temp_btp = *btp; while ( !stack_bt.empty() || temp_btp != NULL ) { while ( temp_btp != NULL ) { stack_bt.push(temp_btp); temp_btp = temp_btp->LeftChild; } if ( !stack_bt.empty() ) { cout << stack_bt.top()->data << endl; temp_btp = stack_bt.top()->RightChild; stack_bt.pop(); } } } typedef struct { BTN_Ptr btnp; int is_first; }F_bt, *F_btp; void post_order_traverse_non_recursion( const BTN_Ptr *btp) { stack<F_btp> stack_F_btp; BTN_Ptr temp_btp = *btp; while ( !stack_F_btp.empty() || temp_btp != NULL ) { while ( temp_btp != NULL ) { F_btp temp_F_btp = new F_bt; temp_F_btp->btnp = temp_btp; temp_F_btp->is_first = 1; stack_F_btp.push(temp_F_btp); temp_btp = temp_btp->LeftChild; } if ( !stack_F_btp.empty() ) { if ( stack_F_btp.top()->is_first == 1 ) { stack_F_btp.top()->is_first = 0; temp_btp = stack_F_btp.top()->btnp->RightChild; } else { cout << stack_F_btp.top()->btnp->data << endl; delete stack_F_btp.top(); stack_F_btp.top() = NULL; stack_F_btp.pop(); temp_btp = NULL; } } } }

二叉搜索树(又称二叉查找树或二叉排序树)

有了上面二叉树的基础, 我们继续学习二叉搜索树. 我们这里也不给他那种晦涩难懂的定义, 感性的认识二叉搜索树. 直接看图, 很容易看得出来, 二叉搜索树每个结点的左孩子都小于右孩子. 因为具有n个结点的完全二叉树的最大高度为log2n+1 而二叉搜索树的查询/增加的时间复杂度都是O(h), h为树的高度,所以复杂度可以看作O(logn), 所以很明显上图中的a树比b树要高效.

查询

BTN_Ptr search(BTN_Ptr btp, int key) { while (btp != NULL ) { if ( btp->data != key) { if ( btp->data < key ) btp = btp->RightChild; else btp = btp->LeftChild; } else { printf("found\n"); return btp; } } printf("error : not found!\n"); return NULL; }

插入

BTN_Ptr insert(BTN_Ptr &btp, int key) { if (btp == NULL) { btp = new BTN; btp->data = key; btp->LeftChild = NULL; btp->RightChild = NULL; return btp; } else { BTN_Ptr saved_btp = btp; BTN_Ptr temp_btp = NULL; while ( btp != NULL) { temp_btp = btp; if ( key < btp->data ) btp = btp->LeftChild; else btp = btp->RightChild; } btp = new BTN; btp->data = key; btp->LeftChild = NULL; btp->RightChild = NULL; if ( key < temp_btp->data ) temp_btp->LeftChild = btp; else temp_btp->RightChild = btp; return saved_btp; } }

测试程序

附上一个测试程序吧

#include <stdio.h> #include <stdlib.h> #include <iostream> #include <stack> using std::stack; using std::cout; using std::cin; using std::endl; int main(int argc, char **argv) { BTN_Ptr my_btp = NULL; if (create_BT(&my_btp) == -1) return -1; cout << "==============pre_order:==============" << endl; pre_order_traverse(&my_btp); cout << "==============in_order:==============" << endl; in_order_traverse(&my_btp); cout << "==============post_order:==============" << endl; post_order_traverse(&my_btp); cout << "==============search : 24==============" << endl; search(my_btp, 24); cout << "==============search : 14==============" << endl; search(my_btp, 14); cout << "==============insert : 25==============" << endl; my_btp = insert(my_btp, 25); cout << "==============pre_order2:==============" << endl; pre_order_traverse(&my_btp); return 0; }