思路:

二叉树的遍历

二叉树的操作有不知凡二种,在这之中最常用的是2叉树的遍历。②叉树的遍历是指依据某种顺序访问贰叉树中的各个结点,使得种种结点都被仅且访问二次。
经过一遍完整的遍历,可使2叉树中的结点由原来的非线性类别变为某种意义的线性类别。依照根节点访问的依次分化,遍历的依次分为前序遍历,中序遍历,后序遍历。

树:层次关系
Tree :n个节点构成的星星点点集合;
n=0时;称为空树;
对此非空树,具有特质有:

多年来看了一下大学的数据结构,学到了原先没学到的东西看到了贰叉树那1块,认为二叉树是个很重点的东西,就看了弹指间底层是怎么落到实处的,纵然能看懂书上用c语言写的伪代码,不过不能够运作,身为七个Java程序员,既然人家能用其余的语言能完结,自身也去试着写了弹指间。

标志二个结点的左右子树是不是曾经被访问过,叶子节点也打开标识

二叉树的遍历方法与算法完结

金沙注册送58 1

二叉树

  • 树中有一个根的别树一帜节点,用r解释;
  • 子树;
    树与非树?
  • 子树是不想交的;
  • 除开根节点外,各类结点点有且仅有一个父节点;
  • 一棵N个结点的树有N-一条边;

数据结构学习第6弹,后续遍历的Java。首先付诸2叉树的节点代码

public class BinTree {

  public BinTree(String name) {
    this.name = name;
  }

  public BinTree(int name) {
    this.name = name + "";
  }

  BinTree left;
  BinTree right;
  public String name;



  public void setLeft(BinTree left) {
    this.left = left;
  }

  public void setRight(BinTree right) {
    this.right = right;
  }

  public void setName(String name) {
    this.name = name;
  }
}

拓展:

先序遍历

先序遍历的递归定义:借使二叉树为空,则遍历的结果为空,不然:

  • 走访根节点
  • 先序遍历左子树
  • 先序遍历右子树

以上海教室作为遍历对象的话:

  • 先走访根节点A
  • 先序遍历根节点的左子树,然后继续遵守先序遍历的顺序

  • 先拜访结点B

  • 做客结点D
    • 左子树为空
    • 做客结点E
  • 走访结点f
    • 做客结点G
    • 右子树为空
  • 做客右子树结点C

金沙注册送58,最后赢得的遍历系列为: ABDEfGC

主旨术语

一、 结点的度 结点的子树个数
贰、树的度:树的保有结点最大的度数
3、叶结点:度为1的结点;
四、父节点:有子树的结点是其子树的根节点的父节点
5、子节点;
六、兄弟结点:同一父节点的各结点是相互的兄弟结点;
7、路线和渠道长度;
八、祖先结点;
玖、子孙节点;
11、结点的层次;
1二、树的深度;

完成方式

金沙注册送58 2

image.png

二叉树:度为2;
出奇贰叉树

  • 斜2叉树
  • 左右逢原贰叉树/满二叉树
  • 一心②叉树(不完整)

然后模拟1个栈的代码,会在前面非递归的时候用到

出于只是去遍历全体节点,未有思考质量上的难题,只是让大家探听思路,底层用ArrayList去完毕栈功效

/*
模拟栈的功能
*/
public class Stack<E> {
  public List<E> mBinTrees = new ArrayList<>();

  /**
   * 把节点放入栈
   * 
   * @param binTree
   */
  public void push(E binTree) {
    mBinTrees.add(binTree);
  }

  /**
   * 从栈顶pop出一个节点并得到这个节点
   * 
   * @return
   */
  public E pop() {
    if (mBinTrees != null) {

      return mBinTrees.remove(mBinTrees.size() - 1);
    }

    return null;
  }

  /**
   * 判断栈里是否还有数据
   * 
   * @return
   */
  public boolean isEmpty() {
    return mBinTrees.size() == 0;
  }

  /**
   * 查看当前栈顶的元素
   * 
   * @return
   */
  public E top() {
    return mBinTrees.get(mBinTrees.size() - 1);
  }
}

遍历进度中读者会意识,某一时时,从栈底到栈顶的成分刚好构成当前走访节点的到根节点的门道。利用这一风味能够完结七个算法:(一)根到某节点的路径(二)多个节点的近年公共祖先

二叉树先序遍历递归算法的兑现

void Preorder(BinTree t)
{
    if(t!=NULL)
    {
        printf("%c ",t->data);
        preOrder(t->leftChild);
        preOrder(t->rightChild);
    }
}

要害性质

2叉树第i层最大结点 贰^(n-1)
纵深为k的贰叉树最大结点总量为二^n-1
非空2叉树 n0为叶节点的个数 n2为度为二的非叶节点个数 满意n0=n贰+一;

常用的遍历方法:
先序–根,左子树,右子树
中序–左子树,根,右子树
后续–左子树,右子树,根
层次遍历–从上到下,从左到右

(一)先序遍历

先看下先序遍历的流程图,接下去的代码也会依照此图是遍历

金沙注册送58 3

先序遍历.JPG

先序遍历顾名思义,正是先会遍历根节点->左孩子->右孩子。遍历是从根节点开始,境遇各类节点时,其遍历进度为:

  • 访问根节点;
  • 先序遍历其左子树;
  • 先序遍历其右子树;

typeDef struct{

二叉树先序遍历非递归算法的兑现

因为举行的种种为从根节点开端,沿着左子树平昔找下去,找到底,然后回到到近年来找过的结点的右子树。所以需求记录走访过的根节点,便于往回走,由于是先让根节点3个个记下起来,然后在回去的时候找如今刚找过的根节点,所以符合栈的特色(先进先出),用顺序栈存款和储蓄就可以。

#define MAXSIZE 100
void Preorder2(BinTree t)
{
    if(t==NULL)
        return ;
    BinTree stack[MAXSIZE],p;
    int top = 0;
    p = t;
    //找到底,且栈中没有可以回去的结点时,遍历结束
    while(p!=NULL || top>0)
    {
        //找左子树,找到头为止
        while(p!=NULL)
        {
            printf("%c ",p->data);  //访问结点的指针域
            if(top<MAXSIZE-1)
            {
                stack[top] = p;
                p++;
            }
            else
            {
                printf("error\n");
                return ;
            }
        }
        //找右子树
        --top;
        p = stack[top];
        p = p->rightChild;
    }
}

二叉树的储存结构

先序遍历递归落成代码:

/**
   * 前序遍历 递归
   */
  public static void preOrderTraversal(BinTree binTree) {
    if (binTree != null) {
      System.out.print(binTree.name);
      preOrderTraversal(binTree.left);
      preOrderTraversal(binTree.right);
    }
  }
BiTree t;
int tag;

按先序连串建立2叉树

建立二叉树时的输入的树为把树的每1个叶子结点的孩子结点填充为’#’。

void CreatBintree(BinTree *root)
{
    char ch;
    if((ch=getchar())=='#') //从键盘上输入二叉树结点数值到#截止
        *root = NULL
    else
    {
        *root = (BinNode*)malloc(sizeof(BinNode));
        (*root)->data = ch;
        CreatBintree(&((*root)->leftChild));
        CreatBintree(&((*root)->rightChild));
    }
}

顺序存储结构

-完全2叉树
:从上到下、从左到右顺序存款和储蓄n个节点的一心二叉树的节点老爹和儿子关系。

  • 父根节点 父节点[i/2]
  • 左孩子节点 贰i
  • 右孩子节点贰i+一
    诚如二叉树也能够采纳那种结构,但会导致空间浪费。

先序遍历非递归达成代码

/**
   * 前序遍历 非递归
   * 输出结果 ABDFECGHI
   */
  public static void preOrderTraversalNoDIGUI(BinTree binTree) {
    Stack<BinTree> stack = new Stack();
    BinTree t = binTree;
    while (t != null || !stack.isEmpty()) {
      while (t != null) {
        System.out.print(t.name);
        stack.push(t);
        t = t.left;
      }
      if (!stack.isEmpty()) {
        t = stack.pop();
        t = t.right;
      }
    }
  }

出口结果

ABDFECGHI

}Stack

中序遍历

中序遍历的递归定义:假设二叉树为空,则遍历的结果为空,不然:

  • 中序遍历根节点的左子树
  • 访问根节点
  • 中序遍历根节点的右子树

有了先序遍历的阅历,以上海体育场合作为遍历对象的话:
终极赢得的遍历连串为:DEBGfAC

链表存款和储蓄

template <typename DataType>
struct TreeNode
{
    DataType data; //存储的数据
    TreeNode *left; //指向左子树根节点
    TreeNode *right; //指向右子树根节点
    //TreeNode * parent; //指向父节点,如果需要的话
    TreeNode(DataType inData): data(inData), right(nullptr), left(nullptr) {}
};

金沙注册送58 4

image.png

(二)中序遍历

金沙注册送58 5

中序遍历.JPG

中序遍历是指对树中任1节点的拜会是在遍历完其左子树后进行的,访问此结点后再对其右子树遍历。遍历从根节点伊始,蒙受各个结点时,其遍历进程为:

  • 中序遍历其左子树;
  • 走访根节点;
  • 中序遍历其右子树

void f(BiTree bt, ElemType x){

二叉树中序遍历递归算法达成

void Inorder(BinTree t)
{
    if(t!=NULL)
    {
        InOrder(t->leftChild);
        printf("%c ",t->data);
        InOrder(t->rightChild);
    }
}

遍历

//遍历
//先序遍历
template <typename DataType>
void Traverse(TreeNode<DataType> * inNode){
    if (inNode == nullptr){
    return;
    }
    //cout<<inNode->data<<endl;//如果在这里访问即为先序访问
    Traverse(inNode->left);
    //cout<<inNode->data<<endl;//如果在这里访问即为中序访问
    Traverse(inNode->right);
    //cout<<inNode->data<<endl;//如果在这里访问即为后序访问
    return;
}

中序遍历递归完毕代码:

  /**
   * 中序遍历 递归
   * DBEFAGHCI
   */
  public static void inOrderTraversal(BinTree binTree) {
    if (binTree != null) {
      inOrderTraversal(binTree.left);
      System.out.print(binTree.name);
      inOrderTraversal(binTree.right);
    }
  }
Stack s[];
top = 0;
while(bt!=null||top>0)
    while(bt!=null){
        s[++top].t = bt;
        s[top].tag = 0;
        bt=bt->lchild;
    }
//注意这里是while   不是if
while(top!=0&&s[top].tag==1)
    print(visit(s[top--]));

if(top!=0){
    s[top].tag = 1;
    bt = s[top].t->rchild;
}

二叉树中序遍历非递归算法达成

对于中序遍历与先序遍历不一致的是造访的逐条区别,但一样要用栈来记录

#define MAXSIZE 100;
void Inorder2(BinTree t)
{
    if(t==NULL)
        return ;
    BinTree stack[MAXSIZE],p;
    int top = 0;
    p = t;
    while(p!=NULL || top>0)
    {
        //先遍历到底再访问结点
        while(p!=NULL)
        {
            if(top<MAXSIZE-1)
            {
                stack[top] = p;
                p++;
            }
            else
            {
                printf("error\n");
                return ;
            }
        }
        top--;
        p = stack[top];
        printf("%c ",p->data);  //访问结点的指针域
        p = p->rightChild;
    }
}

二叉树的非递归算法

先序遍历的非递归:使用宾馆

template <typename DataType>
void NonRecursiveTraverse(TreeNode<DataType> * inNode){
    stack<TreeNode<DataType>*> nodeStack;
    TreeNode<DataType> *cycleNode = inNode;
    while(inNode != nullptr||!nodeStack.empty()){
        //不断访问某一节点的左子节点并压栈知道最左子节点
        while(cycleNode != nullptr){
            //遇到节点先输出
            cout<<cycleNode->data<<endl;
            nodeStack.push(cycleNode);
            cycleNode = cycleNode->left;
        }
        //此时所有的左子树都压入栈中
        //弹出最后一个节点 访问该节点的右子节点并作为下一步作为下一轮遍历节点
        if(!inNode.empty()){
            cycleNode = nodeStack.top();
            cycleNode = cycleNode->right;
            nodeStack.pop();
        }
    }
}

中序遍历:先访问左子节点,在访问根节点,再拜访右子节点。

template <typename DataType>
void NonRecursiveTraverse(TreeNode<DataType> * inNode){
    stack<TreeNode<DataType>*> nodeStack;
    TreeNode<DataType> *cycleNode = inNode;
    while(inNode != nullptr||!nodeStack.empty()){
        //不断访问某一节点的左子节点并压栈知道最左子节点
        while(cycleNode != nullptr){   
            nodeStack.push(cycleNode);
            cycleNode = cycleNode->left;
        }
        //此时所有的左子树都压入栈中
        //弹出最后一个节点 访问该节点的右子节点并作为下一步作为下一轮遍历节点
        if(!inNode.empty()){
            cycleNode = nodeStack.top();
            //在此处访问即为中序遍历,时机为压入右子节点之前
        //cout << cycleNode->data << endl; 
            cycleNode = cycleNode->right;
            nodeStack.pop();
        }
    }
}

是因为扶持压栈,咱们并未将null压入栈中,假设发现左子节点为null则在保留右子节点地址后直接弹出该节点,并动用右子节点作为下壹论访问发轫节点,假诺右子节点为null则意味该节点左右子树均遍历达成,则两次三番弹出直至出现第三个右子树不为空的节点,重复递归。

压栈图中,在前序遍历时,只要境遇节点(压栈进程)就直接出口就能够有限协助根节点首先被输出,而中序遍历由于须求在左子树输出完成后技术出口,因而只要保证在压栈再次来到时(出栈时)且准备遍历右子树时输出就可以。

后序遍历 非递归实现

template <typename DataType>
void NonRecursiveTraverse(TreeNode<DataType> *inNode){
        stack<TreeNode<DataType> *>nodeStack;
        TreeNode<DataType> *cycleNode = inNode;
        TreeNode<DataType> *hasNode = nullptr;
        while(inNode != nullptr || !nodeStack.empty()){
            //不断访问某一节点的左子节点并压栈直到最左子节点
            while(cycleNode != nullptr){
                nodeStack.push(cycleNode);
                cycleNode = cycleNode->left;
            }
            //此时所有的子节点都已经压入栈中。
            //弹出最后一个节点,访问该节点的右子节点并作为下一轮遍历根节点
            if(!nodeStack.empty()){
                cycleNode = nodeStack.top();
                //此时判别是否已经加载右子树
                //如果为空则和中序遍历一样
                if(cycleNode->right == nullptr){
                    hascycle = cycleNode;
                    cout<< cycleNode->data<<endl;
                    nodeStack.pop();
                }
                else if(hascycle == cycleNOde->right){
                    hascycle = cycleNode;
                    cout<<cycleNode->data<<endl;
                    nodeStack.pop();
                }
                cycleNode = nullptr;
                if(!nodeStack.empty() && ndoeStack.top->right!=nullptr)) {
                    cycleNode = nodeStack.top()->right;
                }
            }
        }
}

中序遍历非递归实当代码:

  /**
   * 中序遍历 非递归
   * DBEFAGHCI
   */
  public static void inOrderTraversalNODIGUI(BinTree binTree) {
    Stack<BinTree> stack = new Stack();
    BinTree t = binTree;
    while (t != null || !stack.isEmpty()) {
      while (t != null) {
        stack.push(t);
        t = t.left;
      }
      if (!stack.isEmpty()) {
        t = stack.pop();
        System.out.println(t.name);
        t = t.right;
      }
    }
  }

}

后序遍历

此起彼伏遍历的递归定义:若二叉树为空,遍历结果为空,不然:

  • 后序遍历根节点的左子树
  • 三番五次遍历根节点的右子树
  • 走访根节点

以上图为遍历对象的话
遍历结果的系列为:EDGfBCA

层序遍历

2叉树遍历的骨干难题:2维结构的线性化

  • 从节点访问其左、右外甥
  • 亟待一个存款和储蓄结构保留临时不访问的结点
  • 积存结构:仓库、队列

队列实现:遍历从根节点初阶,首先将根节点入队,然后起首进行循环:结点出队,访问该结点,将左右幼子入队

void LevelOrderTraversal ( BinTree BT){
    Queue Q;BinTree T;
    //如果是空树直接返回
    if(!BT)
        return ;
    //创建并初始化队列Q
    Q = CreatQueue(Maxsize);
    AddQ(Q,BT);
    while( !IsEmptyQ(Q)){
        T = DeleteQ(Q);
        cout  <<T->data<<endl;
        if(T->left)   
            AddQ(Q,T->left);
        if(T->right)
            AddQ(Q,T->right)
    }
}

过程

在沿左子树深深时,进入贰个结点就将其压人宾馆。倘使先序遍历,则在入栈在此以前访问之;
当沿左分支深人不下来时,则赶回,即从货仓中弹出后边压人的结点;若为中序遍历,则此时访问
该结点,然后从该结点的右子树继续深刻;若为后序遍历,则将此结点一次入栈,然后从该结点的
右子树继续深刻,与近日类同,仍为进入3个结点入栈二个结点,深入不下去再回去,直到第二次
从栈里弹出该结点,才访问之。
之所以,依照上述描述的经过,使用货仓能够间接达成相应的非递归算法。先序和中序算法相
对间果些,而后序遍历因为须求三遍将1个结点人栈,情形稍复杂些。上边只以中序遍所头份
介绍二叉树遍历的非递归算法。
在按中序遍历二叉树时,蒙受贰个结点,就把它入栈,并去遍历它的左子树,当左子树遍历结束后,从栈顶弹出那几个结点并访问它,然后按其右指针再去中序遍历该结点的右子树。

您或者感兴趣的

二叉树后序遍历递归算法完结

void Posorder(BinTree t)
{
    if(t!=NULL)
    {
        Posorder(t->leftChild);
        Posorder(t->rightChild);
        printf("%c ",t->data);
    }
}

1经有七个遍历种类分明二叉树

必须求有中序遍历
如若已知先序和中序;

  1. 据说先序遍历体系第二个节点显著根节点;
  2. 杜绝根节点在中序遍历种类中分割出左右多个子类别
  3. 对左子树和右子树分别递归分为左子树和右子树

(叁)后序遍历

金沙注册送58 6

此起彼伏遍历.JPG

后序遍历是指对树中任一节点的拜会是在遍历完其左、右子树后举行的。遍历从根节点开首,遭受每一种结点时,其遍历进程为:

  • 后序遍历其左子树;
  • 后序遍历其右子树
  • 访问根节点;
  • 非递归先序遍历2叉树https://www.cnblogs.com/Coeus-P/p/9353186.html
  • 非递归后序遍历二叉树版本贰
  • 递归算法–2叉树宽度
  • 递归算法–沟通2叉树左右子树
  • 递归算法–二叉树高度
  • 递归算法–2叉树中叶子结点
  • 递归算法–2叉树中度为二的结点
  • 递归算法–2叉树低度为一的结点
  • 非递归完结斐波那契数列
  • 非递归后序遍历二叉树版本一
  • 层次遍历贰叉树
  • 非递归中序遍历2叉树
  • 非递归先序遍历2叉树

二叉树后序遍历非递归算法达成

与前序遍历和中序遍历差别的是你跑完了左子树和右子树本领访问根节点,此时当你遍历完左子树时,你需求重返根节点,不过此时您还不可能访问,因为你要先遍历右子树所以你还要根结点再次入栈,然后下次在出栈的时候能力访问,所以那里用1个标识来拍卖

#define MAXSIZE 100
typedef struct
{
    BinTree link;
    int flag;
}stackType;
void Posorder2(BinTree t)
{
    if(t==NULL)
        return ;
    stackType stack[MAXSIZE];
    BinTree p;
    int top = 0;
    while(p!=NULL || top>0)
    {
        if(p!=NULL)
        {
            //结点第一次进栈
            stack[top].link = p;
            stack[top].flag = 0;
            //找结点的左儿子
            p = p->leftChild;
            top++;
        }
        else
        {
            top--;
            p = stack[top].link;
            sign = stack[top].flag;
            if(sign==0)
            {
                //第二次进栈
                stack[top].link = p;
                stack[top].flag = 1;
                top++;
                p = p->rightChild;
            }
            else
            {
                //访问该结点的数据域
                printf("%c ",p->data);
                //找完讲p置为空防止在继续往左找下去
                p = NULL;
            }
        }
    }
}

贰叉查找树的概念与落实

静态查找:二分查找
动态查找:二叉搜索树;
也称之为2叉排序树,或许2叉查找树;

  • 分空左子树的全体键值小于其根节点的键值。
  • 分空右子树的富有键值大于其根节点的键值。
  • 左右子树都是二叉搜索树。

对于2叉树ADT,一般供给提供以下操作:

  • 清空二叉查找树:MakeEmpty
  • 检索有些节点:Find
  • 删除有些节点:DeleteElement
  • 探索最大值:Find马克斯
  • 搜寻最小值:FindMin
  • 插入三个节点:InsertElement
    2叉查找树的平均深度为O(log(N)),可是假如插入成分体系递增可能递减,2叉查找树将向下成单链表。

后序遍历递归完毕代码:

  /**
   * 后续遍历 递归
   * DEFBHGICA
   * 
   * @param tree
   */
  public static void postOrderTraversal(BinTree tree) {
    if (tree != null) {
      postOrderTraversal(tree.left);
      postOrderTraversal(tree.right);
      System.out.print(tree.name);
    }
  }

2叉树的层序遍历

对于先序,中序,后序来讲,他们属于深度遍历,也等于先探到低然后再折回到。对于层序遍历来讲,顾名思义,便是1层1层的扫过去,所以层序遍历的不二等秘书籍为先上层在下层,同层之间,从左到遍历过去。从这么的遍历描述能够观望该遍历为广度遍历,可用队列来兑现。
上海体育场合的遍历结果为: ABCDfEG

#define Error 0
#define OK 1
#define MAXSIZE 100
typedef char DataType;
typedef struct node
{
    DataType data;
    struct node* leftChild;
    struct node* rightChild;
}BinNode;
typedef BinNode* BinTree;
typedef BinTree ElemType;
typedef struct
{
    ElemType data[MAXSIZE];
    int front;
    int rear;
}SeQueue;
typedef int Status;

Status InitQueue(SeQueue *q)
{
    q->front = 0;
    q->rear = 0;
    return OK;
}
int EmptyQueue(SeQueue *q)
{
    if(q->rear == q->front)
        return 1;
    else
        return 0;
}
ElemType FrontQueue(SeQueue *q)
{
    if(EmptyQueue(q))
    {
        printf("Empty!\n");
    }
    return q->data[q->front];
}
Status DeQueue(SeQueue *q)
{
    if(EmptyQueue(q))
        return Error;
    q->front++;
    return OK;
}
Status EnQueue(SeQueue *q,ElemType e)
{
    if(q->rear == MAXSIZE)
        return Error;
    q->data[q->rear] = e;
    q->rear++;
    return OK;
}
Status LevelOrder(BinTree bt)
{
    if(bt==NULL)
        return Error;
    SeQueue q;
    InitQueue(&q);
    EnQueue(&q,bt);
    while(!EmptyQueue(&q))
    {
        BinTree tmp = FrontQueue(&q);   //获取队头元素
        printf("%c",tmp->data);
        //同层元素从左到右进行遍历
        if(tmp->leftChild!=NULL)        
            EnQueue(&q,tmp->leftChild);
        if(tmp->rightChild!=NULL)
            EnQueue(&q,tmp->rightChild);
        DeQueue(&q);
    }
    printf("\n");
    return OK;
}

贰叉查找树的落到实处

二叉树的中坚构造定义:

template <typename DataType>
struct Node
{
    DataType data;
    Node *left;
    Node *right;
    Node(DataType inData): data(inData), left(nullptr), right(nullptr) {}
};

template <typename DataType>
class BinarySearchTree
{
public:
    BinarySearchTree(): root(nullptr) {}
    ~BinarySearchTree();
    void MakeEmpty(); //清空二叉查找树
    void MakeEmptyNon(); //非递归清空二叉树
    Node<DataType> * Find(DataType inElement); //查找某个元素
    Node<DataType> * FindNon(DataType inElement); //非递归查找
    void DeleteElement(DataType inElement); //删除一个节点
    Node<DataType> * FindMax(); //查找最大元素
    Node<DataType> * FindMaxNon(); //非递归查找最大元素
    Node<DataType> * FindMin(); //查找最小元素
    Node<DataType> * FindMinNon(); //非递归查找最小元素
    Node<DataType> * InsertElementNon(DataType inElement); //非递归插入一个元素
private:
    void MakeEmptyCore(Node<DataType> *inNode);
    Node<DataType> *FindCore(Node<DataType> *inNode, DataType inElement);
    //删除一个节点
    Node<DataType> * DeleteElementCore(Node<DataType> *inNode, DataType inElement);
    Node<DataType> *FindMaxCore(Node<DataType> *inNode);
    Node<DataType> *FindMinCore(Node<DataType> *inNode);
    Node<DataType> *root;
};

二叉查找树的基本数据成员为
递归清空核心函数:

template <typename DataType>
void BinarySearchTree<DataType>::MakeEmptyCore(Node<DataType> *inNode)
{
    if (inNode == nullptr) {
        return;
    }
    MakeEmptyCore(inNode->left);
    MakeEmptyCore(inNode->right);
    delete inNode;
}

递归清空宗旨函数

template <typename DataType>
void BinarySearchTree<DataType>::MakeEmptyCore(Node<DataType> *inNode)
{
    if (inNode == nullptr) {
        return;
    }
    MakeEmptyCore(inNode->left);
    MakeEmptyCore(inNode->right);
    delete inNode;
}

递归清空入口函数,调用清空主题函数

template <typename DataType>
void BinarySearchTree<DataType>::MakeEmpty()
{
    MakeEmptyCore(root); root = nullptr;
}

非递归清空函数,选取某种非递归遍历函数理念就可以

template <typename DataType>
void BinarySearchTree<DataType>::MakeEmptyNon()
{
    stack<Node<DataType> *> nodeStack;
    Node<DataType> *cycleIter = root;
    while (cycleIter != nullptr || !nodeStack.empty()) {
        while (cycleIter != nullptr) {
            nodeStack.push(cycleIter);
            cycleIter = cycleIter->left;
        }

        if (!nodeStack.empty()) {
            Node<DataType> * tmp = nodeStack.top();
            cycleIter = tmp->right;
            delete tmp; nodeStack.pop();
        }
    }
    root = nullptr;
}

递归查找某些成分

template <typename DataType>
Node<DataType> *BinarySearchTree<DataType>::FindCore(Node<DataType> *inNode, DataType inElement)
{
    if (inNode == nullptr) {
        return nullptr;
    }
    if (inNode->data == inElement) {
        return inNode;
    }
    else if (inNode->data > inElement){
        return FindCore(inNode->left, inElement);
    }
    else {
        return FindCore(inNode->right, inElement);
    }
    return nullptr;
}

非递归查找

template <typename DataType>
Node<DataType> * BinarySearchTree<DataType>::FindNon(DataType inElement)
{
    Node<DataType> *cycleIter = root;
    while (cycleIter != nullptr) {
        if (cycleIter->data == inElement) {
            return cycleIter;
        }
        else if (cycleIter->data > inElement){
            cycleIter = cycleIter->left;
        }
        else {
            cycleIter = cycleIter->right;
        }
    }
    return nullptr;
}

递归删除节点函数大旨函数

template <typename DataType>
Node<DataType> * BinarySearchTree<DataType>::DeleteElementCore(Node<DataType> *inNode, DataType inElement)
{
    if (inNode == nullptr) {
        return nullptr;
    }
    else if (inNode->data > inElement) {
        inNode->left = DeleteElementCore(inNode->left, inElement);
    }
    else if (inNode->data < inElement) {
        inNode->right = DeleteElementCore(inNode->right, inElement);
    }
    else {
        if (inNode->left != nullptr && inNode->right != nullptr) {
            Node<DataType> *tmp = FindMinCore(inNode->right);
            inNode->data = tmp->data;
            inNode->right = DeleteElementCore(inNode->right, inNode->data);
        }
        else {
            Node<DataType> *tmp = inNode;
            if (inNode->left == nullptr) {
                inNode = inNode->right;
            }
            else {
                inNode = inNode->left;
            }
            delete  tmp;
        }
    }
    return inNode;
}

递归查找最大因素基本函数

template <typename DataType>
Node<DataType> * BinarySearchTree<DataType>::FindMaxCore(Node<DataType> *inNode)
{
    if (inNode == nullptr) {
        return nullptr;
    }
    else if (inNode->right == nullptr) {
        return inNode;
    }
    else {
        return FindMaxCore(inNode->right);
    }
}

递归查找最大因素

template <typename DataType>
Node<DataType> * BinarySearchTree<DataType>::FindMax()
{
    if (root == nullptr) {
        return nullptr;
    }
    return FindMaxCore(root);
}

非递归查找最大因素

template <typename DataType>
Node<DataType> * BinarySearchTree<DataType>::FindMaxNon()
{
    if (root == nullptr) {
        return nullptr;
    }
    Node<DataType> *pre = root;
    Node<DataType> *cycleIter = pre->right;
    while (cycleIter != nullptr) {
        pre = cycleIter;
        cycleIter = pre->right;
    }
    return pre;
}

递归删除节点函数宗旨因素

template <typename DataType>
Node<DataType> * BinarySearchTree<DataType>::DeleteElementCore(Node<DataType> *inNode, DataType inElement)
{
    if (inNode == nullptr) {
        return nullptr;
    }
    else if (inNode->data > inElement) {
        inNode->left = DeleteElementCore(inNode->left, inElement);
    }
    else if (inNode->data < inElement) {
        inNode->right = DeleteElementCore(inNode->right, inElement);
    }
    else {
        if (inNode->left != nullptr && inNode->right != nullptr) {
            Node<DataType> *tmp = FindMinCore(inNode->right);
            inNode->data = tmp->data;
            inNode->right = DeleteElementCore(inNode->right, inNode->data);
        }
        else {
            Node<DataType> *tmp = inNode;
            if (inNode->left == nullptr) {
                inNode = inNode->right;
            }
            else {
                inNode = inNode->left;
            }
            delete  tmp;
        }
    }
    return inNode;
}

后序遍历非递归达成代码:

有二种思路:

先是种思路:对于任一结点P,将其入栈,然后沿其左子树一贯往下搜索,直到寻找到未有左孩子的结点,此时该结点出现在栈顶,不过此时无法将其出栈并访问,因而其右孩子还为被访问。所以接下去依照同样的平整对其右子树进行同样的处理,当访问完其右孩猪时,该结点又并发在栈顶,此时能够将其出栈并走访。那样就保险了正确的拜访顺序。能够见到,在那几个历程中,每种结点都四回面世在栈顶,唯有在第贰次出现在栈顶时,技巧访问它。由此必要多设置多个变量标记该结点是还是不是是第3回出现在栈顶。

/**
   * 后续遍历 非递归
   * DEFBHGICA
   *
   * @param root
   */
  public static void postOrderTraversalNODIGUI(BinTree root) {
    BinTree cur;
    BinTree pre = null;
    Stack<BinTree> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
      cur = stack.top();
      if ((cur.left == null && cur.right == null)
          || (pre != null && (pre == cur.left || pre == cur.right))) {
        System.out.println(cur.name);
        stack.pop();
        pre = cur;
      } else {
        if (cur.right != null) {
          stack.push(cur.right);
        }
        if (cur.left != null) {
          stack.push(cur.left);
        }
      }
    }
  }

第二种思路:对于任一节点,将其左子树入栈,直到左子树为空,查看当前栈顶得成分是不是有右子树只怕当前右子树不等于前一做客节点,如有,重复在此以前将其左子树入栈,未有,访问当前节点,并把此节点出栈,并把当下节点作为访问过的节点。

 /**
   * 后续遍历 非递归
   * DEFBHGICA
   *
   * @param root
   */
  public static void postOrderTraversalNODIGUI2(BinTree root) {
    BinTree tree = root;
    BinTree cur = null;
    BinTree pre = null;
    Stack<BinTree> stack = new Stack<>();
    while (!stack.isEmpty() || tree != null) {
      while (tree != null) {
        stack.push(tree);
        tree = tree.left;
      }
      cur = stack.top();
      if (cur.right != null && (pre != null && cur.right != pre)) {
        tree = cur.right;
      } else {
        System.out.println(cur.name);
        stack.pop();
      }
      pre = cur;
    }
  }

(四)层序遍历

层序遍历用到了队列,Java中有现有的连串,所以就挑选了链表式的行列。
非递归代码

/**
   * 层序遍历
   * 
   * @param boot
   */
  public static void LevelOrderTraversal(BinTree boot) {
    LinkedBlockingQueue<BinTree> queue = new LinkedBlockingQueue<>();
    BinTree tree;
    if (boot == null) return;
    queue.add(boot);
    while (!queue.isEmpty()) {
      tree = queue.remove();
      System.out.println(tree.name);
      if (tree.left != null) {
        queue.add(tree.left);
      }
      if (tree.right != null) {
        queue.add(tree.right);
      }
    }
  }
先写到那吗,等学到了再立异。

2017.3.9

(5)求多少个贰叉树的深度

/**
   * 树的深度
   *用到了递归
   * @param bt
   */
  public static int postOrderGetHeight(BinTree bt) {
    int leftHeight;
    int rightHeight;
    int maxHeight;
    if (bt != null) {
      leftHeight = postOrderGetHeight(bt.left);
      rightHeight = postOrderGetHeight(bt.right);
      maxHeight = leftHeight > rightHeight ? leftHeight : rightHeight;
      return maxHeight + 1;
    }
    return 0;
  }

相关文章

网站地图xml地图